be the set of integers, and let 
be a function. Prove that there are infinitely many integers 
such that the function 
defined by 
is not bijective.
,
such that 
.
and 
be positive integers, and let 
be a 
grid of unit squares.
or 
rectangle. A subset 
of grid squares in 
edges of the grid squares.
Y by solver1104, scrabbler94, kingofgeedorah, samuel, nemesistheory, Smkh, megarnie, HWenslawski, jhu08, Adventure10
Two rational numbers 
and 
are written on a blackboard, where 
and 
are relatively prime positive integers. At any point, Evan may pick two of the numbers 
and 
written on the board and write either their arithmetic mean 
or their harmonic mean 
on the board as well. Find all pairs 
such that Evan can write 1 on the board in finitely many steps.
Proposed by Yannick Yao
and 
are written on a blackboard, where 
and 
are relatively prime positive integers. At any point, Evan may pick two of the numbers 
and 
written on the board and write either their arithmetic mean 
or their harmonic mean 
on the board as well. Find all pairs 
such that Evan can write 1 on the board in finitely many steps.Proposed by Yannick Yao
This post has been edited 1 time. Last edited by djmathman, Apr 19, 2019, 2:31 PM
for some 
.![\[\dfrac{1}{2^k}\left( m\left(\frac{n}{m}\right)+n\left(\frac{m}{n}\right)\right).\]](http://latex.artofproblemsolving.com/7/2/6/726a382a909b509b1affda6d37faf53d27ebd9d8.png)
.
(thus, proving the lemma solves the problem).
and 
are fully simplified fractions such that 
and 
,
also divides the sum of the numerator and denominator of the arithmetic and harmonic means.
respectively. Now, let 
.
,
.
and 
,
and 
,
?
writable implies 
writable.
summing to a power of two. To see that this works, say 
and note that![\[1 = \frac{m}{2^s} \cdot \frac{n}{m} + \frac{n}{2^s} \cdot \frac{m}{n}\]](http://latex.artofproblemsolving.com/0/c/d/0cd1ca48360e4e5976f3d44e1d7e5308edee5f23.png)
and we can get any dyadic average by using the arithmetic mean only.
is not a power of two, so there exists an odd prime 
.
and so every written number is congruent to 
modulo 
.
,
odd with 
.
and 
with denominators that are powers of 
can be written on the board.
but 
then 
but 
.
and 
to get 
or 
,
and 
then 
,
,
,
but 
so 
.
for an odd prime 
Also, if 
then:
so by induction, all numbers that are written on the board are 
.
for some 
,
from normal arithmetic means, and so Evan eventually may write:
for integer 
.
.
Observe that For any 
such that 
,
Which means that any numbers in blackboard are equivalent to 
since 
.
works, which is possible by weighted arithmetic mean since
(slovenia kazakhstan tournament of towns moment)
for some positive integer 
for positive integers 
are achievable by Evan.
is trivial. Assume 
works. Let 
,
.
are possible by arithmetic mean, and 
are possible by arithmetic meaning 
with 
and 
with 
,
and 
proves that the answer works. Now FTSOC assume some pair 
and 
are divisible by 
since 
is trivial. Then, the ratio the gap between 
and 1 and the gap between 1 and 
is 
,
and 
are divisible by 
Note that 
and 
.
Additionally, there will be no adverse cancellation since 
is not a multiple of 
and again we hvae 
and there will also be no adverse cancellation. Also, note that 
and 
with 
![\[2^k\left(u\cdot \frac{m}{n}+v\cdot\frac{n}{m}\right)\]](http://latex.artofproblemsolving.com/1/c/2/1c26f6b64ca6bd4f969e7cd80dd41ed656d349c2.png)
where 
are positive integers with 
.![\[2^k\left(u\cdot \frac{m}{n}+(2^k-u)\cdot\frac{n}{m}\right)=1\]](http://latex.artofproblemsolving.com/2/f/e/2feb2922878117ab63343b0fac37857ab938935a.png)
has the solution ![\[u=\frac{2^km}{m+n}\]](http://latex.artofproblemsolving.com/4/7/3/4736fee3565484413def56c9d3860846a5567cb4.png)
and since 
,
.
.![\[n=1+2^{\alpha_1}+2^{\alpha_2}+\ldots +2^{\alpha_i}\]](http://latex.artofproblemsolving.com/2/4/5/245a1d6ddf0c34c9920d2f1827bee845d7c1963b.png)
Now, when Evan will want to add 
'
and the last already written number. This will happen for every 
.
and the last already written number. In the end we will have ![\[u=1+2^{\alpha_1}+2^{\alpha_2}+\ldots +2^{\alpha_i}=n\]](http://latex.artofproblemsolving.com/0/a/e/0aecd1e86506fb3561608a3a7d719931f88b00c4.png)
so we are done.
being achievable by suitable applications of arithmetic mean; taking i=n, j=m finishes. On the other hand, note that 
(AM and HM) are s.t. the sum of numerator and denominator of either of those are divisible by an odd prime p when p|a+b,c+d, with a,b,c,d not divisible by p; this means that if the numerator eventually equals denominator, both numerator and denominator must be divisible by that odd prime p, but this is a contradiction since 2ac and 2bd are not divisible by p by assumption (and that now, ad+bc,2bd,2ac,ad+bc are all not divisible by p, meaning we reduce into a'/b',c'/d' with the same properties). We conclude. 
is a power of 
so it is possible to write 
.
,
![$r \in [0, 1]$](http://latex.artofproblemsolving.com/0/e/b/0eb56f884c6dc69389da0953cee3cbdf19832a81.png)
be a dyadic rational. Then the number 
can be formed, if 
is the pair of numbers on the board at some point.
and 
.
by looking at the binary expansion of 
,
![\[r \cdot \frac{m}{n}+(1-r) \cdot \frac{n}{m}, \]](http://latex.artofproblemsolving.com/7/c/f/7cfe87b4111c9df483610d9bbdadb3fccc19ecb9.png)
where 
.
,![\[ \frac{m}{n} \equiv \frac{n}{m} \equiv -1 \pmod{p}. \]](http://latex.artofproblemsolving.com/7/2/b/72b0cab6b637267d8064343abc628531dec2d0dd.png)
Since the arithmetic and harmonic means are preserved 
is always 
so that 
.
.
so that it is sufficient to construct all weighted averages of 
where the weights have denominator a power of 
weighted by 
with 
and average.
in reduced form that may be written on the board has 
.
,
in reduced form with 
are on the board, their arithmetic and harmonic mean must satisfy the same property.
,
which is divisible by 
,
or 
,
with 
shows that the same invariant holds for the harmonic mean as well. 
cannot be obtained since it would imply the existence of an odd prime 
,
.
cannot have 
be a power of 
can be achieved and so 
cannot be reduced to a fraction with a given sum of 
,
of the numerator and denominator can only be 
that is always retained.
must divide the numerator-denominator sum of the unreduced fraction from either operation, but ensuring that it isn't canceled out from dividing out by the 
Note that if not, then 
for some odd prime 
Then all writable terms also have to be 
)Honestly its super clean tho 
then all the fractions written on the board have the sum of their numerator and denominator a multiple of 
is by assumption. For the inductive step, let the two fractions that we apply the operation to next be 
and 
Then, the sum of the numerator and denominator will be 
Notice that the numerator of this is a multiple of 
while the denominator is not, thus proving the claim.
for some positive integer 
is an odd prime factor of 
written on the board we will have 
.
moves. Any fraction created in move ![\[\frac{\frac{a}{b}+\frac{c}{d}}{2} = \frac{(ad+bc)/\gcd(b,d)}{2bd / \gcd(b,d)}\]](http://latex.artofproblemsolving.com/f/f/8/ff8882bfc8b2c32973c36a2246c06be3e93e348b.png)
or![\[\frac{2\frac{a}{b}\cdot \frac{c}{d}}{\frac{a}{b}+\frac{c}{d}} = \frac{ad+bc/\gcd(a,c)}{2ac/ \gcd(a,c)}\]](http://latex.artofproblemsolving.com/3/3/d/33dfe5bc3f84419eb15684aa5f8067502e17d7f2.png)
Thus, the sum is either 
or 
.![\[ad+bc+2bd \equiv a(-c) + (-a)c + 2(-a)(-c) \equiv 0 \pmod{p}\]](http://latex.artofproblemsolving.com/e/e/c/eec18facbea811de56fe55135c7fcf4b4f48a00e.png)
However, 
which implies that 
for which 
and 
and we wish to mark 
using a tool which marks the midpoint of two marked points (arithmetic mean operation). Now, we can scale up by 
so we wish to mark the point 
and 
.
and the distance to the point we wish to mark from 
.
.
is also eventually marked, as desired.![\[\dfrac{1}{2^k}\left( m\left(\frac{n}{m}\right)+n\left(\frac{m}{n}\right)\right)=\dfrac{1}{2^k}(m+n)=1\]](http://latex.artofproblemsolving.com/9/8/5/985589dd48fa20df5c68e9168176724928472810.png)
in which we didnt even use the harmonic mean!
Now notice that every number on the board from this point onwards will also be 
so we can never reach 
but 
