Answer to Question #270882 in Discrete Mathematics for kd bhai

Question

45 candidates appear in a competitive examination. Prove that there are at least two candidates

whose roll numbers differ by a multiple of 44.

Answer 1

Taking into account that there are 44 different remainders of the division by 44, we conclude by Pigeonhole Principle that among 45 roll numbers thare are at least two numbers $a$ and $b$ with the same remanders. It follows that $a=44t+r$ and $b=44s+r$ for some $t,s\in\Z$ and $0\le r<44.$ Therefore, $a-b=(44t+r)-(44s+r)=44(t-s).$ We conclude that 44 divides $a-b,$ and hence there are at least two candidates (with roll numbers $a$ and $b$) whose roll numbers differ by a multiple of 44.