5

Any thoughts on understanding how to do this using the Principle of Mathematical Induction would be great.

A wheel of fortune has the integers from 1 to 25 placed on it in a random manner. Show that regardless of how the numbers are positioned on the wheel, there are three adjacent numbers whose sum is at least 39?

Zev Chonoles
  • 129,973
dwinget2008
  • 51
  • 6
    It is really a Pigeonhole Principle argument. – André Nicolas Jun 13 '13 at 16:29
  • 2
    You can not usually apply induction unless the problem has a parameter, say $n$, which is a natural number i.e. the problem asks you to show that something is true for all $n\in\mathbb{N}$. In that case you show that it is true for some $n_0$ and if it is true for $m$ then it is also true for $m+1.$ – pritam Jun 13 '13 at 16:35

2 Answers2

9

I don't know how you'd apply induction to this, but it's not a hard problem.

There are 25 3-number segments. (They overlap one another, of course.) Let $S_1, S_2, \ldots, S_{25}$ be the sum of the three numbers in each segment. If you add up $S = S_1+\cdots + S_{25}$ you have added each of the numbers $1,\ldots, 25$ three times, so you can calculate exactly what $S$ must be.

Now suppose each of $S_1,\ldots, S_{25}$ were less than 39. This would put an upper bound on how big $ S = S_1+\cdots + S_{25}$ could be. Would this be consistent with the value of $S$ you found in the previous paragraph? If not, you've showed there must be some $S_i$ that is at least 39.

MJD
  • 65,394
  • 39
  • 298
  • 580
3

Note that this can be improved to 41 (instead of 39) using the same ideas.

Consider the position of the number 1.
Take the 8 consecutive sets of 3 digits after that. (These sums would correspond to $S_2, S_5, S_8, S_{11}, S_{14}, S_{17},S_{20}, S_{23}$ in MJD's notation.)
These sets have a sum of $ 2 + 3 + \ldots + 25 = 324$.
Hence, by the pigeonhole principle, one of them must have sum at least $\left\lceil \frac{324}{8} \right\rceil = 41 $.

Is 41 the best we can do? Henry's comment indicates that it is.

Calvin Lin
  • 68,864
  • $1$, $18$, $12$, $11$, $16$, $14$, $8$, $7$, $24$, $10$, $6$, $25$, $9$, $5$, $23$, $13$, $4$, $22$, $15$, $3$, $21$, $17$, $2$, $20$, $19$, $(1$, $18$, $\ldots)$ seems to have a maximum of $41$ for the sum of three consecutive – Henry Jan 13 '21 at 23:49
  • @Henry Great thanks! – Calvin Lin Jan 14 '21 at 03:33