0
$\begingroup$

As far as I'm concerned to show that something is true, proving that something is true for an example is never enough, you have to be able to prove that it is true for all statements/numbers with the same property. However the answer to a problem that I was trying for a while ends the proof with an example. Maybe it is correct but I'm not seeing why.

Determine the greatest natural number $n$, that has the property that writing the numbers $1,2,3,4....,2010$ in any order , there exists 15 consecutive numbers whose sum is at least equal to $n$.

Proof: The sum of all terms is $S=1005\cdot2011$ . Then we can form $2010/15=134$ disjoint groups each of $15$ terms. Therefore there exists a group with the sum of at least $S/134=15082,5$. Rounding to the nearest integer $15083$ (Why does it use the ceiling function?). Now here is the part that I could not understand. It states: And because an example can be constructed so that there are no 15 consecutive terms with a sum greater than 15803, this is the number sought.

Besides what guarantees that there will always be $15$ consecutive numbers that will satisfy the property if according to the problem they can be chosen on any order?

$\endgroup$
5
  • $\begingroup$ The first part of the proof shows that the minimum must be at least $15083$. But that doesn’t prove the minimum is $15083$. It’s conceivable that some better proof might establish that the minimum has to be at least $15084$, or an even higher number. Providing an example shows that the potential minimum can in fact be achieved, so it really is the minimum, and not just a lower bound on the minimum. $\endgroup$
    – Robert Shore
    Commented Mar 15 at 0:39
  • $\begingroup$ None of the groups can be exactly $15082.5$ as they are the sums of integers. If all $134$ were $15082$ or less then the overall sum would be $134\times 15082$ or less which is too small. So at least one group is $15083$ or more. $\endgroup$
    – Henry
    Commented Mar 15 at 0:53
  • $\begingroup$ He's not just showing that it is an example were there exist 15 sums at least equal to 15083. He is also showing that it is an example in which no fifteen consecutive are more than 15083. Since it's possible to arrange them so that no consecutive 15 are 15084 or more, the answer must be less than 15084. And since every way you arrange them you will always have 15 adding to at least 15083 the anwer must be at least 15083. So the answer must be at least 15083 but it must be less than 15084. That means it must be 15083. $\endgroup$
    – fleablood
    Commented Mar 15 at 1:16
  • $\begingroup$ The thing I'm not seeing, is he doesn't seem to be giving any argument that he can arrange them so that none of the consecutive fifeteen add to more than 15083 even though he is clearly claiming that is the case. $\endgroup$
    – fleablood
    Commented Mar 15 at 1:19
  • $\begingroup$ He's saying the average of groups of 15 is $15082.5$ there must be a consecutive group of 15 which is at least average. So there is a group of 15 that adds to $\ge 15082.5$. As any group of 15 must add to an integer there is a group of 15 that add to $\ge 15083$. That's why the ceiling function. But the more I think about it the more I feel it is not done. We can group them so that $a_1, ..., a_{15}$ and $a_16, ...., a_{30}$ etc all add to $18082$ and $18083$ but how do we show that that is true no matter where we break the grouping? $\endgroup$
    – fleablood
    Commented Mar 15 at 1:27

1 Answer 1

Reset to default
1
$\begingroup$

The proof uses the combinatorial "theorem", the Pigeonhole principle. This provides that S/134 is a good lower bound (dealing with all the possible orderings at the same time). As it is not an integer, but the answer to the question is, we actually got that the answer is at least the lowest integer not smaller than S/134. That's why the ceiling function is used.

Your proof doesn't give the exact example, but if an example of 15803 is provided, then you can see that this can actually be reached. So combining the two steps: you saw an example for a sum of 15803, but also got that there is no ordering for 15802 (or less). You can look at the example as the step providing the upper bound for the proof for the correctedness of the answer.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .