Maths Olympiad Prep

Library / /58 of 69

Number theory Difficulty 6.9 National olympiad Prove it Mongolia

Let A={a1,a2,,an}A = \{a_1, a_2, \dots, a_n\} be a set of positive integers with n1n \ge 1 elements. The set AA is called good if, for any two distinct subsets XX and YY of AA (i.e., XYX \neq Y), the difference S(X)S(Y)S(X) - S(Y) is not divisible by 2n2^n. Here, S(X)=aXaS(X) = \sum_{a \in X} a denotes the sum of the elements in the subset XAX \subseteq A, and S()=0S(\emptyset) = 0 by definition.
Determine the number of good sets AA such that all elements in AA are less than 2n2^n.
(Bayarmagnai Gombodorj)

Solution

Answer: 2n(n1)/22^{n(n-1)/2}.
Let N=2nN = 2^n and v2(a)=sv_2(a) = s if and only if 2sa2^s \mid a and 2s+1a2^{s+1} \nmid a, for a positive integer aa. Let v2(A)={v2(a)aA}v_2(A) = \{v_2(a) \mid a \in A\} for the set AA.
Claim: A set AA is good if and only if v2(A)={0,1,,n1}v_2(A) = \{0, 1, \dots, n-1\}.
First we show that sets of the form An={2ibibi odd,0in1}A_n = \{2^i b_i \mid b_i \text{ odd}, 0 \le i \le n-1\} are good. For n=1n=1, this is trivial. For n1n \ge 1, assume AnA_n is good:
{S(X)(modN)XAn}={0,1,,N1}(modN), \{S(X) \pmod N \mid X \subseteq A_n\} = \{0, 1, \dots, N-1\} \pmod N,
and
{S(X)(mod2N)XAn+1}={S(X),S(X)+N(mod2N)XAn}. \{S(X) \pmod{2N} \mid X \subseteq A_{n+1}\} = \{S(X), S(X) + N \pmod{2N} \mid X \subseteq A_n\}.
This implies
{S(X)(mod2N)XAn+1}={0,1,,2N1}(mod2N). \{S(X) \pmod{2N} \mid X \subseteq A_{n+1}\} = \{0, 1, \dots, 2N-1\} \pmod{2N}.
Hence, An+1A_{n+1} is good.
Assume that A={a1,a2,,an}A = \{a_1, a_2, \dots, a_n\} is good, and M=2N1M = 2^N - 1. Since 2N1(modM)2^N \equiv 1 \pmod M and
{S(X)(modN)XA}={0,1,,N1}(modN), \{S(X) \pmod N \mid X \subseteq A\} = \{0, 1, \dots, N-1\} \pmod N,
we have
j=1n(2aj+1)=XA2S(X)k=0N12k0(modM). \prod_{j=1}^{n} (2^{a_j} + 1) = \sum_{X \subseteq A} 2^{S(X)} \equiv \sum_{k=0}^{N-1} 2^k \equiv 0 \pmod M.
Note M=i=0n1(22i+1)M = \prod_{i=0}^{n-1} (2^{2^i} + 1). Therefore, for any 0in10 \le i \le n-1, there exists 1jn1 \le j \le n such that d=gcd(22i+1,2aj+1)1d = \gcd(2^{2^i} + 1, 2^{a_j} + 1) \ne 1. Thus 22i2aj1(modd)2^{2^i} \equiv 2^{a_j} \equiv -1 \pmod d, and 22i+122aj1(modd)2^{2^{i+1}} \equiv 2^{2^{a_j}} \equiv 1 \pmod d, implying 2i+12aj2^{i+1} \mid 2^{a_j}. Since 2s1(modd)2^s \equiv 1 \pmod d where si+1s \le i+1, s>is > i. Therefore, s=i+1s = i+1, and aj=2ibia_j = 2^i b_i, where bib_i is odd. Thus, {0,1,,n1}v2(A)\{0, 1, \dots, n-1\} \subseteq v_2(A), and v2(A)=n|v_2(A)| = n.
Thus, the number of good sets such that all elements are less than 2n2^n is:
2n1×2n2××20=2n(n1)2. 2^{n-1} \times 2^{n-2} \times \dots \times 2^0 = 2^{\frac{n(n-1)}{2}}.

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 and solution reproduced as published; topic and difficulty added by this site.