TITLE: Solve using Pigeonhole principle
QUESTION [2 upvotes]: 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?

REPLY [0 votes]: 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) .
{"set_name": "stack_exchange", "score": 2, "question_id": 521451}