Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Ten students are sitting around a campfire. A teacher randomly assigns each student a different number from 1-10. Another teacher assigns a new number to each student with the requirement that the new number assigned to a student is equal to the students' old number plus the sum of the two numbers of his neighbors. Prove or disprove: one of the students must have a new number STRICTLY GREATER than 17.

What I have done so far: It is very easy to show that one of the students must have a new number strictly greater than 16. This can be done by assuming that each of the numbers is less than or equal to 16. A quick sketch is as follows:

Label the students $a_1, \dots a_{10}$. By contradiction, we have:

$a_1+a_2+a_3 \le 16$

$\dots$

$a_{10} +a_1+a_2 \le 16$

Summing up:

$3a_1+\dots +3a_{10} \le 16\cdot 10$

This is a contradiction as $a_1+\dots + a_{10} = 55$

But this argument breaks down when we try it for 17. Im not even sure that the proposition that a student must have a number more than 17 is even correct! Can someone prove it or find a counterexample?

share|improve this question

3 Answers 3

You are on the right track. We know that the sum of the numbers originally assigned is $55$, and so the sum of the numbers assigned by the second teacher must be three times this, or $165$.

What if every student has a number that is at most $17$? There must be at least 5 people who have the number $17$. In how many different ways can two people be given the number $17$?

Well, way the guy with $9$ originally now has $17$. Then he must be seated next to $1$ and $7$, to $2$ and $6$, or to $3$ and $5$.

Say it's 3 and 5; can 3 or 5 get 17 in the second round? No: one of their neighbors in 9; but the other neighbor they need is sitting on the other side of 9! So neither 3 nor 5 will get 17 in the second assignment.

So: one student gets 17; then her two neighbors do not. Perhaps the next students round in both directions get 17? Then their other two neighbors don't (same argument). So now we have three students who did get 17, and four who did not. We still need at least two more students to get 17, and we only have three students left; can it be done?

Check the other possibilities. Maybe one student got 17, his two neighbors did not, and one of the next two did; is there enough room for the minimum 5 students we need to get 17?

share|improve this answer
    
In the first case (alternating 17s), show that the arrangement must have alternating 17s and 16s ... –  Mark Bennet Aug 29 '11 at 7:52

Using ideas from Arturo Magidin's answer and Mark Bennet's comment:

The average score in the first round is $5.5$, so the average score in the second round is $16.5$. Since scores are integers, this means at least one of the following is true:

  1. Someone has strictly more that 17 in the second round
  2. At least two neighbours have exactly 17 in the second round
  3. The arrangement must have alternating 17s and 16s

For (2), look at $a_1+a_2+a_3 = 17$ and $a_2+a_3+a_4 = 17$, to solve for $a_4$ in terms of $a_1$.

For (3), look at $a_1+a_2+a_3 = 17$ and $a_2+a_3+a_4 = 16$, (ignore $a_3+a_4+a_5 = 17$,) and at $a_4+a_5+a_6 = 16$ and $a_5+a_6+a_7 = 17$, to solve for $a_4$ in terms of $a_1$ and then to solve for $a_7$ in terms of $a_4$.

So (1) must be the case.

share|improve this answer

You have already shown that a student should have a new number that is atleast 17.

Now consider the old numbers. Ignore the student whose old number assignment was $1$. The sum of the old numbers of the remaining students is $54$. Divide these students into three arbitrary (non overlapping) groups. The average sum of three numbers in this group is $54/3 = 18$. Hence, one of the new numbers must be 18 or greater.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.