1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Discrete Math proof

  1. Feb 13, 2010 #1
    I'm completely stumped on how to begin a discrete math proof, and I'm looking for a little advice on what might be a good way to approach this.

    In a previous problem I did a proof by contradiction to show that at least one of the real numbers a1, a2, ... an is greater than or equal to the average of these numbers.

    This was done by a1 + a2 + ... + an < nA.
    By definition, A = (a1 + a2 + ... + an)/n, which is a contradiction of the assumption, and therefore proving a1, a2, ... an [tex]\le[/tex] average of these numbers.

    However, now I'm supposed to use this info to prove that if the first 10 integers are placed around a circle, in any order, there exists three integers in consecutive locations around the circle that have a sum greater than or equal to 17.

    I have no idea where to go with this. Can someone give me a pointer that could help me start?


  2. jcsd
  3. Feb 13, 2010 #2
    Let [itex]b_i[/itex] be the ith number plus its two neighbors. Then you wish to show that for at least one i you have [itex]b_i \geq 17[/itex], so for the sake of contradiction assume [itex]b_i \leq 16[/itex] for all i. Now compute the average [itex]A=(b_1+\cdots+b_{10})/10[/itex] and apply your previous result.
  4. Feb 13, 2010 #3
    Thanks, rasmhop :)

    So, with the contradiction, in order to show that the contradiction is false, can I take any set of three integers to show it is false? For example, can I simply assert there would be a ring where 8, 9, and 10 are neighbors, and thus the contradiction is false?

    I'm still not quite certain how the knowledge from the previous problem is useful. I see that A = 5.66, which means that one of the integers selected will be bigger than 6. Yet, this alone doesn't seem to imply there will be neighbors that will ensure the result is greater than 17.

    Thanks again :)
  5. Feb 13, 2010 #4
    Your average is incorrect. [itex]b_1+\cdots+b_{10}[/itex] counts each number of 1,2,...,10 three times so we have,
    [tex]A = \frac{b_1+b_2+\cdots+b_{10}}{10} = \frac{3(1+2+\cdots+10)}{10} = 165/10 > 16[/tex]
    The average is larger than 16, so at least one b_i must be larger than 16 which contradicts that they are all less than or equal to 16.

    No because you're supposed to prove it for all possible ways to place the numbers around the circle and in general 8,9,10 won't be consecutive.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Discrete Math proof
  1. Discrete Math Proof (Replies: 3)

  2. Discrete Math Proof (Replies: 2)

  3. Discrete Math Proof (Replies: 4)