IMO 2012 Problem 3 part 2

The solution at the bottom is the official one. Just so that in the future I know that I once understand it. I do not know how to come up with the idea.

================================

The liar's guessing game is a game played between two players \(A\) and \(B\) The rules of the game depend on two positive integers \(k\) and \(n\) which are known to both players.

At the start of the game \(A\) chooses integers \(x\) and \(N\) with \(1 \le x \le N\). Player \(A\) keeps \(x\) secret, and truthfully tells \(N\) to player \(B\). Player \(B\) now tries to obtain information about \(x\) by asking player \(A\) questions as follows: each question consists of \(B\) specifying an arbitrary set \(S\) of positive integers (possibly one specified in some previous question), and asking \(A\) whether \(x\) belongs to \(S\). Player \(B\) may ask as many questions as he wishes. After each question, player \(A\) must immediately answer it with yes or no, but is allowed to lie as many times as she wants; the only restriction is that, among any \(k+1\) consecutive answers, at least one answer must be truthful.

After \(B\) has asked as many questions as he wants, he must specify a set \(X\) of at most \(n\) positive integers. If \(x\) belongs to \(X\) then \(B\) wins; otherwise, he loses. Prove that:

1. If \(n \ge 2^k,\) then \(B\) can guarantee a win.
2. For all sufficiently large \(k\) there exists an integer \(n \ge (1.99)^k\) such that \(B\) cannot guarantee a win.

Proposed by David Arthur, Canada

============================================

$A$ makes $N=n$. For every $i\in[n]$, let $m_i$ be the number of consecutive answers that is a lie if $x=i$. $A$'s strategy is to minimize 

$$y=\lambda^{m_1}+\lambda^{m_2}+\dots+\lambda^{m_n}$$

where $\lambda>1$ is to be determined later.

Our goal is to show that $y\le z<\lambda^{k+1}$ for some $z>0$, so that every $m_i<k+1$. Note that together with $z\ge n$, we can prove that $y\le z$ inductively if $$z\lambda/2+n/2\le z,\text{ or }\frac{n}{2-\lambda}\le z.$$

Hence we further require that $\lambda<2$ and $$\frac{n}{2-\lambda}<\lambda^{k+1}.$$

To sum it up, we hope that for sufficiently large $k$ there is an integer $n$ such that

$$1.99^k\le n<(2-\lambda)\lambda^{k+1}.$$

This is achievable for every $\lambda\in(1.99,2)$.

IMO 2024 Problem 1

Determine all real numbers $\alpha$ such that, for every positive integer $n,$ the integer

$$\lfloor\alpha\rfloor +\lfloor 2\alpha\rfloor +\cdots +\lfloor n\alpha\rfloor$$

is a multiple of $n.$ (Note that $\lfloor z\rfloor$ denotes the greatest integer less than or equal to $z.$ For example, $\lfloor -\pi\rfloor =-4$ and $\lfloor 2\rfloor= \lfloor 2.9\rfloor =2.$)

=====================================

$\alpha$ qualifies $\Leftrightarrow$ it is an even integer. It suffices to restrict $\alpha$ to $[0,2)$ because of periodicity. No odd integer $\alpha$ works because $3\alpha$ is not even.

For $\alpha\in[0,1)$, by setting $n=2$ we get $\alpha\in[0, 0.5)$. When $n=3$, it is further restricted to $\alpha\in[0, 1/3)$. We keep going on, where each time we find ourselves further requiring $\alpha\in[0,1/n)$. Therefore we have $\alpha=0$.

For $\alpha\in(1,2)$, by setting $n=2$ we get $\alpha\in[1.5,2)$. When $n=3$, it is further restricted to $\alpha\in[5/3,2)$. We keep going on, where each time we find ourselves further requiring $\alpha\in[2-1/n,2)$ because $(n-1)^2+2n-1=n^2$. Therefore $\alpha$ does not exist and we conclude that $\alpha$ must be an even integer.

