The set $A{}$ of positive integers satisfies the following conditions: If a positive integer $n{}$ belongs to $A{}$, then $2n$ also belongs to $A{}$; For any positive integer $n{}$ there exists an element of $A{}$ divisible by $n{}$; There exist finite subsets of $A{}$ with arbitrarily large sums of reciprocals of elements. Prove that for any positive rational number $r{}$ there exists a finite subset $B\subset A$ such that \[\sum_{x\in B}\frac{1}{x}=r.\]
Problem
Source: Russian TST 2022, Day 3 P3
Tags: algebra, number theory
GuvercinciHoca
29.03.2023 21:32
Bump bumpp
sevket12
09.04.2023 14:24
Say special set such $A$ .Define positive rational $r$ as good iff for any special set $A$ there exist finite subset $B$ of $A$ $\sum_{x\in B}\frac{1}{x}=r.$ We will show that every positive rational number is good. Lemma 1: If $x$ is good then $\frac{x}{2}$ is also good .
Trivial $\square$
Lemma 2: If $x,y$ are good then $x+y$ is also good.
We know that there is a finite subset $B$ of $A$ such that $\sum_{x\in B}\frac{1}{x}=r.$
Let define minimal set C such that $x \in C $then $2x \in C$ and if we take $u\in B$ $\frac{u}{v_2(u)} \in C$
$A'= A /C$ we can see that $A'$ is special set .(why?) Then there is a finite subset of $D$ of $A'$ such that
$\sum_{x\in D}\frac{1}{x}=y.$ and we can see that $B \cap D= \varnothing$ so we are done .$\square$
Lemma 3: 1 is good number.
sub-Lemma: Let $2^{(\alpha+1)}>x \geq 2^{(\alpha)} $if $x\in A$ then we can write $\frac{1}{2^{\alpha}}$
ProofLet $x=\sum2^{\alpha_i}$ $\alpha_1<\alpha_2<...<alpha_k=\alpha$
$\frac{1}{2^{alpha}}=\frac{1}{x.2^{alpha}}.\sum2^{\alpha_i}$ all terms in summation in $A$ so we are done.
Let set $K$ defined as follows $x \in K$ iff $x \in A$ but $\frac{x}{2}$ is not.We can easily se that
$\sum_{x\in K}\frac{1}{x}=\infty$
From sub-Lemma take $\frac{1}{2^{\alpha}}$ for all elements of $K$ since $\frac{1}{2^{\alpha}}>\frac{1}{x}$ we have $\frac{1}{2^{\alpha}}$ which has sum $\infty$ Take finite $\frac{1}{2^{\alpha}}$ such that summation is greater than $1$ we claim that we can write 1 with these $\frac{1}{2^{\alpha}}$ if two of them is same $\frac{1}{2^n} , \frac{1}{2^n} \rightarrow \frac{1}{2^{n-1}} $ at the end of the process if we dont have 1 this means there is maximum 1 $\frac{1}{2^i}$ but this contradicts with sum is greater then 1 . $\square$
Lemma 4 : $\frac{1}{n}$ is good.
Its enough to show that for odd $n$
Since $1$ is good from lemma1 and lemma 2 $\frac {a}{2^b}$ is good for all positive integers $a$ and nonnegaative integers $b$
Now take an element of $A$ divisible by $n$
Let this element is $nl$.
We know that we can write $\frac{1}{n.2^{beta}}$ for large enough $\beta$
Take $\beta$ divisible by $\phi(n)$ then
$\frac{1}{n}=\frac{1}{n.2^{\beta}}+\frac{\frac{2^{\beta}-1}{n}}{2^\beta}$ we are done. $\square$
From lemma 4 and lemma 2 we are done. $\blacksquare$
Supercali
28.07.2023 18:00
Seldom do I encounter a problem of such beauty. We say that a positive rational $r$ is priced by $B$ if $B$ is a finite subset of $A$ and the sum of reciprocals of elements of $B$ is $r$. We just say $r$ is priced if it is priced by some subset of $A$. $r$ is called crowned if for any $N>0$, there exists a finite subset $B \subset A$ such that $r$ is priced by $B$ and every element of $B$ is greater than $N$. We have to prove that every positive rational is priced. Call an integer $a \in A$ pure if $\frac{a}{2} \notin A$. Note that for any $b \in A$, $\frac{b}{2^k}$ is pure for some unique $k \geq 0$. Therefore, if the set of pure elements is $P$, then $A$ is the disjoint union of $P,2P,4P, \dots$. If sum of reciprocals of elements of $P$ is finite, then $$\sum_{x \in A} \frac{1}{x} = \left(1+\frac12+\frac14+\cdots\right)\sum_{y \in P} \frac{1}{y} = 2 \sum_{y \in P} \frac{1}{y} < \infty,$$which contradicts condition 3. Hence sum of reciprocals of elements of $P$ diverges. Let $f(i)$ denote the number of pure integers in the interval $[2^i,2^{i+1})$, for $i \geq 0$. Then the above paragraph implies that $$\sum_{i=0}^\infty \frac{f(i)}{2^i} = \infty.$$Now, let $a \in [2^i,2^{i+1})$ be pure. We claim that $\frac{1}{2^i}$ is priced by a subset of $\{a,2a,4a,\dots\}$. Indeed, let $a=2^{b_0}+2^{b_1}+\cdots +2^{b_k}$ in binary with $b_0<b_1<\cdots < b_k \leq i$ since $a<2^{i+1}$. Then $$\frac{1}{2^{i-b_0}a}+\frac{1}{2^{i-b_1}a}+\cdots+\frac{1}{2^{i-b_k}a}=\frac{1}{2^i}$$as required. Note that if $a_1 \neq a_2$ are pure, then the sets $\{a_1,2a_1,4a_1,\dots\}$ and $\{a_2,2a_2,4a_2,\dots\}$ are disjoint. Therefore the above result immediately gives us the following: If $b_1,b_2,b_3, \dots$ is a sequence of non-negative integers such that $b_i \leq f(i)$ for each $i$ and $b_i=0$ for all but finitely many $i$, then $\sum_{i=0}^\infty \frac{b_i}{2^i}$ is priced. This is because each $\frac{1}{2^i}$ can be priced using a different pure integer in the interval $[2^i,2^{i+1})$. Claim 1: All positive dyadic rationals (i.e., numbers of the form $\frac{p}{2^m}$) are crowned. Proof: Let $N>0$ be arbitrary, and choose a $k \geq m$ such that $2^k>N$. Note that $\sum_{j=k}^\infty \frac{f(j)}{2^j}$ diverges. Hence, by repeatedly adding $\frac{1}{2^j}$ until we overshoot, we can find an index $i \geq k$ and a non-negative integer $b<f(i)$ such that $$\frac{b}{2^i}+\sum_{j=k}^{i-1} \frac{f(j)}{2^j}<\frac{p}{2^m} \leq \frac{b+1}{2^i}+\sum_{j=k}^{i-1} \frac{f(j)}{2^j}$$$$\implies b+\sum_{j=k}^{i-1} 2^{i-j}f(j)<2^{i-m}p \leq b+1+\sum_{j=k}^{i-1} 2^{i-j}f(j).$$This is only possible if $$2^{i-m}p = b+1+\sum_{j=k}^{i-1} 2^{i-j}f(j)$$$$\implies \frac{p}{2^m} = \frac{b+1}{2^i}+\sum_{j=k}^{i-1} \frac{f(j)}{2^j},$$and we know from the above paragraph that the RHS is priced by a set of integers not less than $2^k>N$. $\blacksquare$ Claim 2: If $x$ is crowned and $y_1,y_2,\dots ,y_k$ are distinct numbers satisfying $\frac{1}{y_i} \in A$ for each $y_i$, then $x+y_1+y_2+\cdots + y_k$ is priced. Further, if $x,z$ are crowned, then $x+z$ is also crowned. Proof: Straightforward: Choose representations for $x$ and $z$ with sufficiently large elements. $\blacksquare$ Let $r=\frac{p}{q}$ be an arbitrary positive rational. Let $s$ be such that $sq \in A$, which exists by condition 2. Write $s=2^km$ where $m$ is odd. Choose large distinct integers $M_1,M_2, \dots M_{sp}>2023^{2023^{2023}}$ such that $mq \mid 2^{M_i}-1$ for each $i$. Note that $\frac{1}{sq}=\frac{1}{2^{M_i}sq}+\frac{p_i}{2^{k+M_i}}$ for each $i$, where $p_i=\frac{2^{M_i}-1}{mq}$ is a positive integer. Therefore $$r=\frac{sp}{sq}=\sum_{i=1}^{sp}\frac{1}{2^{M_i}sq}+\sum_{i=1}^{sp}\frac{p_i}{2^{k+M_i}}.$$By Claims 1 and 2, $\sum_{i=1}^{sp}\frac{p_i}{2^{k+M_i}}$ is crowned. Further, the $2^{M_i}sq$ are distinct elements of $A$, so by Claim 2, $r$ is priced, as required.
math_comb01
19.02.2024 15:27
Very Beautiful and nice problem! Sketch: Call a rational number $r$ nice if it can be represented in the said form. Claim 1: $r$ is nice then $\frac{r}{2}$ is also nice
Obvious by using the 1st condition
Claim 2: $r,s$ are nice, then $r+s$ is also nice
Choose sufficiently large elements..
Claim 3: If there is some $x \in A$ s.t. $2^{\aleph} < x \leq 2^{\aleph +1}$ then $2^{\aleph}$ is nice.
Obvious by base expansion and using Claim 2.
Call an element $t \in A$ primitive if $\frac{t}{2} \not\in A$. Claim 4: $1$ is nice.
Here the idea is to notice $\sum_{s \in A} \frac{1}{s} = \infty$ which follows from the fact since $A$ is disjoint union of primitive$\cdot 2^k$, so if this does noot diverge this would contradict condition 3. Now applying Claim 4, and noting $\frac{1}{2^{\aleph}} > \frac{1}{x}$, so if we don't reach $1$ this means that there is a maximal element less than 1, contradiction.
Claim 5: $\frac{1}{n}$ is nice for all $n \in \mathbb{N}$
Note that by Claim 1, we have that $\frac{a}{2^b}$ is nice for all naturals $a,b$. Take an element $\alpha$ of $A$ divisible by $\varphi(n)$, so now by the identity(or variants) $\frac{1}{n} = \frac{1}{2^{\alpha}k} + \frac{\frac{2^{\alpha}-1}{n}}{2^{\alpha}}$we're done.
By using Claim 2 and Claim 5 repeatedly we're done.