2
$\begingroup$

There are 45 candidates appear in an examination. prove that there are at-least two candidates in class whose roll numbers differ by a multiple of 44.

How can I prove this using pigeonhole principle?

$\endgroup$
3
  • $\begingroup$ What do you mean by "roll numbers"? $\endgroup$
    – BaronVT
    Oct 10 '13 at 14:06
  • $\begingroup$ What have you tried - given that you have two numbers which differ by one in the text of your question, which will be the pigeons, and which the holes? $\endgroup$ Oct 10 '13 at 14:06
  • 2
    $\begingroup$ @BaronVT As far as I know, a roll number is basically a student ID number, just an integer that is different for each person. As far as I can see by Internet search, this is a term used in the UK, India, Pakistan, and a bit in Australia, but not e.g. in the US. $\endgroup$ Jan 10 '14 at 6:18
6
$\begingroup$

Consider the possible remainders mod $44$ as the boxes. There are $44$ of these.

Now there are $45$ roll numbers in total. Place each in its box corresponding to its remainder mod $44$.

The pidgeonhole principle says that there will be at least two roll numbers $a,b$ such that they lie in the same box, i.e. $a\equiv b \bmod 44$.

But then $44|(a-b)$.

$\endgroup$
0
$\begingroup$

As we know

Dividend = Quotient x Divisor + Remainder

Here

Dividend = roll number
Divisor = 44
Quotient = any number (depends on Roll number)

But ,

Remainder will be always lies between 0 to 43 (Total count is 44).

Difference of two Roll Number = 44 * diff of Quotient + diff of Remainder .

If diff of Remainder is not zero then Diff of two Roll Number is not multiple of 44.

But it is impossible because all 45 Roll number cannot generate 45 unique Reminder.It will always lies between 0 to 43 (This is called Pigeonhole principle, failed to find uniqueness) .

$\endgroup$
1
  • $\begingroup$ The OP wanted to solve the problem using the pigeonhole principle. $\endgroup$ Dec 21 '15 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.