3

A gambler buys at least one lottery ticket everyday, maybe more. During the whole year he buys at most $400$ tickets. Show that during the year there exists a sequence of consecutive days for which the total number of tickets bought is exactly $330$. Hint: if $v_i$ is the number of tickets bought up to and including the $i^{th}$ day of the year, then we want to prove that there exists $j$ and $i$, with $j>i$, such that $v_j = v_{i-1} + 330$.

I'm not totally sure how to do this. However, I think that it involves the pigeon hole principle. thanks.

Robert MingHao
  • 51
  • This seems like it should be easy but I've been working on it for a while and I'm not finding the magic bullet. It can't be a coincidence that $400-365=35$ and $365-330=35$. – Gregory Grant Feb 16 '16 at 02:41
  • If the question said the gambler buys less than $400$ tickets during the whole year or the year were a leap year, the conclusion would follow. However, since it says at most $400$ and it does not specify that it is a leap year, the conclusion is not necessarily true. – N. F. Taussig Feb 16 '16 at 02:43
  • @N.F.Taussig Can you be specific about the counter-example then please – Gregory Grant Feb 16 '16 at 02:48
  • @GregoryGrant I have posted an answer. – N. F. Taussig Feb 16 '16 at 03:02

1 Answers1

2

The assertion is false.

Counterexample: Let $$ v_i = \begin{cases} 2i - 1 & \text{if $1 \leq i \leq 18$}\\ i + 17 & \text{if $19 \leq i \leq 313$}\\ 2i - 296 & \text{if $314 \leq i \leq 330$}\\ i + 35 & \text{if $331 \leq i \leq 365$} \end{cases} $$ Observe that if there were to exist $i, j$ such that $v_j = v_i + 330$, then $v_i \leq 35$. In the counterexample, there are $18$ such numbers, each of which is odd. Hence, for $1 \leq i \leq 18$, $v_i + 330$ is an odd number and $331 \leq v_i + 330 \leq 365$. If $i \leq 313$, $v_i < 331$. If $i \geq 331$, $v_i > 365$. If $314 \leq i \leq 330$, $v_i$ is an even number satisfying $332 \leq v_i \leq 364$. Hence, there is no $j$ such that $v_j = v_i + 330$.

Note: If we were to replace the words "at most" with less or the year were a leap year, we could draw the desired conclusion. What follows is an attempt to apply the Pigeonhole Principle with the given conditions.

Let $v_i$ be the total number of tickets the gambler has purchased after $i$ days. Let $w_i = v_i + 330, 1 \leq i \leq 365$. Let $$A = \{v_1, v_2, \ldots, v_{365}\}$$
Let $$B = \{w_1, w_2, \ldots, w_{365}\}$$
Since the gambler buys at least one lottery ticket each day, $|A| = |B| = 365$. Since each $v_i$ satisfies the inequalities $1 \leq v_i \leq 400$, $$A \subseteq \{1, 2, 3, \ldots, 400\}$$ Since each $w_i$ satisfies the inequalities $331 \leq w_i \leq 730$, $$B \subseteq \{331, 332, 333, \ldots, 730\}$$
Hence, $$A \cup B \subseteq \{1, 2, 3, \ldots, 730\}$$ If $|A| + |B| \geq 731$, we could conclude that $A \cap B \neq \emptyset$, which would imply that there exists $v_j \in A$ and $w_i \in B$ such that $v_j = w_i$, from which we could conclude that $v_j = v_i + 330$. However, that is not the case here.

N. F. Taussig
  • 76,571
  • 2
    I follow your argument and it's elegant. But it's not clearly constructive so it doesn't completely prove that there's not some other unforeseen reason that $A\cap B\not=\emptyset$. So to prove it conclusively we'd need an explicit example of assigning numbers between $1$ and $35$ to every day that total $400$ and yet there's no solution to the $330$ consecutive problem. It's not that I don't believe it's false I just need to see the counter-example to believe it 100%. – Gregory Grant Feb 16 '16 at 03:13
  • @GregoryGrant I added a specific counterexample. – N. F. Taussig Feb 16 '16 at 03:56