Let's Solve INMO 2023
It is a difficult question paper
Problem 1
Let $S$ be a finite set of positive integers. Assume that there are precisely $2023$ ordered pairs $(x, y)$ in $S \times S$ so that the product $xy$ is a perfect square. Prove that one can find at least four distinct elements in $S$ so that none of their pairwise products is a perfect square.
Note: As an example, if $S=\{1,2,4\},$ there are exactly five such ordered pairs: $(1,1),(1,4),(2,2),(4,1),$ and $(4,4)$.
Solution :
For each $x\in S$, define $S_x = \{y \mid y\in S\; $&$\; xy\text{ is a perfect square}\}$. Now, let us prove the following properties of set $T$ which is the collection of sets $S_x$, for every $x\in S$.
So, the collection of all sets $S_x$ will be either the same (or) disjoint and covering the entire set $S$ which forms a partition of $S$. Now according to the question given, we need to prove that there is always greater than 3 partitions in $S$, so that one can choose exactly one number from some 4 partitions of $S$, say $n_1, n_2, n_3, n_4$, and obviously $S_{n_1}, S_{n_2}, S_{n_3}, S_{n_4}$ will be pairwise disjoint and hence their pairwise product will not be a perfect square.
Suppose there are total $n$ partitions of $S$, then multiplying two numbers of $S$ form a perfect square if and only if both of these numbers are from the same partition in $S$ which follows directly from the 3 properties of $T$. Let $x_1, x_2, \ldots, x_n$ represent the number of numbers in each of the $n$ partitions of $S$ as shown above, then the number of ordered pairs from each of the partition will be $x_i\times x_i = x_i^2$. So,
\[\text{Total number of ordered pairs} = x_1^2 + x_2^2 + \cdots + x_n^2 = 2023\]
Case 1:
If $n=1$, then $x_1^2 = 2023$, but we know that a perfect square cannot end with $3$, so this case is not possible.
Case 2:
If $n=2$, then $x_1^2 + x_2^2 = 2023$. We know that any perfect square is congruent to $0$ (or) $1\pmod{4}$. So, the LHS, $x_1^2+x_2^2 \equiv 0\ (or)\ 1\ (or)\ 2\pmod{4}$, but the RHS, $2023\equiv 3\pmod{4}$, which is not possible.
Case 3:
If $n=3$, then $x_1^2 + x_2^2 + x_3^2 = 2023$. Going$\pmod{4}$ we see that each of $x_1^2,\ x_2^2,\ x_3^2 \equiv 1\pmod{4}$ since $2023\equiv 3\pmod{4}$ and hence they are odd numbers. Any square of an odd number is congruent to $1\pmod{8}$, since $(2k+1)^2 = 8\frac{k(k+1)}{2} + 1 = 8k'+1$, so the LHS, $x_1^2 + x_2^2 + x_3^2 \equiv 3\pmod{8}$, but the RHS, $2023\equiv7\pmod{8}$, which is a contradiction. Hence, this case is also not possible.
So, we conclude that for any such set $S,\ n\geq 4$ and hence one can select $4$ such numbers. Actually, there is a partition of $S$ possible with $n=4$, that is, $(9, 9, 30, 31)$ because $9^2+9^2+30^2+31^2 = 2023$.
Remark: In set theory, the partitions $S_x$ is called equivalence classes of $S$ since multiplying two numbers to get a perfect square is an equivalence relation defined on $S$, which in turn results in a partition of $S$. For further reading, refer to :
Problem 2
Suppose $a_0, \ldots, a_{100}$ are positive reals. Consider the following polynomial for each $k$ in $\{0,1, \ldots, 100\}$ :
\[a_{100+k} x^{100}+100 a_{99+k} x^{99}+a_{98+k} x^{98}+a_{97+k} x^{97}+\cdots+a_{2+k} x^2+a_{1+k} x+a_k,\]where indices are taken modulo $101$, i.e., $a_{100+i}=a_{i-1}$ for any $i$ in $\{1,2, \ldots, 100\}$. Show that it is impossible that each of these $101$ polynomials has all its roots real.
Solution :
Suppose say that all the roots are real for all the polynomials and $\alpha_{ij}$ represent the $i^{th}$ root of the $j^{th}$ polynomial. Then for each $j \in \{1, 2, \ldots, 101\}$,
\[\Rightarrow \frac{1}{\alpha_{1j}^2} + \frac{1}{\alpha_{2j}^2} + \cdots + \frac{1}{\alpha_{100j}^2} \geq 0\]
\[\Rightarrow \left(\frac{1}{\alpha_{1j}} + \frac{1}{\alpha_{2j}} + \cdots + \frac{1}{\alpha_{100j}}\right)^2 - \sum_{0<m<n}^{n\leq 100} \frac{2}{\alpha_{mj}\alpha_{nj}}\geq 0\]
\[\Rightarrow \left(\frac{\sum_{(i_1,i_2,\ldots,i_{99})\in \text{99 tuples of 1 to 100}}\alpha_{i_1j}\alpha_{i_2j}\cdots\alpha_{i_{99}j}}{\alpha_{1j}\alpha_{2j}\cdots\alpha_{100j}}\right)^2 - \frac{2\sum_{(i_1,i_2,\ldots,i_{98})\in \text{98 tuples of 1 to 100}}\alpha_{i_1j}\alpha_{i_2j}\cdots\alpha_{i_{98}j}}{\alpha_{1j}\alpha_{2j}\cdots\alpha_{100j}} \geq 0\]
So, by the Vieta's formula we get,
\[\Rightarrow \frac{\left(\frac{-a_{1+k}}{a_{100+k}}\right)^2}{\left(\frac{a_k}{a_{100+k}}\right)^2} - 2\frac{\left(\frac{a_{2+k}}{a_{100+k}}\right)}{\left(\frac{a_k}{a_{100+k}}\right)} \geq 0\]
\[\Rightarrow \frac{a_{k+1}}{a_k} \geq 2\left(\frac{a_{k+2}}{a_{k+1}}\right),\text{ for each }k\in\{0,1,2,\ldots,100\} \longrightarrow(1)\]
Define $b_i \in \mathbb{R_+}$ as, $b_i = \frac{a_i}{a_{i-1}}$, for each $i\in \{1,\ldots,102\}$, so obviously $b_1=b_{102}$, then from the equation $(1)$ we have,
\[b_i \leq \frac{b_{i-1}}{2},\text{ for each }i\in\{2,\ldots,102\},\text{ so we have,}\]
\[b_{102} \leq \frac{b_{101}}{2} \leq \frac{b_{100}}{2^2} \leq \frac{b_{99}}{2^3} \leq \cdots \leq \frac{b_{2}}{2^{100}} \leq \frac{b_{1}}{2^{101}} = \frac{b_{102}}{2^{101}}\]
\[\Rightarrow b_{102}\leq \frac{b_{102}}{2^{101}}\Rightarrow b_{102} \leq 0,\]
which is not possible as $b_i$'s $\in \mathbb{R_+}$. Hence, we arrive at a contradiction and so we conclude that all the roots of all the polynomials cannot be real.
Problem 3
Let $\mathbb{N}$ denote the set of all positive integers. Find all real numbers $c$ for which there exists a function $f: \mathbb{N} \rightarrow \mathbb{N}$ satisfying:
(a) for any $x, a \in \mathbb{N}$, the quantity $\frac{f(x+a)-f(x)}{a}$ is an integer if and only if $a=1$;
(b) for all $x \in \mathbb{N}$, we have $\mid f(x)-cx\mid <2023$.
Solution :
The only possible values of $c = k+\frac{1}{2},\ \forall k\in \mathbb{N_0}$. Here, $\mathbb{N_0}$ means the set of whole numbers. The proof is illustrated below,
Claim 1: For any integers $k \geq 1$ and $x,\ f\left(x+2^k\right)-f(x)$ is divisible by $2^{k-1}$ but not $2^k$.
Proof. We prove this via induction on $k$.
For $k=1$, the claim is trivial as $2^0$ divides any integer. Now assume the statement is true for some $k$, and hence $f\left(x+2^k\right)-f(x)=2^{k-1} y_1$ and $f\left((x+2^k)+2^k\right)-$ $f\left(x+2^k\right)=2^{k-1} y_2$ for some odd integers $y_1, y_2$. Adding these equations, we see that,
\[f\left(x+2^{k+1}\right)-f(x)=2^{k-1}\left(y_1+y_2\right)\]which is divisible by $2^k$ because $y_1+y_2$ is even. The fact that this is not divisible by $2^{k+1}$ follows from the condition (a) on $f$.
Now using the Claim 1, we see that for any $k \geq 1,\ f\left(1+2^k\right)=f(1)+2^{k-1}\left(2 y_k+1\right)$ for some integer $y_k$, so we get,
\[f\left(1+2^k\right)-c\left(1+2^k\right)=f(1)-c+2^k\left(y_k+\frac{1}{2}-c\right),\ \forall k\in \mathbb{N}\]
The quantity in the LHS is bounded above by 2023 and hence the RHS is also bounded above by 2023 for all values of $k$, but $f(1)-c$ is a constant with varying value of $k$, thus $2^k\left(y_k+\frac{1}{2}-c\right)$ is bounded above. But if this quantity is never zero, then we would have,
\[2^k\left|y_k+\frac{1}{2}-c\right|=2^{k-1}\left|2 y_k+1-2 c\right| \geq 2^{k-1},\ \forall k\in\mathbb{N}\]which contradicts the boundedness of $\mid f(x)-cx\mid$. Thus we must have $y_k+\frac{1}{2}-c=0$, for some $k \in \mathbb{N} \Rightarrow \{c\}=\frac{1}{2}$, where $\{x\}$ represents the fractional part of $x$.
Claim 2: If $\{c\}=\frac{1}{2}$ and $c>0$, then there exist function $f(x) = \lfloor cx\rfloor + 1$ that satisfies both conditions given in the question and if $c<0$, then there exist no function satisfying the given conditions
Proof. Since fractional part of $c>0$ is $\frac{1}{2}$, we assume that $c = k+\frac{1}{2},\ \forall k\in \mathbb{N_0}$. For any $x, a\in \mathbb{N}$,\[\frac{f(x+a)-f(x)}{a} = \frac{\lfloor c(x+a)\rfloor - \lfloor cx\rfloor}{a} = \frac{1}{a}\left(\left\lfloor kx+ka+\frac{x}{2}+\frac{a}{2}\right\rfloor - \left\lfloor kx+\frac{x}{2}\right\rfloor\right)= k + \frac{1}{a}\left(\left\lfloor \frac{x}{2}+\frac{a}{2}\right\rfloor - \left\lfloor \frac{x}{2}\right\rfloor\right)\]
In the above steps, we were able to take $kx$ and $ka$ out of the greatest integer function because they are integers. In general, $\lfloor x+n\rfloor = \lfloor x\rfloor+n$, where $n\in\mathbb{Z}$. So we have,\[\frac{f(x+a)-f(x)}{a} =k + \frac{1}{a}\left(\left\lfloor \frac{x}{2}+\frac{a}{2}\right\rfloor - \left\lfloor \frac{x}{2}\right\rfloor\right)\]Observe that, it is an integer for $a=1$. But for $a \geq 2$, we have,\[\left\lfloor\frac{x+a}{2}\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor \geq\left\lfloor\frac{x+2}{2}\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor=1\]If $a=2r$, then\[\left\lfloor\frac{x+a}{2}\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor=\left\lfloor\frac{x}{2}+r\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor=r<2r=a,\]and if $a=2r+1$ for $r \geq 1$, then\[\left\lfloor\frac{x+a}{2}\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor \leq\left\lfloor\frac{x+2r+2}{2}\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor=r+1<2r+1=a\]
So in either case, the quantity $\left\lfloor\frac{x+a}{2}\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor$ is strictly between 0 and $a$, and thus cannot be divisible by $a$. Thus condition (a) holds.
The condition (b) is trivially true because, $\mid f(x)-cx\mid = \lfloor cx\rfloor -cx + 1 = 1-\{cx\}\leq 1 < 2023$
Now coming to the case in which $c<0$, we see that $\mid f(x)-cx\mid$ can go arbitrarily large for a given negative value of $c$ because, given $c<0$, one can definitely choose a natural number $x>\frac{2023}{\mid c\mid}$, so that, $\mid f(x)+(-cx)\mid > 2023$, since $f(x)>0$ and so the second condition would not be satisfied for any $f(x)$.
So, we conclude from result of the Claim 1 that $\{c\} = \frac{1}{2}$ and from the Claim 2 that for all non-negative values of $c$, such that $\{c\}=\frac{1}{2}$, there exist a function $f(x)=\lfloor cx\rfloor + 1$ satisfying both the given conditions and there exist no function for negative values of $c$ that satisfies the given conditions, and hence proving the desired values of $c$.
Problem 4
Let $k \geq 1$ and $N>1$ be two integers. On a circle are placed $2N+1$ coins all showing heads. Calvin and Hobbes play the following game. Calvin starts and on his move can turn any coin from heads to tails. Hobbes on his move can turn at most one coin that is next to the coin that Calvin turned just now from tails to heads. Calvin wins if at any moment there are $k$ coins showing tails after Hobbes has made his move. Determine all values of $k$ for which Calvin wins the game.
Solution :
We claim that Calvin wins if $k \in \{1, 2, 3, \ldots, N+1\}$. First, let us prove the case in which Calvin wins the game and then we will prove the case in which he may not win.
Step 1:
Claim: In the start of the game, Calvin can form two adjacent tails after Hobbes has made his move.
Proof. Calvin starts the game by turning a coin, say $C_0$, from heads to tails. Now, Hobbes cannot make his move as there are no adjacent tails to it. Then, Calvin turns the next to next coin of $C_0$, say $C_1$, from heads to tails. Again, Hobbes cannot make his move because $C_0$ and $C_1$ cannot be adjacent as $N\geq 2$. Then, Calvin turns the coin between $C_0$ and $C_1$, say $C_2$, from heads to tails. Now, Hobbes have an option to turn $C_0$ (or) $C_1$ back to heads. But in any case, we get two adjacent tails after Hobbes has made his move, thus proving the claim.
By the above claim, assume that we have only two adjacent tails and Calvin is supposed to move now. Let the two adjacent tails be $T_1$ and $T_{N+1}$. Calvin turns the next to next coin of $T_1$ that is not adjacent to $T_{N+1}$, say $T_2$, from heads to tails. Now, Hobbes cannot make a move as there are no adjacent tails to $T_2$. Again, Calvin turns the next to next coin of $T_2$ from heads to tails until he reaches the coin $T_{N+1}$. Note that any move of Calvin after forming the adjacent tails $T_1$ and $T_{N+1}$ will not form anymore adjacent tails as the total number of coins is odd and consequently Hobbes cannot make a move. There are $2N-1$ coins except $T_1$ and $T_{N+1}$ and so there are $N-1$ more tails formed by this alternating tails and heads configuration due to Calvin's move. So, in total there are $N+1$ tails after the Hobbes move. Since the number of tails increases by one in the procedure after each of the Hobbes move (which was not possible anyways), for each $k \in \{1, 2, 3, \ldots, N+1\}$, Calvin wins the game by following the above procedure (obviously he cannot win for $k\geq 2$ if he turn the coins randomly). An example of the procedure is illustrated below for $N=3$ attaining $4=N+1$ tails,
Remark: The procedure has total $N+3$ moves and irrespective of value of $N$, Hobbes can make only one move which forms the first adjacent tails after his move.
Step 2:
Pair up the adjacent coins to form $N$ blocks of coin pairs, say $B_1, B_2, \ldots, B_N$, and a single coin, say $C_1$, as shown in the figure below for $N=3$,
Claim: There is a playing strategy for Hobbes that will not allow both coins of any block to show tails after each move of Hobbes.
Proof. Let us prove this claim by induction on the number of moves by Hobbes. Obviously, it is true for the first move of Hobbes, since by the time Calvin has turned only one coin to tails. Let us assume that the claim is true for "$(n-1)^{th}$" move of Hobbes, i.e., there is no block with both coins showing tails in it after $(n-1)^{th}$ move of Hobbes. Now after Calvin's $n^{th}$ move, there is at most one block with both coins showing tails as he can turn only one coin and if there is such a block after Calvin's move, say $B_i$, then the latest turned coin, say $C_0$, must be in the block $B_i$ and hence, Hobbes turns the adjacent coin of $C_0$ that is in the block $B_i$ from tails to heads which makes sure that there is no block with both coins showing tails after his $n^{th}$ move. Hence, by principle of induction, there is a playing strategy for Hobbes that will not allow both coins of any block to show tails after each move of Hobbes.
Claim: Calvin may not win the game if $k\geq N+2$.
Proof. Now we know that there are $N$ blocks and a coin in total and after each move of Hobbes there is at most one coin showing tails in each block by the above strategy and hence there is at most $N+1$ coins showing tails in total after Hobbes move with the above strategy and hence Calvin will not win the game if $k\geq N+2$ and if Hobbes adopts the above strategy.
Remark: If the total number of coins were even, say $2N$, then Calvin wins the game if $k\in \{1, 2, \ldots, N\}$, which can be easily proved using an argument similar to the above procedure.
Problem 5
Euler marks $n$ different points in the Euclidean plane. For each pair of marked points, Gauss writes down the number $\left\lfloor\log _2 d\right\rfloor$ where $d$ is the distance between the two points. Prove that Gauss writes down less than $2n$ distinct values.
Note: For any $d>0,\left\lfloor\log _2 d\right\rfloor$ is the unique integer $k$ such that $2^k \leq d<2^{k+1}$.
Solution :
We will prove that Gauss writes down at most $n-1$ distinct even numbers and $n-1$ distinct odd numbers and hence, in total at most $2n-2$ distinct numbers which is less than $2n$.
Definition:
Claim 1: Consider a simple graph $G$ with $m$ vertices, where $m\in\mathbb{N}$. If $G$ is connected with no cycle in it, then $G$ has exactly $m-1$ edges.
Proof. If $m=1$, then the claim is trivially true. For $m>1$, let the $m$ vertices be $x_1, x_2, \ldots, x_m$. Consider any vertex $x_i$ and an edge, say $E_1$, that is connecting it to $x_j$ for some $i, j\in\{1, 2, \ldots, m\}$ (since $G$ is connected, there must be such an edge). Consider the subgraph containing $x_i$ and $x_j$ and the edge $E_1$ to be $G_2$, which is a connected subgraph. For $i\geq2$, considering $G_i$ to be a connected subgraph of $G$ with $i$ vertices and $i-1$ edges, let us inductively define that $G_{i+1}$ is a union of the graph $G_i$ with a new edge $E_i$ that is connecting some vertex of $G_i$ to a vertex not in $G_i$, say $V_i$ and the vertex $V_i$ as shown below. Notice that $G_{i+1}$ is a connected graph because there exists such an edge $E_i$ (since $G$ is connected) and $G_i$ is also connected. So, by induction, the graph $G_m$ is connected with all the $m$ vertices and $m-1$ edges in it. Now, if there is any more edge that is in $G$ but not in $G_m$, then it must form a cycle in $G$ because there are would be two paths connecting the endpoints of this edge, one in $G_m$ and other is this edge, which contradicts our assumption in the claim. Hence, there are exactly $m-1$ edges in the graph $G$.
Claim 2: If $G$ is a simple graph with $m$ vertices, $m-1$ edges and no cycle in it, then $G$ is connected.
Proof. Let the graph $G$ have $t$ connected components in it. We know that any two connected components are each connected and disjoint so that there is no path connecting them, because they form a partition for both vertex and edge sets. Since each of the connected component is connected with no cycle in it, the number of edges in it is exactly one less than number of vertices in it. So, the total number of edges in $G$ will be $m-t$, because components partition all the edges. Hence, $t=1$ as there are $m-1$ edges. So, there must be only one connected component, which means that $G$ is connected.
Claim 3: If $G$ is a simple graph with $m$ vertices and at least $m$ edges, then $G$ must have a cycle.
Proof. Assume that there is no cycle in $G$. Now, remove few edges from the graph to get a subgraph $G_0$ with the same $m$ vertices and $m-1$ edges and no cycle in it. By the Claim 2, $G_0$ should be connected. Now, if you insert back any one of the removed edge, say $E$, into $G_0$, it forms a cycle because there are now two paths connecting the endpoints of $E$, one in $G_0$ and other is $E$, which is a contradiction to our assumption that there was no cycle in $G$. Hence, $G$ must have a cycle.
Now assume that Gauss writes at least $n$ distinct even integers and we will derive a contradiction. For every distinct even integer that Gauss writes down, construct an edge between the two points whose logarithmic distance corresponds to this value. Since there are at least $n$ distinct values, there are at least $n$ edges constructed with distinct even numbers, which forms a simple graph with vertices as the $n$ points.
Thus, we have a graph with $n$ vertices and $n$ edges and so by the Claim 3, there must be a cycle in the graph. Suppose say that the distinct even integers are $2k_1, 2k_2, 2k_3, \ldots, 2k_r$, where $r\in\mathbb{N}$ is the cycle length. Without loss of generality, let $2k_r$ be the largest and let $2k_i$ be the second largest integer. Then sum of distances of the edges corresponding to the logarithmic values $2k_1, 2k_2, \ldots, 2k_{r-1}$ is less than,
\[2^{2k_1+1}+2^{2k_2+1}+\cdots+2^{2k_{r-1}+1} \leq 2^{2k_i+1}\left(1+2^{-2}+2^{-4}+\cdots+2^{-2(r-2)}\right)\]
since $k_i$ is the second largest and the integers are distinct. So we get,
\[2^{2k_i+1}\left(1+2^{-2}+2^{-4}+\cdots+2^{-2(r-2)}\right) = 2^{2k_i+1}\left(\frac{1-\left(2^{-2}\right)^{r-1}}{1-2^{-2}}\right) = \frac{4}{3}2^{2k_i+1}\left(1-2^{-(2r-2)}\right)\]
\[\Rightarrow 2^{2k_1+1}+2^{2k_2+1}+\cdots+2^{2k_{r-1}+1} \leq \frac{4}{3}2^{2k_i+1}\left(1-2^{-(2r-2)}\right) < \frac{4}{3}2^{2k_i+1} < 2^{2k_i+2} \leq 2^{2k_r}\]
Triangle Inequality states that for any $r\geq 3$ points in the Euclidean plane, say $x_1, x_2, \ldots, x_r$, we have, $d(x_1, x_2) + d(x_2, x_3) + d(x_3, x_4) + \cdots + d(x_{r-1}, x_r) \geq d(x_r, x_1)$, which is obtained by addition of all the triangle inequalities in the triangles $(x_1, x_2, x_3)\ ;\ (x_1, x_3, x_4)\ ;\ (x_1, x_4, x_5)\ ;\ \ldots\ ;\ (x_1, x_{r-1}, x_r)$. But the above $r$ points violate this inequality as the largest distance is greater than the sum of other $r-1$ distances. Hence, we get a contradiction.
So, Gauss writes at most $n-1$ distinct even integers and by a similar argument, he writes at most $n-1$ distinct odd integers and hence, Gauss writes at most $2n-2$ distinct integers in total which is less than $2n$.
Problem 6
Euclid has a tool called cyclos which allows him to do the following:
Show that given two marked points, Euclid can draw a circle centered at one of them and passing through the other, using only the cyclos.
Solution :
For any given non-collinear points $X, Y, Z,$ let $\left(XY\right)$ represent the circle drawn with $XY$ as the diameter, $\left(XYZ\right)$ represent the circumcircle of $\triangle XYZ$ drawn using the cyclos.
Claim 1: Given any 3 non-collinear points that forms a non-right angled triangle, one can draw the nine-point circle of this triangle using only the cyclos.
Proof. Let $A, B, C$ be the three non-collinear points, then the intersection of $(AB)$ and $(AC)$ is the foot of perpendicular from $A$ to $BC$, say $P_A$. Similarly one can construct all the foot of perpendiculars, $P_B, P_C$. The points $P_A, P_B, P_C$ must be distinct as $\triangle ABC$ is non-right angled triangle. Now the circle $\left(P_AP_BP_C\right)$ is the nine-point circle of $\triangle ABC$ as it is the unique circle passing through all the foot of perpendiculars.
Claim 2: Given two points in the plane, one can mark its mid-point using only the cyclos.
Proof. Let $A, B$ be the two points, then draw the circle $(AB)$. Choose a new point $X$ on the circumference of $(AB)$. Mark the other intersection of $(XA)$ and $(XB)$ as $D$, which is the foot of perpendicular from $X$ to $\overline{AB}$. Mark the intersections of $(AD)$ and $(XD)$ to be $E$ and $(BD)$ and $(XD)$ to be $F$, which are the feet of perpendiculars from $D$ to $XA$ and $XB$ respectively. Since, $\angle AED = \angle BFD = 90^{\circ}$ and $D$ lies inside the segment $\overline{AB}\Rightarrow \angle AEB$ and $\angle AFB >90^{\circ}$, i.e., obtuse and hence $\triangle AEB$ and $\triangle AFB$ are non-right angled triangles and so we can construct the nine-point circles of $\triangle AEB$ and $\triangle AFB$ by the Claim 1. Observe that $X$ is the foot of perpendiculars from $A$ to $BF$ and $B$ to $AE$, so both the nine-point circles must pass through $X$ and also they both must pass through the midpoint of $\overline{AB}$ by definition and hence we mark the other intersection point of the two nine-point circles to get the midpoint of $\overline{AB}$, say $M$, which is illustrated in the diagram below,
Remark: Dotted red circles represent the nine-point circles of $\triangle AEB$ and $\triangle AFB$. The two nine-point circles are different, since the feet of perpendiculars from $E$ and $F$ to $AB$ are different and each of them do not lie on the other nine-point circle. And two different circles intersect at most at two points and hence we can uniquely mark the midpoint of $\overline{AB}$ without any dilemma, since the intersection point $X$ is already marked.
Construction:
Suppose say that the two marked points as per the question to be $A$ and $B$. Consider point $C$ as the reflection of $B$ with respect to the point $A$, so that $A,B,C$ are collinear with $AC=AB$, but you need not mark $C$. Mark a new point $Y$ on the circumference of $(AB)$. Mark the intersection of $(YA)$ and $(YB)$ to be $U$, which is the foot of perpendicular from $Y$ to $AB$. By the Claim 2, we can mark the midpoint of $\overline{YB}$ as $W$ using only the cyclos. Now, construct $(AUW)$ and mark the other intersection of $(AUW)$ and $(YB)$ to be $S$. Note that $(AUW)$ is the nine-point circle of $\triangle CYB$ and thus feet of perpendiculars from $Y$ to $CB$ (which is $U$) and $B$ to $CY$ lie on both $(AUW)$ and $(YB)$. So, other intersection $S$ is the foot of the perpendicular from $B$ to $CY \Rightarrow \angle CSB=90^{\circ}$. Observe that $A$ is the midpoint of hypotenuse, which is the circumcenter of $\triangle CSB \Rightarrow AB = AS$.
Repeat the same procedure by marking a new point $Z$ on the circumference of $(AB)$ to obtain the foot of perpendicular from $B$ to $CZ$, say $T$, so that $AB=AT$. Most probably, $S$ and $T$ will be distinct because $CY$ and $CZ$ cannot intersect at more than 1 point. But it might happen that $C, Y, Z$ are collinear, in which case the lines $CY$ and $CZ$ coincide and so the points $S$ and $T$ coincide. In that case, we take some other new point $Z'$ on the circumference of $(AB)$ and repeat the procedure to obtain a new point $T'$, which must be different from $S$ because now $CY$ and $CZ'$ are two different lines.
Now, Construct $(BST)$ using cyclos, which is the required circle passing through $B$ and centered at $A$ because $AB = AS = AT$ and there is such a unique point which should be the circumcenter of $\triangle BST$. The final construction diagram is provided below with dotted red circle as the required circle,
Remark: This proves that the cyclos can perform everything that a compass can perform in constructions because now cyclos can construct a circle passing through a given point centered at a given point.
Let's Solve INMO 2023
It is a difficult question paper
Problem 1
Let $S$ be a finite set of positive integers. Assume that there are precisely $2023$ ordered pairs $(x, y)$ in $S \times S$ so that the product $xy$ is a perfect square. Prove that one can find at least four distinct elements in $S$ so that none of their pairwise products is a perfect square.
Note: As an example, if $S=\{1,2,4\},$ there are exactly five such ordered pairs: $(1,1),(1,4),(2,2),(4,1),$ and $(4,4)$.
Solution :
For each $x\in S$, define $S_x = \{y \mid y\in S\; $&$\; xy\text{ is a perfect square}\}$. Now, let us prove the following properties of set $T$ which is the collection of sets $S_x$, for every $x\in S$.
So, the collection of all sets $S_x$ will be either the same (or) disjoint and covering the entire set $S$ which forms a partition of $S$. Now according to the question given, we need to prove that there is always greater than 3 partitions in $S$, so that one can choose exactly one number from some 4 partitions of $S$, say $n_1, n_2, n_3, n_4$, and obviously $S_{n_1}, S_{n_2}, S_{n_3}, S_{n_4}$ will be pairwise disjoint and hence their pairwise product will not be a perfect square.
Suppose there are total $n$ partitions of $S$, then multiplying two numbers of $S$ form a perfect square if and only if both of these numbers are from the same partition in $S$ which follows directly from the 3 properties of $T$. Let $x_1, x_2, \ldots, x_n$ represent the number of numbers in each of the $n$ partitions of $S$ as shown above, then the number of ordered pairs from each of the partition will be $x_i\times x_i = x_i^2$. So,
\[\text{Total number of ordered pairs} = x_1^2 + x_2^2 + \cdots + x_n^2 = 2023\]
Case 1:
If $n=1$, then $x_1^2 = 2023$, but we know that a perfect square cannot end with $3$, so this case is not possible.
Case 2:
If $n=2$, then $x_1^2 + x_2^2 = 2023$. We know that any perfect square is congruent to $0$ (or) $1\pmod{4}$. So, the LHS, $x_1^2+x_2^2 \equiv 0\ (or)\ 1\ (or)\ 2\pmod{4}$, but the RHS, $2023\equiv 3\pmod{4}$, which is not possible.
Case 3:
If $n=3$, then $x_1^2 + x_2^2 + x_3^2 = 2023$. Going$\pmod{4}$ we see that each of $x_1^2,\ x_2^2,\ x_3^2 \equiv 1\pmod{4}$ since $2023\equiv 3\pmod{4}$ and hence they are odd numbers. Any square of an odd number is congruent to $1\pmod{8}$, since $(2k+1)^2 = 8\frac{k(k+1)}{2} + 1 = 8k'+1$, so the LHS, $x_1^2 + x_2^2 + x_3^2 \equiv 3\pmod{8}$, but the RHS, $2023\equiv7\pmod{8}$, which is a contradiction. Hence, this case is also not possible.
So, we conclude that for any such set $S,\ n\geq 4$ and hence one can select $4$ such numbers. Actually, there is a partition of $S$ possible with $n=4$, that is, $(9, 9, 30, 31)$ because $9^2+9^2+30^2+31^2 = 2023$.
Remark: In set theory, the partitions $S_x$ is called equivalence classes of $S$ since multiplying two numbers to get a perfect square is an equivalence relation defined on $S$, which in turn results in a partition of $S$. For further reading, refer to :
Problem 2
Suppose $a_0, \ldots, a_{100}$ are positive reals. Consider the following polynomial for each $k$ in $\{0,1, \ldots, 100\}$ :
\[a_{100+k} x^{100}+100 a_{99+k} x^{99}+a_{98+k} x^{98}+a_{97+k} x^{97}+\cdots+a_{2+k} x^2+a_{1+k} x+a_k,\]where indices are taken modulo $101$, i.e., $a_{100+i}=a_{i-1}$ for any $i$ in $\{1,2, \ldots, 100\}$. Show that it is impossible that each of these $101$ polynomials has all its roots real.
Solution :
Suppose say that all the roots are real for all the polynomials and $\alpha_{ij}$ represent the $i^{th}$ root of the $j^{th}$ polynomial. Then for each $j \in \{1, 2, \ldots, 101\}$,
\[\Rightarrow \frac{1}{\alpha_{1j}^2} + \frac{1}{\alpha_{2j}^2} + \cdots + \frac{1}{\alpha_{100j}^2} \geq 0\]
\[\Rightarrow \left(\frac{1}{\alpha_{1j}} + \frac{1}{\alpha_{2j}} + \cdots + \frac{1}{\alpha_{100j}}\right)^2 - \sum_{0<m<n}^{n\leq 100} \frac{2}{\alpha_{mj}\alpha_{nj}}\geq 0\]
\[\Rightarrow \left(\frac{\sum_{(i_1,i_2,\ldots,i_{99})\in \text{99 tuples of 1 to 100}}\alpha_{i_1j}\alpha_{i_2j}\cdots\alpha_{i_{99}j}}{\alpha_{1j}\alpha_{2j}\cdots\alpha_{100j}}\right)^2 - \frac{2\sum_{(i_1,i_2,\ldots,i_{98})\in \text{98 tuples of 1 to 100}}\alpha_{i_1j}\alpha_{i_2j}\cdots\alpha_{i_{98}j}}{\alpha_{1j}\alpha_{2j}\cdots\alpha_{100j}} \geq 0\]
So, by the Vieta's formula we get,
\[\Rightarrow \frac{\left(\frac{-a_{1+k}}{a_{100+k}}\right)^2}{\left(\frac{a_k}{a_{100+k}}\right)^2} - 2\frac{\left(\frac{a_{2+k}}{a_{100+k}}\right)}{\left(\frac{a_k}{a_{100+k}}\right)} \geq 0\]
\[\Rightarrow \frac{a_{k+1}}{a_k} \geq 2\left(\frac{a_{k+2}}{a_{k+1}}\right),\text{ for each }k\in\{0,1,2,\ldots,100\} \longrightarrow(1)\]
Define $b_i \in \mathbb{R_+}$ as, $b_i = \frac{a_i}{a_{i-1}}$, for each $i\in \{1,\ldots,102\}$, so obviously $b_1=b_{102}$, then from the equation $(1)$ we have,
\[b_i \leq \frac{b_{i-1}}{2},\text{ for each }i\in\{2,\ldots,102\},\text{ so we have,}\]
\[b_{102} \leq \frac{b_{101}}{2} \leq \frac{b_{100}}{2^2} \leq \frac{b_{99}}{2^3} \leq \cdots \leq \frac{b_{2}}{2^{100}} \leq \frac{b_{1}}{2^{101}} = \frac{b_{102}}{2^{101}}\]
\[\Rightarrow b_{102}\leq \frac{b_{102}}{2^{101}}\Rightarrow b_{102} \leq 0,\]
which is not possible as $b_i$'s $\in \mathbb{R_+}$. Hence, we arrive at a contradiction and so we conclude that all the roots of all the polynomials cannot be real.
Problem 3
Let $\mathbb{N}$ denote the set of all positive integers. Find all real numbers $c$ for which there exists a function $f: \mathbb{N} \rightarrow \mathbb{N}$ satisfying:
(a) for any $x, a \in \mathbb{N}$, the quantity $\frac{f(x+a)-f(x)}{a}$ is an integer if and only if $a=1$;
(b) for all $x \in \mathbb{N}$, we have $\mid f(x)-cx\mid <2023$.
Solution :
The only possible values of $c = k+\frac{1}{2},\ \forall k\in \mathbb{N_0}$. Here, $\mathbb{N_0}$ means the set of whole numbers. The proof is illustrated below,
Claim 1: For any integers $k \geq 1$ and $x,\ f\left(x+2^k\right)-f(x)$ is divisible by $2^{k-1}$ but not $2^k$.
Proof. We prove this via induction on $k$.
For $k=1$, the claim is trivial as $2^0$ divides any integer. Now assume the statement is true for some $k$, and hence $f\left(x+2^k\right)-f(x)=2^{k-1} y_1$ and $f\left((x+2^k)+2^k\right)-$ $f\left(x+2^k\right)=2^{k-1} y_2$ for some odd integers $y_1, y_2$. Adding these equations, we see that,
\[f\left(x+2^{k+1}\right)-f(x)=2^{k-1}\left(y_1+y_2\right)\]which is divisible by $2^k$ because $y_1+y_2$ is even. The fact that this is not divisible by $2^{k+1}$ follows from the condition (a) on $f$.
Now using the Claim 1, we see that for any $k \geq 1,\ f\left(1+2^k\right)=f(1)+2^{k-1}\left(2 y_k+1\right)$ for some integer $y_k$, so we get,
\[f\left(1+2^k\right)-c\left(1+2^k\right)=f(1)-c+2^k\left(y_k+\frac{1}{2}-c\right),\ \forall k\in \mathbb{N}\]
The quantity in the LHS is bounded above by 2023 and hence the RHS is also bounded above by 2023 for all values of $k$, but $f(1)-c$ is a constant with varying value of $k$, thus $2^k\left(y_k+\frac{1}{2}-c\right)$ is bounded above. But if this quantity is never zero, then we would have,
\[2^k\left|y_k+\frac{1}{2}-c\right|=2^{k-1}\left|2 y_k+1-2 c\right| \geq 2^{k-1},\ \forall k\in\mathbb{N}\]which contradicts the boundedness of $\mid f(x)-cx\mid$. Thus we must have $y_k+\frac{1}{2}-c=0$, for some $k \in \mathbb{N} \Rightarrow \{c\}=\frac{1}{2}$, where $\{x\}$ represents the fractional part of $x$.
Claim 2: If $\{c\}=\frac{1}{2}$ and $c>0$, then there exist function $f(x) = \lfloor cx\rfloor + 1$ that satisfies both conditions given in the question and if $c<0$, then there exist no function satisfying the given conditions
Proof. Since fractional part of $c>0$ is $\frac{1}{2}$, we assume that $c = k+\frac{1}{2},\ \forall k\in \mathbb{N_0}$. For any $x, a\in \mathbb{N}$,\[\frac{f(x+a)-f(x)}{a} = \frac{\lfloor c(x+a)\rfloor - \lfloor cx\rfloor}{a} = \frac{1}{a}\left(\left\lfloor kx+ka+\frac{x}{2}+\frac{a}{2}\right\rfloor - \left\lfloor kx+\frac{x}{2}\right\rfloor\right)= k + \frac{1}{a}\left(\left\lfloor \frac{x}{2}+\frac{a}{2}\right\rfloor - \left\lfloor \frac{x}{2}\right\rfloor\right)\]
In the above steps, we were able to take $kx$ and $ka$ out of the greatest integer function because they are integers. In general, $\lfloor x+n\rfloor = \lfloor x\rfloor+n$, where $n\in\mathbb{Z}$. So we have,\[\frac{f(x+a)-f(x)}{a} =k + \frac{1}{a}\left(\left\lfloor \frac{x}{2}+\frac{a}{2}\right\rfloor - \left\lfloor \frac{x}{2}\right\rfloor\right)\]Observe that, it is an integer for $a=1$. But for $a \geq 2$, we have,\[\left\lfloor\frac{x+a}{2}\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor \geq\left\lfloor\frac{x+2}{2}\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor=1\]If $a=2r$, then\[\left\lfloor\frac{x+a}{2}\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor=\left\lfloor\frac{x}{2}+r\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor=r<2r=a,\]and if $a=2r+1$ for $r \geq 1$, then\[\left\lfloor\frac{x+a}{2}\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor \leq\left\lfloor\frac{x+2r+2}{2}\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor=r+1<2r+1=a\]
So in either case, the quantity $\left\lfloor\frac{x+a}{2}\right\rfloor-\left\lfloor\frac{x}{2}\right\rfloor$ is strictly between 0 and $a$, and thus cannot be divisible by $a$. Thus condition (a) holds.
The condition (b) is trivially true because, $\mid f(x)-cx\mid = \lfloor cx\rfloor -cx + 1 = 1-\{cx\}\leq 1 < 2023$
Now coming to the case in which $c<0$, we see that $\mid f(x)-cx\mid$ can go arbitrarily large for a given negative value of $c$ because, given $c<0$, one can definitely choose a natural number $x>\frac{2023}{\mid c\mid}$, so that, $\mid f(x)+(-cx)\mid > 2023$, since $f(x)>0$ and so the second condition would not be satisfied for any $f(x)$.
So, we conclude from result of the Claim 1 that $\{c\} = \frac{1}{2}$ and from the Claim 2 that for all non-negative values of $c$, such that $\{c\}=\frac{1}{2}$, there exist a function $f(x)=\lfloor cx\rfloor + 1$ satisfying both the given conditions and there exist no function for negative values of $c$ that satisfies the given conditions, and hence proving the desired values of $c$.
Problem 4
Let $k \geq 1$ and $N>1$ be two integers. On a circle are placed $2N+1$ coins all showing heads. Calvin and Hobbes play the following game. Calvin starts and on his move can turn any coin from heads to tails. Hobbes on his move can turn at most one coin that is next to the coin that Calvin turned just now from tails to heads. Calvin wins if at any moment there are $k$ coins showing tails after Hobbes has made his move. Determine all values of $k$ for which Calvin wins the game.
Solution :
We claim that Calvin wins if $k \in \{1, 2, 3, \ldots, N+1\}$. First, let us prove the case in which Calvin wins the game and then we will prove the case in which he may not win.
Step 1:
Claim: In the start of the game, Calvin can form two adjacent tails after Hobbes has made his move.
Proof. Calvin starts the game by turning a coin, say $C_0$, from heads to tails. Now, Hobbes cannot make his move as there are no adjacent tails to it. Then, Calvin turns the next to next coin of $C_0$, say $C_1$, from heads to tails. Again, Hobbes cannot make his move because $C_0$ and $C_1$ cannot be adjacent as $N\geq 2$. Then, Calvin turns the coin between $C_0$ and $C_1$, say $C_2$, from heads to tails. Now, Hobbes have an option to turn $C_0$ (or) $C_1$ back to heads. But in any case, we get two adjacent tails after Hobbes has made his move, thus proving the claim.
By the above claim, assume that we have only two adjacent tails and Calvin is supposed to move now. Let the two adjacent tails be $T_1$ and $T_{N+1}$. Calvin turns the next to next coin of $T_1$ that is not adjacent to $T_{N+1}$, say $T_2$, from heads to tails. Now, Hobbes cannot make a move as there are no adjacent tails to $T_2$. Again, Calvin turns the next to next coin of $T_2$ from heads to tails until he reaches the coin $T_{N+1}$. Note that any move of Calvin after forming the adjacent tails $T_1$ and $T_{N+1}$ will not form anymore adjacent tails as the total number of coins is odd and consequently Hobbes cannot make a move. There are $2N-1$ coins except $T_1$ and $T_{N+1}$ and so there are $N-1$ more tails formed by this alternating tails and heads configuration due to Calvin's move. So, in total there are $N+1$ tails after the Hobbes move. Since the number of tails increases by one in the procedure after each of the Hobbes move (which was not possible anyways), for each $k \in \{1, 2, 3, \ldots, N+1\}$, Calvin wins the game by following the above procedure (obviously he cannot win for $k\geq 2$ if he turn the coins randomly). An example of the procedure is illustrated below for $N=3$ attaining $4=N+1$ tails,
Remark: The procedure has total $N+3$ moves and irrespective of value of $N$, Hobbes can make only one move which forms the first adjacent tails after his move.
Step 2:
Pair up the adjacent coins to form $N$ blocks of coin pairs, say $B_1, B_2, \ldots, B_N$, and a single coin, say $C_1$, as shown in the figure below for $N=3$,
Claim: There is a playing strategy for Hobbes that will not allow both coins of any block to show tails after each move of Hobbes.
Proof. Let us prove this claim by induction on the number of moves by Hobbes. Obviously, it is true for the first move of Hobbes, since by the time Calvin has turned only one coin to tails. Let us assume that the claim is true for "$(n-1)^{th}$" move of Hobbes, i.e., there is no block with both coins showing tails in it after $(n-1)^{th}$ move of Hobbes. Now after Calvin's $n^{th}$ move, there is at most one block with both coins showing tails as he can turn only one coin and if there is such a block after Calvin's move, say $B_i$, then the latest turned coin, say $C_0$, must be in the block $B_i$ and hence, Hobbes turns the adjacent coin of $C_0$ that is in the block $B_i$ from tails to heads which makes sure that there is no block with both coins showing tails after his $n^{th}$ move. Hence, by principle of induction, there is a playing strategy for Hobbes that will not allow both coins of any block to show tails after each move of Hobbes.
Claim: Calvin may not win the game if $k\geq N+2$.
Proof. Now we know that there are $N$ blocks and a coin in total and after each move of Hobbes there is at most one coin showing tails in each block by the above strategy and hence there is at most $N+1$ coins showing tails in total after Hobbes move with the above strategy and hence Calvin will not win the game if $k\geq N+2$ and if Hobbes adopts the above strategy.
Remark: If the total number of coins were even, say $2N$, then Calvin wins the game if $k\in \{1, 2, \ldots, N\}$, which can be easily proved using an argument similar to the above procedure.
Problem 5
Euler marks $n$ different points in the Euclidean plane. For each pair of marked points, Gauss writes down the number $\left\lfloor\log _2 d\right\rfloor$ where $d$ is the distance between the two points. Prove that Gauss writes down less than $2n$ distinct values.
Note: For any $d>0,\left\lfloor\log _2 d\right\rfloor$ is the unique integer $k$ such that $2^k \leq d<2^{k+1}$.
Solution :
We will prove that Gauss writes down at most $n-1$ distinct even numbers and $n-1$ distinct odd numbers and hence, in total at most $2n-2$ distinct numbers which is less than $2n$.
Definition:
Claim 1: Consider a simple graph $G$ with $m$ vertices, where $m\in\mathbb{N}$. If $G$ is connected with no cycle in it, then $G$ has exactly $m-1$ edges.
Proof. If $m=1$, then the claim is trivially true. For $m>1$, let the $m$ vertices be $x_1, x_2, \ldots, x_m$. Consider any vertex $x_i$ and an edge, say $E_1$, that is connecting it to $x_j$ for some $i, j\in\{1, 2, \ldots, m\}$ (since $G$ is connected, there must be such an edge). Consider the subgraph containing $x_i$ and $x_j$ and the edge $E_1$ to be $G_2$, which is a connected subgraph. For $i\geq2$, considering $G_i$ to be a connected subgraph of $G$ with $i$ vertices and $i-1$ edges, let us inductively define that $G_{i+1}$ is a union of the graph $G_i$ with a new edge $E_i$ that is connecting some vertex of $G_i$ to a vertex not in $G_i$, say $V_i$ and the vertex $V_i$ as shown below. Notice that $G_{i+1}$ is a connected graph because there exists such an edge $E_i$ (since $G$ is connected) and $G_i$ is also connected. So, by induction, the graph $G_m$ is connected with all the $m$ vertices and $m-1$ edges in it. Now, if there is any more edge that is in $G$ but not in $G_m$, then it must form a cycle in $G$ because there are would be two paths connecting the endpoints of this edge, one in $G_m$ and other is this edge, which contradicts our assumption in the claim. Hence, there are exactly $m-1$ edges in the graph $G$.
Claim 2: If $G$ is a simple graph with $m$ vertices, $m-1$ edges and no cycle in it, then $G$ is connected.
Proof. Let the graph $G$ have $t$ connected components in it. We know that any two connected components are each connected and disjoint so that there is no path connecting them, because they form a partition for both vertex and edge sets. Since each of the connected component is connected with no cycle in it, the number of edges in it is exactly one less than number of vertices in it. So, the total number of edges in $G$ will be $m-t$, because components partition all the edges. Hence, $t=1$ as there are $m-1$ edges. So, there must be only one connected component, which means that $G$ is connected.
Claim 3: If $G$ is a simple graph with $m$ vertices and at least $m$ edges, then $G$ must have a cycle.
Proof. Assume that there is no cycle in $G$. Now, remove few edges from the graph to get a subgraph $G_0$ with the same $m$ vertices and $m-1$ edges and no cycle in it. By the Claim 2, $G_0$ should be connected. Now, if you insert back any one of the removed edge, say $E$, into $G_0$, it forms a cycle because there are now two paths connecting the endpoints of $E$, one in $G_0$ and other is $E$, which is a contradiction to our assumption that there was no cycle in $G$. Hence, $G$ must have a cycle.
Now assume that Gauss writes at least $n$ distinct even integers and we will derive a contradiction. For every distinct even integer that Gauss writes down, construct an edge between the two points whose logarithmic distance corresponds to this value. Since there are at least $n$ distinct values, there are at least $n$ edges constructed with distinct even numbers, which forms a simple graph with vertices as the $n$ points.
Thus, we have a graph with $n$ vertices and $n$ edges and so by the Claim 3, there must be a cycle in the graph. Suppose say that the distinct even integers are $2k_1, 2k_2, 2k_3, \ldots, 2k_r$, where $r\in\mathbb{N}$ is the cycle length. Without loss of generality, let $2k_r$ be the largest and let $2k_i$ be the second largest integer. Then sum of distances of the edges corresponding to the logarithmic values $2k_1, 2k_2, \ldots, 2k_{r-1}$ is less than,
\[2^{2k_1+1}+2^{2k_2+1}+\cdots+2^{2k_{r-1}+1} \leq 2^{2k_i+1}\left(1+2^{-2}+2^{-4}+\cdots+2^{-2(r-2)}\right)\]
since $k_i$ is the second largest and the integers are distinct. So we get,
\[2^{2k_i+1}\left(1+2^{-2}+2^{-4}+\cdots+2^{-2(r-2)}\right) = 2^{2k_i+1}\left(\frac{1-\left(2^{-2}\right)^{r-1}}{1-2^{-2}}\right) = \frac{4}{3}2^{2k_i+1}\left(1-2^{-(2r-2)}\right)\]
\[\Rightarrow 2^{2k_1+1}+2^{2k_2+1}+\cdots+2^{2k_{r-1}+1} \leq \frac{4}{3}2^{2k_i+1}\left(1-2^{-(2r-2)}\right) < \frac{4}{3}2^{2k_i+1} < 2^{2k_i+2} \leq 2^{2k_r}\]
Triangle Inequality states that for any $r\geq 3$ points in the Euclidean plane, say $x_1, x_2, \ldots, x_r$, we have, $d(x_1, x_2) + d(x_2, x_3) + d(x_3, x_4) + \cdots + d(x_{r-1}, x_r) \geq d(x_r, x_1)$, which is obtained by addition of all the triangle inequalities in the triangles $(x_1, x_2, x_3)\ ;\ (x_1, x_3, x_4)\ ;\ (x_1, x_4, x_5)\ ;\ \ldots\ ;\ (x_1, x_{r-1}, x_r)$. But the above $r$ points violate this inequality as the largest distance is greater than the sum of other $r-1$ distances. Hence, we get a contradiction.
So, Gauss writes at most $n-1$ distinct even integers and by a similar argument, he writes at most $n-1$ distinct odd integers and hence, Gauss writes at most $2n-2$ distinct integers in total which is less than $2n$.
Problem 6
Euclid has a tool called cyclos which allows him to do the following:
Show that given two marked points, Euclid can draw a circle centered at one of them and passing through the other, using only the cyclos.
Solution :
For any given non-collinear points $X, Y, Z,$ let $\left(XY\right)$ represent the circle drawn with $XY$ as the diameter, $\left(XYZ\right)$ represent the circumcircle of $\triangle XYZ$ drawn using the cyclos.
Claim 1: Given any 3 non-collinear points that forms a non-right angled triangle, one can draw the nine-point circle of this triangle using only the cyclos.
Proof. Let $A, B, C$ be the three non-collinear points, then the intersection of $(AB)$ and $(AC)$ is the foot of perpendicular from $A$ to $BC$, say $P_A$. Similarly one can construct all the foot of perpendiculars, $P_B, P_C$. The points $P_A, P_B, P_C$ must be distinct as $\triangle ABC$ is non-right angled triangle. Now the circle $\left(P_AP_BP_C\right)$ is the nine-point circle of $\triangle ABC$ as it is the unique circle passing through all the foot of perpendiculars.
Claim 2: Given two points in the plane, one can mark its mid-point using only the cyclos.
Proof. Let $A, B$ be the two points, then draw the circle $(AB)$. Choose a new point $X$ on the circumference of $(AB)$. Mark the other intersection of $(XA)$ and $(XB)$ as $D$, which is the foot of perpendicular from $X$ to $\overline{AB}$. Mark the intersections of $(AD)$ and $(XD)$ to be $E$ and $(BD)$ and $(XD)$ to be $F$, which are the feet of perpendiculars from $D$ to $XA$ and $XB$ respectively. Since, $\angle AED = \angle BFD = 90^{\circ}$ and $D$ lies inside the segment $\overline{AB}\Rightarrow \angle AEB$ and $\angle AFB >90^{\circ}$, i.e., obtuse and hence $\triangle AEB$ and $\triangle AFB$ are non-right angled triangles and so we can construct the nine-point circles of $\triangle AEB$ and $\triangle AFB$ by the Claim 1. Observe that $X$ is the foot of perpendiculars from $A$ to $BF$ and $B$ to $AE$, so both the nine-point circles must pass through $X$ and also they both must pass through the midpoint of $\overline{AB}$ by definition and hence we mark the other intersection point of the two nine-point circles to get the midpoint of $\overline{AB}$, say $M$, which is illustrated in the diagram below,
Remark: Dotted red circles represent the nine-point circles of $\triangle AEB$ and $\triangle AFB$. The two nine-point circles are different, since the feet of perpendiculars from $E$ and $F$ to $AB$ are different and each of them do not lie on the other nine-point circle. And two different circles intersect at most at two points and hence we can uniquely mark the midpoint of $\overline{AB}$ without any dilemma, since the intersection point $X$ is already marked.
Construction:
Suppose say that the two marked points as per the question to be $A$ and $B$. Consider point $C$ as the reflection of $B$ with respect to the point $A$, so that $A,B,C$ are collinear with $AC=AB$, but you need not mark $C$. Mark a new point $Y$ on the circumference of $(AB)$. Mark the intersection of $(YA)$ and $(YB)$ to be $U$, which is the foot of perpendicular from $Y$ to $AB$. By the Claim 2, we can mark the midpoint of $\overline{YB}$ as $W$ using only the cyclos. Now, construct $(AUW)$ and mark the other intersection of $(AUW)$ and $(YB)$ to be $S$. Note that $(AUW)$ is the nine-point circle of $\triangle CYB$ and thus feet of perpendiculars from $Y$ to $CB$ (which is $U$) and $B$ to $CY$ lie on both $(AUW)$ and $(YB)$. So, other intersection $S$ is the foot of the perpendicular from $B$ to $CY \Rightarrow \angle CSB=90^{\circ}$. Observe that $A$ is the midpoint of hypotenuse, which is the circumcenter of $\triangle CSB \Rightarrow AB = AS$.
Repeat the same procedure by marking a new point $Z$ on the circumference of $(AB)$ to obtain the foot of perpendicular from $B$ to $CZ$, say $T$, so that $AB=AT$. Most probably, $S$ and $T$ will be distinct because $CY$ and $CZ$ cannot intersect at more than 1 point. But it might happen that $C, Y, Z$ are collinear, in which case the lines $CY$ and $CZ$ coincide and so the points $S$ and $T$ coincide. In that case, we take some other new point $Z'$ on the circumference of $(AB)$ and repeat the procedure to obtain a new point $T'$, which must be different from $S$ because now $CY$ and $CZ'$ are two different lines.
Now, Construct $(BST)$ using cyclos, which is the required circle passing through $B$ and centered at $A$ because $AB = AS = AT$ and there is such a unique point which should be the circumcenter of $\triangle BST$. The final construction diagram is provided below with dotted red circle as the required circle,
Remark: This proves that the cyclos can perform everything that a compass can perform in constructions because now cyclos can construct a circle passing through a given point centered at a given point.
