2
$\begingroup$

I'd like to ask for some hint for the following math exercise below. I've been working on it for days now and it drives me crazy.

There is a drunkard wolverine who drinks at least $1$ mug of beer every day. (The number of mugs per day is an integer. The wolverine lives forever, so there are infinitely many days.) Every week the wolverine drinks $12$ mugs of beer in total. Prove that one can choose some consecutive days where the number of consumed mugs of beer is $20$.

(A "week" means $7$ days from Monday to Sunday.)

This can be translated into algebraic language; then it says that if $\left(\ldots, m_{-1}, m_0, m_1, m_2, \ldots\right)$ is a sequence of positive integers (infinite in both directions) such that $m_{7i+1} + m_{7i+2} + \cdots + m_{7i+7} = 12$ for each integer $i$, then there exist $u \leq v$ such that $m_u + m_{u+1} + \cdots + m_v = 20$.

The problem is similar to Example 6 of http://www.math.uvic.ca/faculty/jing/222pigeonhole.pdf .

$\endgroup$
  • $\begingroup$ pigeonhole principle. $\endgroup$ – user645636 Dec 28 '19 at 1:14
  • 2
    $\begingroup$ There is some missing information... How many days does the wolverine drink? (e.g., if you only have one week of data, this is impossible) $\endgroup$ – angryavian Dec 28 '19 at 1:14
  • $\begingroup$ Key word is every @angryavian $\endgroup$ – user645636 Dec 28 '19 at 1:19
  • 3
    $\begingroup$ In particular, two weeks of data is not enough: a counterexample is $1, 1, 1, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6$. $\endgroup$ – angryavian Dec 28 '19 at 1:46
  • $\begingroup$ @angryavian You have a seven day period where the wolverine only drinks seven beers. Does every week mean starting and ending on a fixed day or does it mean every seven day period? $\endgroup$ – John Douma Dec 28 '19 at 14:38
5
$\begingroup$

Hint: For a period of three consecutive weeks, keep track of the total number of beers the wolverine has consumed, mod $20$. This number will start at $1$ on the Monday of the first week and end at $16$ on the final Sunday, at which point the Wolverine has consumed a total of $36$ beers.

Rest of solution below:

Since there are $21$ days altogether and only $20$ residues mod $20$, the pigeonhole principle says some residue must repeat within the three-week period, which means the wolverine has consumed some multiple of $20$ beers from the first of those two days to the second. But the only (positive) multiple of $20$ less than $36$ is $20$ itself.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm ashamed of not being able to solve this myself... :( Anyway thanks for your answer $\endgroup$ – v0rp3x Dec 28 '19 at 19:37
2
$\begingroup$

Let $a_i$ be the total number of mugs drunk on days $1$ through $i$.

$a_1,a_2,\ldots$ is a strictly increasing sequence of positive integers, such that $a_{7k} = 12k$ for positive integers $k$.

It turns out that it suffices to look at the first $35$ days.

Consider $a_{15}, a_{16}, \ldots,a_{35}, a_1+20, a_2+20,\ldots, a_{21}+20$. This is a list of $42$ numbers ranging from $21$ to $60$, so some number must appear [at least] twice in that list. Because $(a_i)$ is strictly increasing, $a_{15},\ldots, a_{35}$ must be distinct, and $a_1+20, \ldots, a_{21} +20$ must be distinct. Can you conclude from here?


Note that this answer is inferior to Barry Cipra's since this answer requires 35 days while his requires only 21.

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

Turns out the answer by @BarryCipra is tight, in the sense that we cannot prove it using $20$ (or fewer) days.

Here is a drinking schedule, listing the cumulative consumption after the first $20$ days.

  • week $1: 1, 3, 5, 7, 9, 11, 12$

  • week $2: 16, 17, 18, 19, 20, 22, 24$

  • week $3$ (minus last day)$: 26, 28, 30, 33, 34, 35$

It is clear that no pair of numbers differ by $20$ (or in Barry's context, we have used every residue of mod $20$ exactly once).

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

Every week the wolverine drinks 12 mugs with one guaranteed per day, so using the sticks and stones method, there are $\dbinom{12-7+6}{6}=462$ ways the wolverine can drink beer in one week. Hopefully this helps in some way.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ aka stars and bars. $\endgroup$ – user645636 Dec 28 '19 at 3:03

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.