IMO 2025 Problem 5

Alice and Bazza are playing the inekoalaty game, a two‑player game whose rules depend on a positive real number $\lambda$ which is known to both players.  On the $n$th turn of the game (starting with $n=1$) the following happens:

-If $n$ is odd, Alice chooses a nonnegative real number $x_n$ such that

$$x_1 + x_2 + \cdots + x_n \le \lambda n$$

-If $n$ is even, Bazza chooses a nonnegative real number $x_n$ such that

$$x_1^2 + x_2^2 + \cdots + x_n^2 \le n$$

If a player cannot choose a suitable $x_n$, the game ends and the other player wins.  If the game goes on forever, neither player wins.  All chosen numbers are known to both players.

Determine all values of $\lambda$ for which Alice has a winning strategy and all those for which Bazza has a winning strategy.

===========================================

For $\lambda>1/\sqrt{2}$, Alice wins; for $\lambda<1/\sqrt{2}$, Bazza wins; otherwise it is a tie if they both play optimally.

Bazza's strategy is to choose $x_n$ such that $x^2_{n-1}+x^2_n=2$ whenever possible.

If $\lambda\ge1/\sqrt{2}$, Alice keeps choosing $x_n=0$. The best Bazza can do to maximize the sum is to follow his strategy by choosing $x_n=\sqrt{2}$. After $n=2k$ rounds, Alice can choose at least $y=(n+1)\lambda-n/\sqrt{2}=\lambda+n(\lambda-1/\sqrt{2})\ge0$. Thus Alice does not lose. When $\lambda>1/\sqrt{2}$, $y^2>n+2$ for sufficiently large $n$. Hence Alice wins by switching from $0$ to $y$.

If $\lambda\le1/\sqrt{2}$, Bazza follows his strategy. The sum after Bazza's turn is at least $n/\sqrt{2}$, so Alice's choice cannot exceed $$y=(n+1)\lambda-n/\sqrt{2}=n(\lambda-1/\sqrt{2})+\lambda\le\lambda\le1/\sqrt{2}<\sqrt{2}.$$ Thus inductively Bazza can always follow his strategy and does not lose. If $\lambda<1/\sqrt{2}$ then $y<0$ for sufficiently large $n$, i.e., Alice cannot choose a suitable $x_n$ and Bazza wins.

IMO 2025 Problem 1

A line in the plane is called $sunny$ if it is not parallel to any of the $x$–axis, the $y$–axis, or the line $x+y=0$.

Let $n\ge3$ be a given integer.  Determine all nonnegative integers $k$ such that there exist $n$ distinct lines in the plane satisfying both of the following:

-for all positive integers $a$ and $b$ with $a+b\le n+1$, the point $(a,b)$ lies on at least one of the lines; and

-exactly $k$ of the $n$ lines are sunny.

========================================

We claim that $k=0,1$, or $3$. For $n=3$ it is easy to check, also for $n>3$ we know that any $k\in\{0,1,3\}$ suffices. We show that for $n>3$ one of the $n$ lines must be $x+y=n,x=1$, or $y=1$, and thus the problem is reduced to $n-1$. Suppose that no line is $x+y=n,x=1$, or $y=1$. Let $A=\{(1,y):y\in[n]\}, B=\{(x,1):x\in[n]\}$, and $C=\{(x,y):x+y=n,x,y\in\mathbb{N}\}$. Each of the set has size $n$, so every $m$ lines must contain $m$ points from each set for any $m\in[n]$. Fix distinct integers $x_1,x_2\in[2,n-1]$. The point $(x_1,1)$ must lie on a line $\ell_1$ that goes through $(1,n)$, and so must point $(x_2,1)$ on line $\ell_2$. Hence the lines $\ell_1$ and $\ell_2$ do not contain two points from $A$ nor two points from $C$, a contradiction.