A field worker has to make altogether 43 visits, at least one on each day. Is there a period of consecutive days on which he makes exactly 21 visits if he makes his visits on 22 days? What happens to the problem if he makes his visits on 23 days instead of 22 days?  How can I approach to solve this problem using Pigeonhole principle, thanks.
123227
This is for self-study. This question is from Rosen's "Discrete Mathematics And Its Applications", 6th edition.  An arm wrestler is the champion for a period of 75 hours. (Here, by an hour, we mean a period starting from an exact hour, such as 1 P.M., until the next hour.) The arm wrestler had at least one match an hour, but no more than 125 total matches.  1 - Show that there is a period of consecutive hours during which the arm wrestler had exactly 24 matches.  2 - Is the statement in the previous exercise true if 24 is replaced by  a) 2? b) 23? c) 25? d) 30?  My solution to part 1 is the following, based on Rosen's solution to a similar problem given as example in the text:  1 - If I consider $a_i$ to be the number of competitions until the $i^{th}$ hour, then, $1\leq a_1&lt;a_2&lt;\cdots&lt;a_{75}\leq 125$, because there are no more than 75 hours and the total number of competitions is no more than 125. Now I will add 24 to all the terms of the above inequality: $25\leq a_1+24&lt;a_2+24&lt;\cdots&lt;a_{75}+24\leq 149$.  There are 150 numbers $a_1,\cdots,a_{75},a_1+24,\cdots,a_{75}+24$. By the inequalities above, these numbers range from 1 to 149. Then, by the pigeonhole principle, at least two of them are equal (in a list of 150 integers ranging from 1 to 149, at least two are equal).  Because all the numbers $a_1,\cdots,a_{75}$ are distinct, and all numbers $a_1+24,\cdots,a_{75}+24$ are also distinct, it follows that $a_i = a_j + 24$ for some $i &gt; j$. Therefore, from the $(j+1)^{th}$ hour to the $i^{th}$ hour, there were exactly 24 competitions.  Now, I will show the attempt at a solution for part 2:  2 - a) The same reasoning as above can be used:  $1\leq a_1&lt;a_2&lt;\cdots&lt;a_{75}\leq 125$. Adding 2 to all terms:  $3\leq a_1 + 2&lt;a_2 + 2&lt;\cdots&lt;a_{75} + 2\leq 127$  So, there are 150 numbers that range from 1 to 127. Therefore, by the pigeonhole principle, at least $\left \lceil \frac{150}{127} \right \rceil$ = 2 numbers must be equal. So, there is an $a_i = a_j + 2$. This guarantees that there is a period of consecutive hours during which there were exactly 2 competitions.  b) The same reasoning as above can be used:  $1\leq a_1&lt;a_2&lt;\cdots&lt;a_{75}\leq 125$. Adding 23 to all terms:  $24\leq a_1 + 23&lt;a_2 + 23&lt;\cdots&lt;a_{75} + 23\leq 148$  So, there are 150 numbers that range from 1 to 148. Therefore, by the pigeonhole principle, at least $\left \lceil \frac{150}{148} \right \rceil$ = 2 numbers must be equal. So, there is an $a_i = a_j + 23$. This guarantees that there is a period of consecutive hours during which there were exactly 23 competitions.  c) $1\leq a_1&lt;a_2&lt;\cdots&lt;a_{75}\leq 125$. Adding 25 to all terms:  $26\leq a_1 + 25&lt;a_2 + 25&lt;\cdots&lt;a_{75} + 25\leq 150$  In this case, there are 150 numbers that range from 1 to 150. So, there are not necessarily two equal numbers. Therefore, we can't conclude anything directly.  But it is possible to show that the statement is not true for 25, because an explicit counter-example (suggested below in the comments) can be found. Suppose the number of matches until each one of the 75 hours is, respectively: $\{1,2,\cdots,25,51,\cdots,75,101,\cdots,125\}$. Here, there are no pairs of numbers whose difference is 25.  d) $1\leq a_1&lt;a_2&lt;\cdots&lt;a_{75}\leq 125$. Adding 30 to all terms:  $31\leq a_1 + 30&lt;a_2 + 30&lt;\cdots&lt;a_{75} + 30\leq 155$  In this case, there are 150 numbers that range from 1 to 155. So, we can't apply the pigeonhole principle here, similarly to the above situation. It is not easy to find a counter-example in this case; I think that, for 30, the statement is always true (that is, there is always a period of consecutive hours during which there were exactly 30 matches). But I'm not sure how to prove it.  Edit: I think I found a way to prove it, based on the suggestion given by Lopsy; I've included it as an answer to this question.  Thank you in advance.
62763
I was wondering if someone could critique my argument here. The problem is to find the probability where exactly 2 people in a room full of 23 people share the same birthday.  My argument is that there are 23 choose 2 ways times $\displaystyle \frac{1}{365^{2}}$ for 2 people to share the same birthday. But, we also have to consider the case involving 21 people who don't share the same birthday. This is just 365 permute 21 times $\displaystyle \frac{1}{365^{21}}$. To summarize:  $$\binom{23}{2} \frac{1}{365^2} \frac{1}{365^{21}} P\binom{365}{21}$$
118602
As most of you might know, the Pigeonhole Principle basically  that      If $n$ items are put into $m$ containers, with $n&gt;m$, then at least one container must contain more than one item   It always surprises me how this trivial - and at the same time powerful - idea might be the key in order to solve extremely complicated math olympiad-problems...  Quick and beautiful solutions are characteristic of pigeonhole problems, which are often a three-part process   Recognize that the problem requires the Pigeonhole Principle Figure out what the pigeons and what the pigeonholes might be After applying the pigeonhole principle, there is often more work to be done   I'll illustrate this with an example I've always liked...     (Example-)Problem: Given a $n\times n$ square, prove that if $5$ points are placed randomly inside the square, then two of them are at most $\frac{n}{\sqrt2}$ units apart.   Step 1: This problem can be solved with the Pigeonhole Principle  Step 2: We divide the $n\times n$ square into four $\frac{n}{2}\times\frac{n}{2}$ squares (pigeonholes). Consequently, at least two points (pigeons) are inside the same $\frac{n}{2}\times\frac{n}{2}$ square.  Step 3: The maximal distance between two points in an $\frac{n}{2}\times\frac{n}{2}$ square is the diagonal, which has the length $\frac{n}{\sqrt2}\qquad\square$  Another problem which can be solved with the Pigeonprinciple is the following:     IMO $1972/1$           Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum.      At this point, you might have noticed how useful the Pigeonhole Principle can be, if you know how to recognize and use it.     Question: I would like to work on this amazing principle with my students for a week and was, therefore, gathering problems related to the Pigeonhole Principle with beautiful solutions.   Could you suggest some more?
16530
During self-study, I ran across the question of how many ways six numbers can be chosen from the numbers 1 - 49 without replacement, stipulating that no two of the numbers be consecutive.  I can obtain a simple lower bound by saying that, in the worst-case scenario, when you choose a particular number, there are now three numbers that cannot be chosen next.  For example, if I first pick 17, then I can't choose 16, 17, or 18 for the remaining choices.  This gives me the lower bound  $$\frac{49*46*43*40*37*34}{6!} = 6,773,770 \frac{8}{9}$$  This is about 48% of ${}_{49}C_6 =  13,983,816$.  The real answer must be bigger (and an integer).  I haven't found a way to calculate it, though.  The original problem asked to show that the probability of having non-consecutive integers when you choose six is greater than 50%, so if the problem is complicated to count exactly, better approximations that show the answer is above 50% would also be appreciated.   Of course, I can use a computer to do the counting, but I'm interested in learning what methods I'm missing.
43369
During a period of $n$ days, two persons drink beers, one each. There are $n$ different beers $B_1, B_2, B_3,\ldots, B_n$, where $n\geqslant 1$ is an integer. t Person1 drinks the beers in order, i.e., on the $i$-th day, she drinks beer $B_i$. Person2 takes a uniformly random permutation $a_1, a_2, \ldots, a_n$ of the set $\{1, 2,\ldots, n\}$ and drinks beer $B_{a_i}$ on the $i$-th day. Let $X$ be the random variable whose value is the number of days during which person 1 and person 2 drink the same beer. Determine the expected value $\mathbb E(X)$ of $X$.  I know that I should let $X$ be the number of days during which both persons drink the same beer. And  $$ X_i = \left\{\begin{array}{rc} 1,&amp;\text{if they drink the same beer on the }i\text{-th day} \\ 0,&amp;\text{if they drink different beers on the }i\text{-th day}\end{array}\right. $$  Then  $$\begin{align} \mathbb E[X_i] &amp;= 1\cdot P(X=1) = P(\text{Person 1 and Person 2 drink beer }i) \\&amp;= P(\text{Person1 drinks beer }i)P(\text{Person 2 drinks beer }i) \\ &amp;= 1\cdot P(\text{Person 2 drinks beer }i) = \frac{1}{(n-i)!} \end{align}$$   So, is my approach right? If it's will the next step be: $\mathbb E(X) = n\cdot\frac{1}{(n-i)!}$?
105141
How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two   consecutive integers if 1 and n also count as consecutive?   It looks that the number of such subsets obeys the (Fibonacci-style) formula $$ F(n) = F(n-1)+F(n-2) $$ with $F(0)=1$ and $F(1)=2$, but I wasn't able to prove this conjecture.
75151
The problem is quite simple to formulate. If you have a large group of people (n > 365), and their birthdays are uniformly distributed over the year (365 days), what's the probability that every day of the year is someone's birthday?  I am thinking that the problem should be equivalent to finding the number of ways to place n unlabeled balls into k labeled boxes, such that all boxes are non-empty, but C((n-k)+k-1, (n-k))/C(n+k-1, n) (C(n,k) being the binomial coefficient) does not yield the correct answer.
102177
I'm back again So there's another problem that I can't get to prove  If we take 21 numbers randomly from $1, 2, 3, ..., 40$ then between those $21$ numbers we will be able to find two numbers, of which the smaller one will divide the bigger one  I've been reading james hein "discrete structures, logic and computability" but still can't get to think logically myself. I would be very grateful if I could get some directions/tips/hints or anything, thanks in advance
64110
Show that any set of 7 distinct integers includes two integers $x$ and $y$, such that either $x-y$ or $x+y$ is divisible by 10. I'm trying to apply the pigeonhole principle, but haven't been able to come up with a convincing argument.   Though similar to , I think the difference between the two is enough to warrant a second post.
46496
Hi there I am planning a ”Scavenger hunt”-like activity (I have no other words for this event), and I am having trouble creating the schedule.   The idea of this hunt/run/game/competition is that 10 teams will battle each other at X different mini games. The games on are team vs. team based, meaning that there will always be two teams on each post and one winner and one loser.  I require that every team fights every other team. Meaning that team 1 will have to meet team 2, 3, 4, 5, 6, 7, 8, 9, and 10, and team 2 will have to meet team 1, 3, 4, 5, 6, 7, 8, 9, 10 (and so forth). The amount of mini games must be so, that every team only meets the other teams ONCE each, but still they have to meet every team.  How many posts do I need to create, and how could I schedule the overall activity? (A table of rounds and teams would be much appreciated).
38568
Just wanted to share a nice problem.I have given my method below.More answers are welcome.  Consider a rectangular integral grid of size $m*n$.A person has to travel from one end say $(0,0)$ to the diagonally opposite end $(m,n)$.He moves one step at a time towards the east or towards the north(that is,never moves towards the west or south at any time).How many distinct paths exist from the point A to the point C ?
90820
Can someone check my logic here.   Question: How many ways are there to choose a an $k$ person committee from a group of $n$ people?   Answer 1: there are ${n \choose k}$ ways.   Answer 2: condition on eligibility. Assume the creator of the committee is already in the committee. This leaves us with choosing $k - 1$ people from a group of $n - 1$ potentially eligible people. If all remaining people are eligible, there are ${n - 1 \choose k - 1}$ possible committees, if there are $n - 2$ eligible people, there are ${n - 2 \choose k - 1}$ committees, if there are $n - 3$ eligible people, there are ${n - 3 \choose k - 1}$ committees,..., if there are $k - 1$ eligible people there are ${k - 1 \choose k - 1}$ committees. Therefore,$${n - 1 \choose k - 1} + {n - 2 \choose k - 1} + {n - 3 \choose k - 1} + \dots + {k - 1 \choose k - 1} = {n \choose k}$$.
97085
Adam has a box containing 10 cookies. Each day he eats each cookie with a probability of $\frac12$. Calculate the expected number of days it takes Adam to complete the cookies.   As a start we can set $X$ as the expected days it takes for Adam to finish eating the cookies. However I'm unable to progress further.
39036
"An event less frequent in the long run is likely to happen before a more frequent event!"  How can I show that THTH is more likely to turn up before HTHH with a probability of  9/14, even though waiting time of THTH is 20 and HTHH, 18!  I would be very thankful if you could show me the way of  calculating the probability of turning up earlier,   and the waiting time. Thank you!
57418
I recently read a math problem and, having not yet taken anything beyond calculus 1, was curious about how to solve it correctly.   Problem:  Calculate the probability of two people meeting at the same location between 1 and 2 p.m. Assume both people show and person 1 will wait 15 minutes for person 2.     Doesn't this probability increase as the time frame shrinks?  For example, Isn't there a much smaller chance the pair will meet if person 1 arrives at 1:00 vs arrives at 1:45 (the probability of meeting becomes 1).  Is this somewhat easily answered using basic statistics?  Just curious if my thought process is accurate or way wrong.
21919
I have been looking at the birthday problem (http://en.wikipedia.org/wiki/Birthday_problem) and I am trying to figure out what the probability of 3 people sharing a birthday in a room of 30 people is. (Instead of 2).  I thought I understood the problem but I guess not since I have no idea how to do it with 3.
80007
Anyone have any ideas on this question? I think you have to use the pigeon hole principle..but I am not sure about that?     The numbers $1,2,3,\ldots,101$ are written down in a row in some order. Is it always possible to cross out $90$ numbers in a way such that all $11$ numbers left will stay either in increasing or decreasing order?