3
$\begingroup$

Say someone is given at least one marble every day for 7 weeks. However, there are never more than 11 marbles given to the person in one week. Prove that there is some period of consecutive days in which the person has been given exactly 20 marbles.

This looks like a question where the pigeonhole principle should be used.

$\endgroup$
  • $\begingroup$ It appears I did not state the question correctly. I've edited the question to include the word "given". Sorry about the confusion. Clearly, this changes the question. $\endgroup$ – settheorynoob Feb 1 '16 at 22:58
  • $\begingroup$ No worries. I'll tidy away my comments now you've fixed the question. $\endgroup$ – Rob Arthan Feb 1 '16 at 23:37
3
$\begingroup$

Hint: Let $a_k$ be the number of marbles the person has been given after $k$ days. Since the person receives at least one marble each day, each element in the set $$A = \{a_1, a_2, \ldots, a_{49}\}$$ is distinct. Since the person receives at most eleven marbles in a week and receives marbles for seven weeks, $$A \subseteq \{1, 2, \ldots, 77\}$$ Let $b_k = a_k + 20$. Then the set $$B = \{b_1, b_2, \ldots, b_{49}\} \subseteq \{21, 22, \ldots, 97\}$$ Hence, $$A \cup B \subseteq \{1, 2, 3, \ldots, 97\}$$ Since $|A| = 49$ and $|B| = 49$, the elements in set $A$ and set $B$ can not all be distinct.

$\endgroup$
  • 2
    $\begingroup$ Cool! So there exists one element in both A and B. So some $a_k = b_l=a_l+20 $. Therefore, there exists k and l such that $a_k-a_l=20$ $\endgroup$ – settheorynoob Feb 2 '16 at 1:58

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.