IMO 1983 Problem 5

I knew this construction, so it's not by me.

Is it possible to choose $1983$ distinct positive integers, all less than or equal to $10^5$, no three of which are consecutive terms of an arithmetic progression?

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

Yes. Consider all natural numbers no more than $11$ digits in base $3$ representation without digits $2$. The largest is $$1+3+\dots+3^{10}<10^5,$$and there are $2^{11}>1983$ of them.

IMO 1989 Problem 6

A more elegant solution not from me is at the bottom.

A permutation $ \{x_1, x_2, \ldots, x_{2n}\}$ of the set $ \{1,2, \ldots, 2n\}$ where $ n$ is a positive integer, is said to have property $ T$ if $ |x_i-x_{i+1}|=n$ for at least one $ i$ in $ \{1,2, \ldots, 2n-1\}.$ Show that, for each $ n$, there are more permutations with property $ T$ than without.

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

Proof #1

We say that a pair of numbers are twins if they differ by $n$. Let $a_{2n,2k}$ be the number of permutations with at most a pair of neighboring twins such that the number of elements separated by them differ by $2k$. So $a_{2n,2n}$ is the number of permutations without $T$. For $k\notin\{n,-n\}$ we have $$a_{2n,2k}=a_{2n,2n}+2n\cdot a_{2n-2,2k}.$$ Moreover $$a_{2n,2n}=2n\left(a_{2n-2,2n-2}+a_{2n-2,2n-4}+\dots+a_{2n-2,4-2n}\right).$$ With some manipulation we get $$a_{2n,2n}=2n\left((2n-1)a_{2n-2,2n-2}+(2n-2)a_{2n-4,2n-4}\right).$$ Let $f(2n):=a_{2n,2n}/(2n)!$, then $$f(2n)=f(2n-2)+\frac{f(2n-4)}{(2n-1)(2n-3)}\le f(2n-2)+\frac{1}{2}(\frac{1}{2n-3}-\frac{1}{2n-1}).$$ Since $f(4)=1/3$, for $2n\ge6$ we have $$f(2n)\le \frac{1}{3}+\frac{1}{2}\left(\frac{1}{3}-\frac{1}{5}+\frac{1}{5}-\frac{1}{7}+\dots\right)<\frac{1}{2}.$$

Proof #2

Let $(x_1,\dots,x_{2n})$ be a permutation without $T$ and $x_k$ be the twin of $x_1$ where $k>2$, then $$f(x_1,\dots,x_{2n})=(x_2,\dots,x_{k-1},x_1,x_k,\dots,x_{2n})$$ has $T$. The mapping $f$ is injective but not surjective, so the inequality follows.

IMO 1989 Problem 1

I got a weird construction.

Prove that the set $ \{1,2, \ldots, 1989\}$ can be partitioned into disjoint subsets $A_1,A_2,\dots,A_{117}$ such that

i.) each $ A_i$ contains $17$ elements

ii.) the sum of all the elements in each $ A_i$ is the same.

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

Proof

To simplify notations, we place numbers in a matrix $A$ whose columns are subsets.

Step 1: reduce $[1989]$ to $[117\cdot3]=[351]$, because we could then extend $A$ vertically to include $$\begin{pmatrix}3\cdot117+1 & 3\cdot117+2 & \dots & 4\cdot117\\ 5\cdot117 & 5\cdot 117-1&\dots&4\cdot117+1\\5\cdot117+1 & 5\cdot117+2 & \dots & 6\cdot117\\ 7\cdot117 & 7\cdot 117-1&\dots&6\cdot117+1\\ \vdots & \vdots & \ddots & \vdots \\ 15\cdot117+1 & 15\cdot117+2 & \dots & 16\cdot117\\ 17\cdot117 & 17\cdot 117-1&\dots&16\cdot117+1\end{pmatrix}.$$

Step 2: shift $[351]$ to $\{0,\pm1,\dots,\pm175\}$.

Step 3: make the first $88$ columns $$\begin{pmatrix}-175 & -174 & \dots & -88 \\ 87 & 85 & \dots & -87 \\ 88 & 89 & \dots & 175\\ \end{pmatrix}$$ and leaves $\{0,\pm2,\dots,\pm86\}$, or equivalently $\{0,\pm1,\dots,\pm43\}$.

Step 4: make the next $22$ columns $$2\begin{pmatrix}-43 & -42 & \dots & -22 \\ 21 & 19 & \dots & -21 \\ 22 & 23 & \dots & 43\\ \end{pmatrix}$$ and leaves $\{0,\pm2,\dots,\pm20\}$, or equivalently $\{0,\pm1,\dots,\pm10\}$.

Step 5: make the next $4$ columns $$4\begin{pmatrix}-10 & -9 & -8 & -7 \\ 3 & 1 & -1 & -3 \\ 7 & 8 & 9 & 10\\ \end{pmatrix}$$ and leaves $\{0,\pm2,\pm4,\pm5,\pm6\}$.

