Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and the Yahoo Answers website is now in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

Anonymous
Anonymous asked in Science & MathematicsMathematics · 1 year 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
    1 year 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.