# Tag Info

12

HINT: Let $S=\{f(k):k=0,\ldots,49\}$; you want to show that there is some $k$ such that $f(k)+20\in S$. (You want to allow $k=0$ to cover the possibility that some $f(k)=20$; $f(0)$ is of course $0$.) You know that $f(49)\le 7\cdot11=77$, so all of the $100$ integers $f(k)$ and $f(k)+20$ for $k=0,\ldots,49$ are in the range $[0,97]$. However, there are only ...

6

OK this was an interesting problem in itself, and the pigeonhole principle is implicit in practically any argument, so I just felt I would try to reason it out directly. With all kudos to Brian M Scott's more "hands-off" solution. I'll proceed by trying to devise a schedule that allows Jessica to beat the expectation of a run of days with a 20-hour study ...

6

The proof consists of two parts. Part I: Prove that a period of $20$ days is enough such that there must exist some period of consecutive days during which totally $20$ hours are spent on studying. Part II: A counterexample which shows that $19$ days are not enough is presented. Proof of Part I Let $x_1$, $x_2$, $\cdots$, $x_{20} \in \mathbb{N}^+$ ...

5

Here's code to run an exhaustive search, which confirms your suspicion that the answer is $20$ days. Interestingly, it's still $20$ days if Jessica is allowed to work up to $14$ hours in any $7$-day period. If she's allowed to work $15$ hours, a repeating pattern of $5,1,1,1,5,1,1,1,\ldots$ avoids any sums of $20$ for any number of days.

4

Hint: Show that there exist at least two disjoint periods in each of which the total number of hours spent for combinatorics is $0$ modulo $20$. Prove that one of them must have exactly $20$ hours (by verifying that not both periods can have at least $40$ hours).

4

Inscribe a regular pentagon in the circle. Three of the vertices must have the same color and they form the triangle you seek.

3

We proceed via induction over $n$. The base case is $n=1$ and it is trivial, we have $3$ numbers, so clearly we can pick two with the same parity. Inductive step: Split the $2^{n+1}-1$ elements into two groups of size $2^{n}-1$ and an extra element. By the inductive hypothesis we can pick two groups of $2^{n-1}$ elements from each group, with sum ...

2

This is in response to @joriki's observation that the constraint of the weekly total studying hours could be loosen while the conclusion of minimum $20$ days would still hold. I am not sure if it's appropriate to post this as an answer, but it turns out to be too long to fit in the comment section. We shall prove the following, by using a slightly ...

1

As suggested in the comments this is Erdos-Ginzburg-Ziv theorem for a power of $2$. The proof of E-G-Z has an easy inductive part, that if the theorem is true for $p$ and $q$ it is true for $pq$, and a nontrivial base case of proving the theorem true for primes. Here the prime is $2$ so the base case is true by inspection. The proof of the multiplicative ...

1

Connect the midpoints of the sides to each other. This divides the original triangle into four smaller, congruent equilateral triangles of side 1 unit. You have five points and only four triangles, so two points must be in one of the triangles. They can't be more than one unit apart.

1

I think this might essentially be a reformulation of Wiley's proof in the case when at most $13$ hours of study are permitted over a $7$-day period. However, the application of the pigeonhole principle is perhaps simpler. For $0 \le i \le 20$, let $S_i$ be the total number of hours studied by the end of the $i$th day (setting $S_0 = 0$), and consider these ...

1

Hint: If two kings sit in a $2$-by-$2$ square, they are in check.

Only top voted, non community-wiki answers of a minimum length are eligible