Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Pidgeon hole

  1. Jul 31, 2006 #1
    I am in a really badly taught and administered summer course :grumpy:
    We never get solutions to exams or explanations of our mistakes. So, here is this problem that bothers me, still don't know how to do it:

    Prove that in sequence of 15 positive integers (not including zero) that are not necessarily consequitive and not necessarily unique which sum up to 24 there is a sequence of numbers summing up to 5.

    I am not even sure if I understood the question right, but is it THAT trivial? I mean, you can have all itegers = 1 and there is a sequence of 5 one's, but that even does not add up to 24.
    Anyway... someone help, please :confused:
  2. jcsd
  3. Jul 31, 2006 #2


    User Avatar
    Science Advisor

    Well, if they are all positive you can split them into those that equal 1, and those that do not equal one. Your job is to show that there are at least five numbers in the sequence that equal one.
  4. Jul 31, 2006 #3
    well it is pretty trivial to see that it is true:

    if the sum is 24 and you need 15 positive numbers, consider what happens when all of them are [itex]\leq 2[/itex]. Then you can have at most 12 2's: if you have more than 12 2's, then the sum of those will be [itex]> 24[/itex]. So you have [itex]\leq 12[/itex] 2's. But in fact you can't have any more than 9 [itex]2's[/itex]: if you have 12 2's then their sum is 24 so you can't add any other numbers, if you have 11 2's then their sum is 22 so you get at most 13 numbers, and if you have 10 2's then their sum is 20 so you get at most 14 numbers. On the other hand, 9 2's and 6 1's gives a sum of 24 with 15 numbers.

    See if you can finish the rest on your own :smile:
  5. Aug 3, 2006 #4
    Think about the type of 15 numbers you can use to add up to 24. If you wanted to use the lowest numbers possible for all 15 numbers, how many times would the number one have to be used?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook