Maths Olympiad Prep

Library / /51 of 65

Number theory Difficulty 6.3 National Olympiad Prove it Bulgaria

Problem:

Consider the set A={1,2,3,4,,2n}A = \{1, 2, 3, 4, \ldots, 2^{n}\}, n2n \geq 2. Find the number of the subsets BB of AA, such that if the sum of two elements of AA is a power of 22 then exactly one of them belongs to BB.

Solution

Solution:

1. Let BB be a subset of AA having the given property. Since 1+3=221 + 3 = 2^{2}, we have that exactly one of the numbers 11 or 33 belongs to BB.
If 1B1 \in B then 3B3 \notin B. We prove by induction that for any integer tt, 0t<2n20 \leq t < 2^{n-2}, the integers of the form 4t+14t+1 belong to BB and the integers of the form 4t+34t+3 do not belong to BB. The statement is true for t=0t=0 and suppose it is true for tst \leq s. Since 4(s+1)+14(s+1)+1 is an odd number there exists ll such that 2l<4(s+1)+1<2l+12^{l} < 4(s+1)+1 < 2^{l+1}. Therefore 2(4s+5)>22l=2l+12(4s+5) > 2 \cdot 2^{l} = 2^{l+1} giving 0<2l+1(4s+5)<4s+50 < 2^{l+1} - (4s+5) < 4s+5. Set x=4s+5x = 4s+5 and y=2l+1(4s+5)y = 2^{l+1} - (4s+5). Then x+y=2l+1x + y = 2^{l+1} and since yy is of the form 4m+34m+3 we conclude that yBy \notin B and therefore 4(s+1)+1B4(s+1)+1 \in B. Analogously 4(s+1)+3B4(s+1)+3 \notin B.
If 1B1 \notin B then 3B3 \in B and we prove as above that the integers of the form 4t+14t+1 belong to BB and the integers of the form 4t+34t+3 do not.
Therefore the odd numbers in BB are either all integers of the form 4t+14t+1 or all integers of the form 4t+34t+3.
Let x=2px0x = 2^{p} x_{0} and y=2qy0y = 2^{q} y_{0}, where x0x_{0} and y0y_{0} are odd and pp and qq are positive integers. If 2px0+2qy0=2k2^{p} x_{0} + 2^{q} y_{0} = 2^{k} and pqp \neq q, say p<qp < q, then x0+2qpy0=2kpx_{0} + 2^{q-p} y_{0} = 2^{k-p}, which is impossible. Therefore p=qp = q and it follows that the sum of the elements from distinct sets Ai={2ia:aA_{i} = \{2^{i} a : a is an odd integer },i=1,2,,n\}, i = 1, 2, \ldots, n is not a power of 22. For any AiA_{i}, after dividing by 2i2^{i} and applying the above arguments, we obtain that either all integers of the form 2i(4t+1)2^{i}(4t+1) are in BB or all integers of the form 2i(4t+3)2^{i}(4t+3) are in BB.
Therefore there exist 2n+12^{n+1} sets BB with the given property.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.