Maths Olympiad Prep

Library / Turkish Mathematical Olympiad /5 of 47

Turkish Mathematical Olympiad

Combinatorics Difficulty 5.6 AIME, harder Prove it Turkey

Is it possible that a set consisting of 2323 real numbers has exactly 24222422 non-empty subsets such that the product of all elements of each subset is a rational number?

Solution

Answer: Yes.
Let nn be a positive integer whose value will be determined later on. Let SS be the set consisting of 2n2^n's for i=0,1,…,22i = 0, 1, \dots, 22. Let QQ be the set of subsets of SS whose product of own elements is a rational number together with the empty set. Since every positive integer has a unique representation as sum of distinct powers of 22, the cardinality of QQ is precisely the number of integers from 00 to K=223−1K = 2^{23} - 1 which are divisible by nn. Therefore,
∣Q∣=2423  ⟺  1+⌊Kn⌋=2423  ⟺  2422≤Kn<2423  ⟺  K2423<n≤K2422. |Q| = 2423 \iff 1 + \left\lfloor \frac{K}{n} \right\rfloor = 2423 \iff 2422 \le \frac{K}{n} < 2423 \iff \frac{K}{2423} < n \le \frac{K}{2422}.
Thus, if K/2422−K/2423≥1K/2422 - K/2423 \ge 1, then there exists an integer nn such that ∣Q∣=2423|Q| = 2423. As 2422⋅2423<(2112−1)2<223−1=K2422 \cdot 2423 < (2^{11}\sqrt{2} - 1)^2 < 2^{23} - 1 = K, there is such an nn. (Indeed, n=3463n = 3463 fulfills the condition.)

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

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