Balkan 96/4 solution

13th Balkan 1996

Problem 4

Can we find a subset X of {1, 2, 3, ... , 2¹⁹⁹⁶-1} with at most 2012 elements such that 1 and 2¹⁹⁹⁶-1 belong to X and every element of X except 1 is the sum of two distinct elements of X or twice an element of X?

Solution

Answer: yes.

In the sequence 2ⁿ - 1, 2ⁿ⁺¹ - 2, 2ⁿ⁺² - 2², ... , 2²ⁿ - 2ⁿ, 2²ⁿ - 1 each number is double its predecessor, except for the last number which is the sum of its predecessor and the first number. Thus by adding n elements we can extend a sequence from 2ⁿ - 1 to 2²ⁿ - 1 whilst preserving the property that each element (except the first) is the sum of two previous elements or is double a previous elements.

Thus starting with 1 = 2¹ - 1, we can construct a sequence of 1 + 2 + 3 + 5 + 9 + 17 + 33 + 65 + 129 = 264 terms which has the property and last term 2²⁵⁶ - 1. With 243 doublings, we can extend the sequence to last term 2⁴⁹⁹ - 2²⁴³. The sequence already includes the 6 terms 2²⁴³ - 2¹¹⁵ (115 doublings after 2¹²⁸ - 1), 2¹¹⁵ - 2⁵¹, 2⁵¹ - 2¹⁹, 2¹⁹ - 2³, 2³ - 2, and 1, so by successively adding these we reach the 264 + 243 + 6 = 513rd term 2⁴⁹⁹ - 1.

We can now extend this to 2⁹⁹⁸ - 1 with a further 500 terms, then to 2¹⁹⁹⁶ - 1 with a further 999 terms, giving 2012 in all.

[To be completely explicit the set is:
1, 2=1+1, 3=1+2, 6=3+3, 12= 6+6, 15=12+3, 30=15+15, 60=30+30, 120=60+60, 240=120+120
255=240+15, 2⁸⁺ⁿ-2ⁿ=(2^8+n-1-2^n-1)+(2^8+n-1-2^n-1), n = 1, 2, ... , 8
2¹⁶-1=(2¹⁶-2⁸)+(2⁸-1), 2¹⁶⁺ⁿ-2ⁿ=(2^16+n-1-2^n-1)+(2^16+n-1-2^n-1), n = 1, 2, ... , 16
2³²-1=(2³²-2¹⁶)+(2¹⁶-1), 2³²⁺ⁿ-2ⁿ=(2^32+n-1-2^n-1)+(2^32+n-1-2^n-1), n = 1, 2, ... , 32
2⁶⁴-1=(2⁶⁴-2³²)+(2³²-1), 2⁶⁴⁺ⁿ-2ⁿ=(2^64+n-1-2^n-1)+(2^64+n-1-2^n-1), n = 1, 2, ... , 64
2¹²⁸-1=(2¹²⁸-2⁶⁴)+(2⁶⁴-1), 2¹²⁸⁺ⁿ-2ⁿ=(2^128+n-1-2^n-1)+(2^128+n-1-2^n-1), n = 1, 2, ... , 128
2²⁵⁶-1=(2²⁵⁶-2¹²⁸)+(2¹²⁸-1), 2²⁵⁶⁺ⁿ-2ⁿ=(2^256+n-1-2^n-1)+(2^256+n-1-2^n-1), n = 1, 2, ... , 243
2⁴⁹⁹-2¹¹⁵=(2⁴⁹⁹-2²⁴³)+(2²⁴³-2¹¹⁵), 2⁴⁹⁹-2⁵¹)=(2⁴⁹⁹-2¹¹⁵)+(2¹¹⁵-2⁵¹), 2⁴⁹⁹-2¹⁹=(2⁴⁹⁹-2⁵¹)+(2⁵¹-2¹⁹), 2⁴⁹⁹-2³=(2⁴⁹⁹-2¹⁹)+(2¹⁹-2³), 2⁴⁹⁹-2=(2⁴⁹⁹-2³)+6, 2⁴⁹⁹-1=(2⁴⁹⁹-2)+1
2⁴⁹⁹⁺ⁿ-2ⁿ=(2^499+n-1-2^n-1)+(2^499+n-1-2^n-1), n = 1, ... , 499
2⁹⁹⁸-1=(2⁹⁹⁸-2⁴⁹⁹)+(2⁴⁹⁹-1), 2⁹⁹⁸⁺ⁿ-2ⁿ=(2^998+n-1-2^n-1)+(2^998+n-1-2^n-1), n = 1, 2, ... , 998
2¹⁹⁹⁶-1=(2¹⁹⁹⁶-2⁹⁹⁸)+(2⁹⁹⁸-1) ].

13th Balkan 1996