Anonymous
Anonymous asked in Science & MathematicsMathematics · 6 months ago

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

Relevance
  • atsuo
    Lv 6
    6 months ago
    Favorite 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.

Still have questions? Get your answers by asking now.