Minimum number of holes such that each of 160 pigeons fly in different hole with a condition

Solution 1:

To satisfy the problem requirement, the following condition is necessary and sufficient: for every pair of distinct integers $x$ and $y$ with $1 \leq x, y \leq 160$, we have $$n \not \mid x^2 - y^2.$$

We will proceed by finding the smallest possible $n$ satisfying the above condition.

As you mentioned, $n$ must be at least $320$. Indeed, if $n \leq 319$, then we could set $x = n - 160$ and $y = 160$. We would have $1 \leq x < y \leq 160$ and $$x^2 - y^2 = (x+y)(x-y) = n(n-320)$$ is clearly divisible by $n$.

We now check the next few numbers. We utilise the factorisation $x^2 - y^2 = (x+y)(x-y)$ repeatedly.

• For $n = 320 = 80 \times 4$, we could set $x = 42$ and $y = 38$.
• For $n = 321 = 107 \times 3$, we could set $x = 55$ and $y = 52$.
• For $n = 322 = 46 \times 7$, we could set $x = 30$ and $y = 16$. (Note that $x^2 - y^2 = 2n$ in this case.)
• For $n = 323 = 19 \times 17$, we could set $x = 18$ and $y = 1$.
• For $n = 324 = 54 \times 6$, we could set $x = 30$ and $y = 24$.
• For $n = 325 = 65 \times 5$, we could set $x = 35$ and $y = 30$.

Let us now look at $n = 326$. We will prove that the condition is satisfied when $n = 326$ using contradiction.

Suppose $326 | (x+y)(x-y)$ for some distinct integers $x$ and $y$ with $1 \leq x, y \leq 160$. Then at least one of $(x+y)$ and $(x-y)$ must be divisible by $163$. (Notice that $163$ is one of the prime factors of $326$.)

We cannot have $163 | (x-y)$. (Why? Consider the fact that $0 < |x-y| \leq 159 < 163$.) So, we know that $163 | (x+y)$, i.e., $x+y$ is a (positive) multiple of $163$. But $x+y$ obviously cannot be larger than $159 + 160 = 319$, so $x+y$ can only be $163$.

Since $x + y = 163$, we know $x+y$ is odd. Observe that $x+y$ and $x-y$ must have the same parity for any integers $x$ and $y$. (Why?) Hence, $x-y$ is odd too. But this means $(x+y)(x-y)$ is odd, which implies it cannot be divisible by the even number $326$. This is a contradiction.

So, the smallest possible number of holes is $326$.

Solution 2:

It looks like you're on the right track.

Consider $y^2-x^2=pk$, where $x,y$ are pigeon numbers, $p$ is the number of holes, and $k$ is an integer. Now factorise the LHS. Given the domain of $x,y$, what conditions does that place on $p$?

Here's a live Python script you can use to test various $p$. But maybe don't look at it until you've figured out the solution. ;)