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

Question

PROBLEM STATEMENT :

Suppose there are $160$ pigeons and $ n$ holes. The first pigeon flies to the $1st$ hole, the second pigeon flies to the $4th$ hole, and so on, such that the $i^{th}$ pigeon flies to the $$( i^2 \ mod \ n )^{th} \ hole. $$ Find the minimum value of $n$ such that there is at most one pigeon per hole .

MY WORKING:

This is how I could interpret the problem:

We have to find minimum n such that the following equality holds

$$i^2 \equiv k_{i}\pmod n$$ Where $i \in {1,2,...,160} $, and $k_{i} \equiv k_{j} $ if and only if $i=j$.

Simple analysis shows that $n≥160×2=320 $. I further checked for $n=320,321,...$, but couldn't find a valid n.

After spending some time, I came to the conclusion that $p=n$ satisfies the problem condition if and only if there exists no integral solution to the following equation : $$p+ x^2=y^2.$$

It seems that I am using more of number theory approaches to a combinatorics problem, and thus ending up with more complications.

Is my approach correct? How should I move further? Any hints or solutions will be much appreciated.

Thanks.

Answer 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$.

Answer 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. ;)

Answer 3

More generally, consider $m\ge 5$ pigeons and $n$ boxes. Clearly, we must have $n\ge m$. Let’s classify some $n$ that work and later pick the smallest such $n$.

If $n$ is a prime, then either $n\le 2m-1$ and we see that $\frac{n+1}2$ and $\frac{n-1}2$ are in the same box; or $n>m+(m+1)$ and hence none of $x\pm y$ can be $\ge n$ nor a multiple of $n$.

$n$ prime works iff $n>2m+1$. Note that by Bertrand, a prime $n$ with $2m+1<n<4m+2$ exists.

If $n=2p$ with $p$ prime, either $p<m$ so that $p\pm1$ are in the Sam box; or $p\ge m$ and $2p\mid (x+y)(x-y)$ implies that $x,y$ have same parity and one factor is a multiple of $p$, hence $x+y\ge 2p$, which is impossible.

$n=2p$ works iff $p\ge m$. Note that by Bertrand, such $n$ with $2m\le n=2p\le4m-2$ exists.

If $n=ab$ where $1<a\le b$ and $a,b$ are of same parity, and $a+b\le 2m$, note that $\frac{a\pm b}2$ are in the same box.

Such $n$ works at most when $a+b>2m$. But then $n\ge 2\cdot(2m-1)=4m-2$, which is beaten by the $2p$ case above.

If $n=2ab$ where $3\le a\le b$ and $a,b$ are odd, then $a\pm b$ are in the same box. Hence such $n$ works at most if $a+b>m$. But then $n\ge 2\cdot3\cdot(m-2)=6m-12\ge 4m-2$, which is beaten by the $2p$ case.

We conclude that the smallest $n$ is either the smallest prime $>2m+1$ or twice the smallest prime $\ge m$, whichever is smaller.