0
$\begingroup$

I have the following problem, quoted directly from Biggs, Discrete Mathematics:

A golfer has $d$ days to prepare for a tournament and must practice by playing at least one round each day. In order to avoid staleness he should not play more than $m$ rounds altogether. Show that if $r$ satisfies $1\leq r\leq 2d-m-1$, then there is a sequence of consecutive days during which he plays exactly $r$ rounds.

I'm not asking for a full solution, but rather for a hint on how to start. Any ideas?

$\endgroup$
  • $\begingroup$ Without thinking too much, an obvious thing to do is pick a specific example (say, $(d,m,r)=(5,3,4)$) and see if you can figure out why it works in that case. (Alternatively, take $r=2d-m=7$ in that case and convince yourself why the inequality matters.) Also, right now the $r$ seems only to be a value constrained by that inequality. Is it supposed to be the total number of rounds he plays in preparation? $\endgroup$ – Semiclassical Oct 9 '14 at 18:48
0
$\begingroup$

This is a pigeonhole principle problem, but it’s a little tricky. I’ll get you started.

For $i=1,\ldots,d$ let $r_i$ be the number of rounds that he plays on day $i$; $r_i\ge 1$ for each $i$. Let $s_0=0$, and for $n=1,\ldots,d$ let $s_n=\sum_{k=1}^nr_k$; then $s_0<s_1<\ldots<s_d\le m$. Suppose that he plays exactly $r$ rounds altogether on days $i+1,\ldots,j$; then $s_i+r=s_j$. Thus, there is a string of consecutive days on which he plays a total of exactly $r$ rounds if and only if at least one of the numbers $s_0+r,s_1+r,\ldots,s_{d-1}+r$ is in the set $\{s_1,s_2,\ldots,s_d\}$. Turn it around: there fails to be such a string of days if and only if the $2d$ numbers $s_0+r,s_1+r,\ldots,s_{d-1}+r,s_1,s_2,\ldots,s_d$ are all distinct. What are the smallest and largest possible values of one of these numbers?

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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