Step 6: make the lat $3$ columns $$4\begin{pmatrix}-2 & 2 & 5 \\ -4 & 4 & 0 \\ 6 & -6 & -5\\ \end{pmatrix}$$ and we are done.

IMO 1986 Problem 3

The problem is less interesting once we set out to find a quantity that strictly increases or decreases while keeping something else a constant. It just felt more like an algebraic problem.

To each vertex of a regular pentagon an integer is assigned, so that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers $x,y,z$ respectively, and $y<0$, then the following operation is allowed: $x,y,z$ are replaced by $x+y,-y,z+y$ respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to an end after a finite number of steps.

Solution

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

Yes, it does.

Let the numbers be $a_1,\dots,a_5$, and define $a_6:=a_1$. It could be checked that when we operate on $a_j$, the total sum does not change while the quantity $$J(a_1,\dots,a_5):=\sum_{i=1}^5a_i^2+(a_i+a_{i+1})^2$$ changes by $$2a_j(a_1+\dots+a_5)<0.$$ Since $J(a_1,\dots,a_5)$ is nonnegative, the process necessarily terminates after any finite number of steps. The statement holds even when the numbers are not integral.

IMO 1988 Problem 2

Let $ n$ be a positive integer. Let $ A_1, A_2, \ldots, A_{2n+1}$ be sets having $2n$ elements each such that any two of them have exactly one element in common while every element of their union belongs to at least two of the given sets. For which $n$ can one assign to every element of the union one of the numbers 0 and 1 in such a manner that each of the sets has exactly $n$ zeros?

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

Let the elements be $1,2,\dots$, and let $j$ be in $m_j\ge2$ sets. Double count $(A_i,j)$ where $j\in A_i$ and we have $$2n(2n+1)=\sum_j m_j.$$

Double count $(A_i,A_k,j)$ where $j\in A_i\cap A_k$ and we have

$$\binom{2n+1}{2}=\sum_j\binom{m_j}{2},$$ or $$2n(2n+1)=\sum_j m_j(m_j-1).$$

Since $m_j-1\ge1$, we see that $m_j=2$ for every $j$ in the union of all sets. Equivalently, we associate each number the pair of sets that it belongs to. Let $f(j)\in\{0,1\}$ be the assignment.

Double count $(A_i, j)$ where $j\in A_i$ and $f(j)=1$ we get $$n(2n+1)=2\big|\left\{j:f(j)=1\right\}\big|.$$Hence $n$ must be even. We set

$$f(A_i\cap A_k)=\begin{cases}1&\big|(i-k\bmod 2n+1)\big|\le \frac{n}{2},\\0&\text{otherwise}.\end{cases}$$Intuitively, we arrange $A_1,\dots,A_{2n+1}$ on a circle and let $f(j)=1$ if and only if one of the arcs between the unique pair $(A_i,A_k)$ of sets that $j$ belongs to has less than $\frac{n}{2}$ other sets.

IMO 1985 Problem 2

Let $n$ and $k$ be relatively prime positive integers with $k<n$. Each number in the set $M=\{1,2,3,\ldots,n-1\}$ is colored either blue or white. For each $i$ in $M$, both $i$ and $n-i$ have the same color. For each $i\ne k$ in $M$ both $i$ and $|i-k|$ have the same color. Prove that all numbers in $M$ must have the same color.

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

Proof

It suffices to work on $\mathbb{Z}_k$, where $x$ and $-x$ have the same color, and $x$ and $y$ have the same color if $x+y\equiv n(\bmod k)$. We can then reduce $(n,k)$ to $(k, n\bmod k)$, and the latter are relatively prime. Thus we keep reducing until the smaller number is $1$, where it is clear that all numbers have the same color.

From Tutte's theorem to Hall's marriage theorem

Let $G$ be an $X,Y$-bigraph, and $|S|<o(G-S)$ for some $S\subseteq V(G)$. We aim to show that $|N(X')|<|X'|$ for some $X'\subseteq X$. This essentially proves Hall's marriage theorem using Tutte's theorem.

Let $X_0=S\cap X$ and $Y_0=S\cap Y$. Every odd component of $G-S$ has distinct sizes in $X$ and $Y$, so suppose that $G-S$ has $p$ odd components whose intersections with $X$ is larger than with $Y$, and $q$ odd components whose intersections with $X$ is smaller than with $Y$. Without loss of generality say $p>|Y_0|$. Let these $p$ odd components intersect with $X$ and $Y$ at $X_1,\dots,X_p$ and $Y_1,\dots,Y_p$, respectively. Define $$X'=X_1\cup\dots\cup X_p.$$ Then $$N(X')\subseteq Y_0\cup Y_1\cup\dots Y_p=Y'.$$ We have $$|X'|-|N(X')|\ge|X'|-|Y'|=|X_1|-|Y_1|+\dots+|X_p|-|Y_p|-|Y_0|\ge p-|Y_0|>0.$$