Mod problem - computer sci math course

[TheRascalKing]

Homework Statement

Let b be a positive integer and consider any set S of b+1 positive integers.
Show that there exists two different numbers x, y ∈ S so that x mod b = y mod b

Homework Equations

The Attempt at a Solution

Pretty stumped. I tried for a while to use different values of b but I soon realized that this could lead to pretty much infinite amounts of any different positive integers in my set.

 

[voko]

So you have b + 1 different numbers. Take any of them, say x, you can obtain z, the remainder of x's division by b, so you have a map x -> z in this way. To how many different z's, at most, can you map the original set?

 

[Mark44]

Homework Statement

Let b be a positive integer and consider any set S of b+1 positive integers.
Show that there exists two different numbers x, y ∈ S so that x mod b = y mod b

Homework Equations

The Attempt at a Solution

Pretty stumped. I tried for a while to use different values of b but I soon realized that this could lead to pretty much infinite amounts of any different positive integers in my set.

This problem uses the "pigeon-hole" principle. Here you have b slots (0, 1, 2, 3, ..., b-2, b-1) and b+1 numbers. Is there any way the b+1 numbers can go into the slots without at least one duplication?