Solution: 2016 Fall Midterm - 8

To determine the minimum value of $ m $ such that we can guarantee that a set $ S $ of $ m $ integers contains at least two elements whose difference is divisible by $ n $, we can use the Pigeonhole Principle.

Let $ k \geq 1 $ be an integer. If $ k+1 $ or more objects are placed into $ k $ boxes, then there is at least one box containing two or more objects.

• textbf{Residue Classes Modulo $ n $:}
  Consider the integers modulo $ n $. There are $ n $ possible residue classes: $ 0, 1, 2, ..., n-1 $.
• textbf{Pigeonholes and Pigeons:}
  Each integer in the set $ S $ will fall into one of these $ n $ residue classes. If $ m $ integers are placed into these $ n $ residue classes, then by the Pigeonhole Principle, if $ m > n $, at least two integers must fall into the same residue class.
• textbf{Difference Divisible by $ n $:}
  If two integers are in the same residue class, their difference is divisible by $ n $. Therefore, we need $ m $ to be large enough to ensure that at least two integers are guaranteed to fall into the same residue class.

To guarantee that there are at least two elements whose difference is divisible by $ n $, we need at least one more than $ n $ integers. Thus, the minimum value of $ m $ is $ n + 1 $.

The minimum value of $ m $ such that we can guarantee that $ S $ contains at least two elements whose difference is divisible by $ n $ is $ n + 1 $. $boxed{m = n + 1}$