Pigeonhole principle - help expand on proof

[MaryStew]

A group of n agents all start at the same location and each one takes a ≤m-walk on the line, where a ≤m-walk is a sequence of at most m steps and each step moves the agent one unit to the left or one unit to the right. (Different agents might take different walks.) Prove that, if n>2m+1, then some pair of agents finishes their walk at the same location.

Okay, so I know by logic that if the number of agents is higher than (n > 2m+1) then at least one of the agents (pigeons) must end up in the same pigeonhole (location). The problem is I'm not really sure how I can prove this using math or something. I feel that "oh this will always be greater than this number therefore..." is not convincing enough but that's the best I can think of. I was wondering if someone could show me how I could expand on this solution?

 

[Romsek]

what is the total number of different ... squares, units, whatever, that the agents can end up on at the end of their walk?

 

[JeffM]

The only way that you can prove this is if each agent moves the same distance on each move. Now we can think of the starting point as zero on the number line and each agent's ending point as an integer.

The set of possible ending points range from -m through m for a total of 2m + 1 distinct elements in that set. You cannot assign each of n agents to a unique element of 2m + 1 possible set of ending points if n exceeds 2m + 1.

That's all the pigeon hole idea does: compare the sizes of sets.

 

[Steven G]

Lets try to prove that it is NOT true.
Lets consider that number line from -m to m where all the agents start at 0. So there are exactly 2m+ spaces for the agents to land on. Let the1st agent go to 1. The 2nd agent walks to 2,...the mth agent walks to m, the (m+1)st agent walks to 0. There are more than m agents left. Just do the same with the negative number. After m+1 agents reach their destination it must be true that the (m+2)nd agent will occupy the same space as another agent.
We tried our best to prove the statement was wrong but in fact we were wrong.

 

[Steven G]

I do not like the word pair in this problem. A pair, at least to me, is 2 agents.
Now you can put all agents on the same spot and the statement is not true. That is there is NOT a single pair of agents in the same location. Of course the problem wants you to think that a pair means more that one (but that is wrong!)

 

[Dr.Peterson]

Prove that, if n>2m+1, then some pair of agents finishes their walk at the same location.

I'd say the wording issue is here. They mean that some twp agents finish their walks at the same place! Each is walking separately, not as a pair; [at least] two of them have to finish their walks in the same place.

The way I like to think about pigeonhole problems is to imagine an enemy is trying to prevent the goal by manipulating everything that happens. He tries to force each agent to end up in a different place than anyone else; but he fails, because he runs out of places. The last one has to be in an already-used place.