Olympiad Maths Prep

Library / /1 of 5

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=2231K = 2^{23} - 1 which are divisible by nn. Therefore,
Q=2423    1+Kn=2423    2422Kn<2423    K2423<nK2422. |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/2422K/24231K/2422 - K/2423 \ge 1, then there exists an integer nn such that Q=2423|Q| = 2423. As 24222423<(21121)2<2231=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.)

Looking for a route rather than 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.