# Dirichlet Principle

• Jun 6th 2011, 07:17 AM
seit
Dirichlet Principle
How many pairs of integers (a,b) are necessary to make sure that for two of them, say $({a_1},{b_1})$ and $({a_2},{b_2})$ it is the case that ${a_1}$ mod 5 = ${a_2}$ mod 5 and ${b_1}$ mod 5 = ${b_2}$ mod 5?
• Jun 6th 2011, 08:35 AM
emakarov
OK, using Google Translate, I guess the question is the following.

How many pairs of integers (a, b) are necessary to make sure that for two of them, say $(a_1,b_1)$ and $(a_2,b_2)$ it is the case that $a_1\equiv a_2\pmod{5}$ and $b_1\equiv b_2\pmod{5}$?

Dirichlet (or Pigeonhole) Principle talks about pigeons and holes. I suggest considering pairs $(a, b)$ where $a,b\in\mathbb{Z}$ as pigeons and pairs $(x, y)$ where $x,y\in\mathbb{Z}$ and $0\le x, y < 5$ as holes. A pigeon $(a, b)$ is in the hole $(x, y)$ if $a\equiv x\pmod{5}$ and $b\equiv y\pmod{5}$. You have to check that having two pigeons in one hole corresponds to the condition in the problem statement, as well as to find out the number of holes.
• Jun 6th 2011, 10:51 AM
Plato
Quote:

Originally Posted by seit
How many pairs of integers (a,b) are necessary to make sure that for two of them, say $({a_1},{b_1})$ and $({a_2},{b_2})$ it is the case that ${a_1}$ mod 5 = ${a_2}$ mod 5 and ${b_1}$ mod 5 = ${b_2}$ mod 5?

Let $\mathcal{L}=\{0,1,2,3,4\}$ residues mod 5.
Use the pairs in $\mathcal{L}\times\mathcal{L}$ to label 'pigeon-holes".
So we would put the pair $(15,-3)$ into the hole with label $(0,2)$.

How is this question finished?