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?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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)$.
As we know
Dividend = Quotient x Divisor + Remainder
Dividend = roll number
Divisor = 44
Quotient = any number (depends on Roll number)
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) .