Is it possible that a set consisting of $23$ real numbers has a property that the number of the nonempty subsets whose product of the elements is rational number is exactly $2422$?
Problem
Source: 2023 Turkey NMO 2nd Round P5
Tags: algebra, construction, Sets
BarisKoyuncu
22.12.2023 14:08
$\{e, 2e, 3e, \cdots, 12e, e^{-7}, 2e^{-7}, e^{-8}, e^{-10}, 2e^{-10}, \cdots, 5e^{-10}, e^{-11}, e^{-12}, e^{-31}\}$
works so the answer is Yes.
Since for any integer $n$, we have $e^n\in\mathbb{Q}\Leftrightarrow n=0$, we need to show that there are exactly $2422$ nonempty subsets of $$S=\{\underbrace{1,1,\cdots ,1}_{12\text{ times}}, -7, -7, -8, \underbrace{-10,\cdots ,-10}_{5\text{ times}}, -11, -12, -31\}$$whose sum of the elements equals to $0$ (treating each $1$ as a different number).
Let any of these sets be $P$. Notice that there should be exactly one negative number in $P$ and considering the possible values of this negative number, we can easily come up with the total number of subsets, which is $$2\cdot \binom{12}{7}+1\cdot \binom{12}{8}+5\cdot \binom{12}{10}+1\cdot \binom{12}{11}+1\cdot \binom{12}{12}=2422$$
trying_to_solve_br
22.12.2023 20:46
Trying to generalize it: For every positive integers $n,m$ with $m \leq 2^n - 1$, is there always a set of reals such that for exactly $m$ subsets of them, the product is rational?
CircleGeometryGang
22.12.2023 21:29
trying_to_solve_br wrote: Trying to generalize it: For every positive integers $n,m$ with $m \leq 2^n - 1$, is there always a set of reals such that for exactly $m$ subsets of them, the product is rational? Definitely not Other than $m = 2^n - 1$ itself, any other m with this property would have to satisfy $m \leq 2^n + 1 - 2^{\lfloor \frac{n-1}{2} \rfloor} - 2^{\lceil \frac{n-1}{2} \rceil}$ if I'm understanding the problem correctly
hakN
24.12.2023 01:32
I think the set $A\cup B\cup C$ works where: $A = \{2^{\frac{1}{2885}},2^{\frac{2^1}{2885}},2^{\frac{2^2}{2885}},\dots,2^{\frac{2^{10}}{2885}}\}$, $B = \{2\cdot 2^{\frac{1}{2885}},2\cdot 2^{\frac{2^1}{2885}},2\cdot 2^{\frac{2^2}{2885}},\dots,2\cdot 2^{\frac{2^{10}}{2885}}\}$ and $C=\{3\cdot 2^{\frac{2}{2885}}\}$. Since $2(1+2^1+2^2+\dots+2^{10})+2 = 4096 < 2\cdot 2885$, it suffices to count the number of solutions to $a+b+c=2885$ where $a,b\in \{0,1,\dots,2047\}$ and $c\in \{0,2\}$. When $c=0$, there are $2047-838+1 = 1210$ triplets and when $c=2$, there are $2047-836+1=1212$ triplets, so in total we have $2422$ triplets which is what we want.
trying_to_solve_br
24.12.2023 16:37
CircleGeometryGang wrote: trying_to_solve_br wrote: Trying to generalize it: For every positive integers $n,m$ with $m \leq 2^n - 1$, is there always a set of reals such that for exactly $m$ subsets of them, the product is rational? Definitely not Other than $m = 2^n - 1$ itself, any other m with this property would have to satisfy $m \leq 2^n + 1 - 2^{\lfloor \frac{n-1}{2} \rfloor} - 2^{\lceil \frac{n-1}{2} \rceil}$ if I'm understanding the problem correctly why?? I don't understand the bound
pavel kozlov
28.01.2024 23:36
Below is clever solution by one of my students: Let us take the set consisting of numbers $a_i=2^{2^{i-1}/3463}$ for $i=1\dots 23$. All products of elements of this set can be described as $b_i=2^{k/3463}$, where $k$ runs from $1$ to $2^{23}-1$. So we have exactly $\left [ \frac{2^{23}-1}{3463} \right] = 2422$ subsets with rational product.
tugra_ozbey_eratli
07.07.2024 12:07
$\{e, e^{2}, e^{4}, e^{8}, e^{16}, e^{32}, e^{-11}, 2e^{-11}, \cdots, 13e^{-11}, e^{-52}, 2e^{-52}, 3e^{-52}, e^{-53}\}$ This construction works so the answer is Yes. This works because you can see that the number of the nonempty subsets whose product of the elements is rational number is exactly $$\binom{13}{1}+\binom{13}{2}+\binom{13}{3}+\binom{13}{4}+\binom{13}{5}+3\cdot13+4=2422$$