Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A set of whole numbers is chosen from to . The rule is that no number in the set may be exactly twice another number in the set. For example, and cannot both be chosen.
What is the largest possible size of such a set? Split to into chains that start at an odd number and keep doubling, such as 3, 6, 12, 24, 48, 96. Find the most numbers you can take from each chain, and add them up. Also count how many chains there are.
Remainders on division by are boxes. The prefix sums give a block with a sum divisible by . Cut a figure into pieces: two points in one piece are close.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. Each chain is a path where neighbours are a number and its double. Take the most from each chain.
Step 1. The chains. Each number with odd lies in the chain that starts at . There are odd numbers up to , so chains.
Step 2. The most from one chain. In a chain the forbidden pairs are neighbours. From a chain of length we can take the 1st, 3rd, 5th, and so on, which is numbers. More than that would put two neighbours together, by the pigeonhole principle on the pairs (1st, 2nd), (3rd, 4th), and so on.
Step 3. Chain lengths. Odd from to give chains of length ( chains). From to , length ( chains). From to , length ( chains). Then have length ; has length ; has length ; has length .
Step 4. Add up. .
Check. A second way: take every number whose power of is even, that is , , or . That gives numbers, and no one of them is twice another.
Answer: chains, and the largest such set has numbers.
Log in to join the discussion.
Loading…