Determine all integer pairs $(m, n)$ such that $\frac{n^{3}+1}{m n-1}$ is an integer.
Another International Olympiad exercise (1994/4). The first thing to notice is that $n$ and $m$ play symmetric roles, because if $mn-1$ divides $n^3+1$, it also divides $m^3(n^3+1)$, but it also divides $m^3n^3-1$, so it divides the difference $m^3+1$. Therefore, we can assume that $n \leq m$. The second important idea is that $n^3+1 \equiv 1$ (mod $n$), $mn-1 \equiv -1$ (mod $n$), so the quotient must be congruent to -1 modulo $n$, i.e., of the form $kn-1$. Since $mn-1 \geq n^2-1$, we must have: $(kn-1)(n^2-1) \leq n^3+1$, which factors into: $(k-1)(n^3-n) \leq n^2+n$, or: $(k-1)(n-1) \leq 1$. Therefore, either $n=1$, or $k=1$, or $n=k=2$.

$n=1$ gives: $(m-1)$ divides 2, so $m=2$ or $m=3$.

$k=1$ gives: $(n-1)(nm-1)=n^3+1$ or: $(n-1)m=n^2+1$, or:
$m=n+1+\frac{2}{n-1}$ which is an integer for $n=2$ and $n=3$. In both cases, $m=5$.

$n=k=2$ gives $nm-1=\frac{n^3+1}{kn-1}=3$, so $m=2$.

Thus, we have nine solutions: $(1,2),(1,3),(2,1),(3,1),(2,5),(3,5),(5,2),(5,3),(2,2)$.

## Group D: Combinatorics

## Saturday, 23rd morning: Guillaume Conchon-Kerjan

## Introduction

Here we propose a number of rather difficult exercises (including combinatorial geometry, but not only) using relatively elementary tools.

## Exercises

## Appetizer