Posers and Puzzles

Posers and Puzzles

  1. Joined
    25 Aug '06
    Moves
    0
    12 Jan '10 22:50
    Prove:

    If two numbers greater than 1 appear in the same row in Pascal's triangle, then they cannot be coprime.
  2. Standard memberua41
    Sharp Edge
    Dulling my blade
    Joined
    11 Dec '09
    Moves
    14434
    12 Jan '10 23:53
    I'm not as fluent in mathematics, but could one use the Euclidean algorithm to do such a thing?
  3. Joined
    02 Mar '06
    Moves
    17881
    13 Jan '10 13:47
    Originally posted by David113
    Prove:

    If two numbers greater than 1 appear in the same row in Pascal's triangle, then they cannot be coprime.
    i think i've seen this before and it was a relatively cute problem... don't remember the path towards solution though. maybe using the definition of the "choose" numbers, and seeing that some factor not cancelled in n!/k!(n-k)! must also necessarily be present in n!/(k+i)!(n-[k+i])! for any number i<(n-k)? something to that effect?
  4. Standard memberTheMaster37
    Kupikupopo!
    Out of my mind
    Joined
    25 Oct '02
    Moves
    20443
    17 Jan '10 17:12
    Here's my go at it. Might be wrong though :/

    Let A = k!(n-k-1)! and C = GCD(k+1, n-k)

    (n over k) = n! / k!(n-k)! = n! / A(n-k)

    (n over k+1) = n! / (k+1)!(n-k-1)! = n! / (k+1)A


    So the GCD of the two is Cn! / (k+1)(n-k)A = Cn! / (k+1)!(n-k)! = C(n over k) / (k+1)

    Since both of the combination-numbers are not equal to 1 we know that k is not 0, n-1 or n.

    From that we have that k+1 divides N but also is smaller than n. And thus the GCD > 1.
Back to Top