# pigeonhole principle - prove that, if n>(m+k−1)C(k−1)?

Let V={v1,…,vk} be any set of vectors in R^2. Suppose n agents each start at (0,0) and each takes a mV-walk where a mV-walk consists of a sequence of exactly m steps and each step moves the agent along a vector in V. Prove that, if n>(m+k−1)C(k−1), then some pair of agents finishes their walk at the same location.

The (m+k−1)C(k−1) is basically just a giant bracket with m+k-1 on the top and k-1 below it. I think it might be a combination but I'm not sure?how do i do dis

### 1 Answer

- atsuoLv 66 months agoFavorite Answer
Assume that an agent takes

x1 steps along a vector v1,

x2 steps along a vector v2,

.

.

.

xk steps along a vector vk.

So x1 + x2 + ... + kx = m and x1 to xk are non-negative integers.

And the location where the agent finishes his(her) walk is decided

by the combination of x1, x2, ..., xk.

So count the number of ways of dividing m into k non-zero integers.

For example, let m=4 and k=3. Think 4 "X"s and divide them into

3 groups by 3-1=2 partitions. Represent a partition by "p",

the combinations are

XXXXpp : x1,x2,x3 = 4,0,0

XXXpXp : x1,x2,x3 = 3,1,0

XXXppX : x1,x2,x3 = 3,0,1

XXpXXp : x1,x2,x3 = 2,2,0

XXpXpX : x1,x2,x3 = 2,1,1

XXppXX : x1,x2,x3 = 2,0,2

XpXXXp : x1,x2,x3 = 1,3,0

XpXXpX : x1,x2,x3 = 1,2,1

XpXpXX : x1,x2,x3 = 1,1,2

XppXXX : x1,x2,x3 = 1,0,3

pXXXXp : x1,x2,x3 = 0,4,0

pXXXpX : x1,x2,x3 = 0,3,1

pXXpXX : x1,x2,x3 = 0,2,2

pXpXXX : x1,x2,x3 = 0,1,3

ppXXXX : x1,x2,x3 = 0,0,4

2 characters out of 6 characters are "p", so there are 6C2 = 15 ways.

In general, there are (m+k-1)C(k-1) ways. So if n > (m+k-1)C(k-1)

then at least 2 agents have the same combination of x1, x2, ..., xk.

That is, they finish their walk at the same location.