I'm currently working through a paper related to my bachelors thesis and I'm stuck at a point where the author mentions the following result as "a standard application of the pigeonhole principle".
Let $N\in\mathbb{N}$ and $q\in \{1,\dots,N-1\}$. Let further $A \subseteq \{1,\dots,N-1\}$ such that $|A| = q$.
Then there exists a $d \in \mathbb{Z}_N$ such that:
$$d \in \{ -N^{q/{(q+1)}}, -N^{q/{(q+1)}}+1, \dots, N^{q/{(q+1)}} \},$$
$$ad \in \{ -N^{q/{(q+1)}}, -N^{q/{(q+1)}}+1, \dots, N^{q/{(q+1)}} \} \ \forall a \in A$$
(or equivalently $ |d| \leq N^{q/{(q+1)}}$, $|ad|\leq N^{q/{(q+1)}} \forall a \in A$.)
I would be very grateful for any pointers on how one can use the pigeonhole principle to prove this.
Thanks!
This is a perfect example of a type of result that's both "standard" (to people who know the game) and pretty opaque (to people who haven't been initiated yet). I'm going to ignore the fact that expressions like $N^{q/(q+1)}$ aren't integers, for the purposes of exposition.
Set $t=N^{1/(q+1)}$. Given $A=\{a_1,\dots,a_q\}$, for each $k\in\{0,1,\dots,t^q\}$ consider the point $(ka_1,\dots,ka_q)\in(\Bbb Z_N)^q$. Break $(\Bbb Z_N)^q$ up into $t^q$ "subcubes of side length $t^q$": each subcube looks like a direct product of intervals $I_1\times \cdots \times I_q$, where $I_j = \{ k_j t^q, \dots, (k_j+1)t^q-1 \}$ for some $0\le k_j<t$.
There are $t^q$ subcubes and $t^q+1$ points of the form $(ka_1,\dots,ka_q)$, so some subcube must contain two such points, say $(ka_1,\dots,ka_q)$ and $(k'a_1,\dots,k'a_q)$. Now set $d=k-k'$, and check that all of your wishes have come true....