2
$\begingroup$

How to solve this problem using Pigeonhole Principle?

A worker plans to work 60 hours in the next 37 days, and he works at least 1 h/day, show that he will be working 13 hours in total in some continuous days.

So there are 23 hours more to spend on 37 days, but how is that related to 13 on continuous days?

$\endgroup$
  • 2
    $\begingroup$ And... what did you try? $\endgroup$ – Lazy Lee May 22 '17 at 0:49
  • $\begingroup$ @LazyLee So there are 23 hours more to spend on 37 days, but how is that related to 13 on continuous days? $\endgroup$ – pjpj May 22 '17 at 0:53
  • $\begingroup$ @pwd why don't you break up your problem into blocks of $n$ continuous days where he works at least $n$ hours/block. Choose an appropriate $n$ and then apply PPP to the blocks. (Also, your question would have been much better imo had your comment been part of it). $\endgroup$ – Zain Patel May 22 '17 at 1:02
  • 1
    $\begingroup$ @ZainPatel PPP... pigeon pole principle? $\endgroup$ – Ben Grossmann May 22 '17 at 1:05
  • $\begingroup$ @ZainPatel ... I don't understand your approach. $\endgroup$ – pjpj May 22 '17 at 1:52
1
$\begingroup$

Denote the total amount of the worker has worked from the first day until the $n-$th day by $S_n$.

Now $S_n\leq 60$ and $A_n=S_n+13 \leq 73$ for all $n$.

Both $S_n,A_n$ are between $1$ and $73$ and there are $74$ of them. Consequently, by the pigeonhole principle, there are two of them that are equal.

From your condition that the worker works at least one hour per day the collection of $S_n$ are pairwise distinct and the same holds for the $A_n$ family. Therefore there are $n_1$ and $n_2$ such that $A_{n_1}=S_{n_2}$ whence $S_{n_2}-S_{n_1}=13$.

So we conclude that the desired time interval where the worker worked for exactly $13$ hours is between days $n_1+1, n_1+2, \cdots, n_2$

$\endgroup$
  • $\begingroup$ "total amount of TIME the worker has worked" $\endgroup$ – clark May 22 '17 at 1:18
  • $\begingroup$ why by the pigeonhole principle there are 2 of them are equal? $\endgroup$ – pjpj May 22 '17 at 1:34
  • $\begingroup$ @pwd We have $74$ numbers $S_1, S_2, \cdots , S_{37}, A_1, A_2,\cdots, A_{37}$ and for all $i$ $1 \leq A_i\leq 73$ and $1 \leq S_i \leq 73$. So, we have 74 integers between $1$ and $73$ therefore two of these numbers much be the same. The numbers are the pigeons and the value each number corresponds to is the hole. $\endgroup$ – clark May 22 '17 at 1:40
  • $\begingroup$ @clark could you suggest a textbook where similar problems and/or this kind of reasoning is used/taught $\endgroup$ – magma May 22 '17 at 1:48
  • $\begingroup$ OK, I get it, I think it should be $1\leq S_i \leq 60$ and $14\leq A_i \leq 73$ to be more precise though. $\endgroup$ – pjpj May 22 '17 at 1:56

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.