Hot answers tagged pigeonhole-principle
78
Here is a way of rewriting your original argument that should convince your friend:
Let $A,B,C,D\subset\{1,2,\dots,100\}$ be the four sets, with $|A|=85$,$|B|=80$,$|C|=75$,$|D|=70$. Then we want the minimum size of $A\cap B\cap C\cap D$. Combining the fact that $$|A\cap B\cap C\cap D|=100-|A^c\cup B^c\cup C^c\cup D^c|$$ where $A^c$ refers to $A$ ...
51
Consider when the runner passes the one-mile mark. If it is before 4:00 then he ran the first mile in less than 4 minutes. If it is after 3:59, then the second mile was covered in less than 4 minutes. But because 3:59 comes before 4:00 at least one of these cases (and possibly both) must be true.
49
If you add up all the injuries, there is a total of 310 sustained. That means 100 soldiers lost 3 limbs, with 10 remaining injuries. Therefore, 10 soldiers must have sustained an additional injury, thus losing all 4 limbs.
The manner in which you've argued your answer seems to me, logical, and correct.
46
If $x \geq 4$ and $y \geq 4$ then $x+y \geq 8.$
EDIT: on André's extra credit problem, use Beni's way of writing, time function $f,$ then define $g(m) = f(m+1) - f(m)$ with $0 \leq m \leq 1.$ We know $f(0) = 0, \; f(2) = 8.$ So, $g(0) + g(1) = 8.$ If both $g(0), g(1)$ are $4,$ we are done with André's problem. If one of the pair is above 4, ...
27
The comment by André Nicolas is related to a very pretty theorem that deserves to be much better known. I first came across it in R.P. Boas's Traveler's Suprises, which appeared in The Two-Year College Mathematics Journal, 10 no. 2 (1979), pp. 82-88 (though I read it in the reprint that appeared in the highly recommended Lion hunting and other ...
16
Nice problem! I almost hate to post a solution. If you like puzzles and haven't put in any time on this one yet, I encourage you not to read further.
Imagine writing the numbers in $A$ on a stack of cards, one number per card. We write the numbers of $B$ on a separate stack, again one per card. We then recursively define a sequence $s_j$ as follows:
...
12
take a chain of subsets of $A$, $\emptyset\subset\{a_1\}\subset\{a_1,a_2\}\subset...\subset A$. this chain has 101 elements. now sort them by their sum modulo 100. two of the sets in the chain must be equal modulo 100. hence there is $n>m$ with
$
(0+a_1+...+a_n)-(0+a_1+...+a_m)
$
divisible by 100, so that $a_{m+1}+...+a_n$ is divisible by 100.
here ...
11
Number the houses sequentially from 1 to 50. Define 5 pigeonholes using the house numbers (1, 6, 11, ..., 46), (2, 7, 12, ..., 47), ..., (5, 10, 15, ..., 50).
Since you are distributing 26 pigeons into these 5 pigeonholes, one of them receives at least 6 pigeons. Since there are 6 pigeons (i.e. 6 numbers are being chosen), it must be that two of them are ...
11
Suppose that the sums of sequences of three adjacent numbers in the circle are $s_1,s_2,\dots,s_{20}$. When you form the grand sum $s_1+s_2+\cdots+s_{20}$, in effect you’re adding up the numbers from $1$ through $20$ three times (why?), so you know the total. If all of the $s_k$ were less than $32$, what would the maximum possible total be?
11
Consider the numbers $a_1=1$, $a_2=11$, $a_3=111$, and so on. Let $r_1, r_2,r_3,$ and so on be the remainders when the $a_i$ are divided by $n$.
There are at most $n$ conceivable such remainders. So there must be two numbers $a_i$, $a_j$ such that $i\lt j$ and $r_i=r_j$. Their difference $a_j-a_i$ is divisible by $n$, and has only $0$'s and/or $1$'s. ...
9
You could model your case as follows: denote $f$ the time function, $f:[0,2] \to \Bbb{R}_+$, increasing, with $f(0)=0$, which shows the time at distance $x$. You know that $f(2)=7:59$.
If you suppose that $f(x+1)-f(x)\geq 4:00$ then $f(2)=f(2)-f(1)+f(1)-f(0) \geq 8:00$, and this is a contradiction.
9
For $\displaystyle 1 \le k \le 24$ you can definitely show that the master must have played exactly $k$ games on some set of consecutive days, using pigeonhole principle.
Suppose the total number of games the master has played till the end of day $\displaystyle j$ is $\displaystyle g_j$.
Now consider the $\displaystyle 154$ numbers: $\displaystyle g_1, ...
9
Note that three numbers $a\leq b\leq c$ are the sides of an acute triangle iff $a^2+b^2>c^2$. Suppose no triple of $d_i$ among $1< d_1,\leq \cdots\leq d_{12}< 12$ are the sides of an acute triangle. Then $1<d_1^2\leq \cdots \leq d_{12}^2<144$, and we have $1<d_1^2,1<d_2^2$ and $d_{i}^2+d_{i+1}^2\leq d_{i+2}^2$. But these last three ...
9
HINT: There are $9$ possible first digits, $1,2,\dots,9$, and $10$ possible fifth digits, $0,1,2,\dots,9$, so there are $9\cdot10$ possible combinations of first and fifth digits. If you have more than $9\cdot10$ twelve-digit numbers, ...
In other words, the pigeons are the $100$ numbers, and the boxes are the $9\cdot10$ possible combinations of first and ...
9
Start at a certain position and form sums of subsequences of length $1, 2, \dotsc, 101$ starting at that position and going in clockwise direction. This is an increasing sequence of $101$ numbers so there are two different entries that are equal $\bmod$ $100$ (end in the same two digits). The difference between those entries is a positive multiple of $100$ ...
7
Our set $A$ has $10$ elements, and therefore has $2^{10}=1024$ subsets.
The smallest conceivable subset sum is $0$ (the empty set) and the largest is $945$ ($90$ to $99$). So $A$ has no more than $946$ different subset sums. It follows by the Pigeonhole Principle that two of the subset sums of $A$ must be equal. Note that if $X$ and $Y$ are distinct ...
7
Some problems can be shown not to be solvable using the pigeonhole principle. For example, the nonexistence of a universal lossless compression algorithm (an algorithm that always compresses a string of characters into a shorter string of characters) can be shown to be impossible by using a pigeonhole argument that shows that two strings would have to be ...
7
Your answer is right. Think of it like this: How many people are free of not losing each limb? Make sure these people do not overlap, to create a group of people who are guaranteed to have at least one limb and to maximize the size of this group. The remaining people unfortunately do not have this "one limb is safe" guarantee. Calculate their percentage ...
6
Look at the pairs $(1,1997)$, $(2, 1996)$, and so on up to $(998,1000)$, together with the singleton $999$. These are the pigeonholes. Every number belongs to exactly one pigeonhole. If we choose $1000$ numbers, then since there are only $998$ pairs and $1$ singleton, at least $2$ of our numbers end up being in the same pigeonhole, that is, adding up to ...
6
Consider the numbers 1,11,111,...,111...11 (1 is repeated n+1 times). Since these are n+1 numbers we can use the pegionhole principle to deduce that 2 of them are congruent $modulo$ $n$. Find the absolute value of the difference between the 2 numbers that are congruent modulo n. The difference is made up of 1(s) and zeros. This number is also divisible by n. ...
6
That's a reasonable answer. I think my favorite way of viewing this question is to think of a complete graph on six vertices (i.e. each vertex is connected to each other vertex), where all edges are colored either red or blue. Then you are to show that there is either a red triangle or a blue triangle.
You could put your reasoning on this picture, as it ...
5
I don't really know how you would do this with the pidgeonhole principle. I would count how many numbers have no zeros, then how many numbers have 2 zeros (hint, it's 9), then use that to find how many numbers have 1 zero. Then you can use all of that information to get the total number of zeros.
There's a common theme when counting that it's sometimes ...
5
Let's proceed to the actual division :
$
\begin{array} {r|l}
\boxed{217}\hphantom{000\;} & 660\\
\hline
2170\hphantom{000} & 0.3287\\
-1980\hphantom{000} & \\
\boxed{190}\hphantom{00\;} & \\
1900\hphantom{00} & \\
-1320\hphantom{00} & \\
\boxed{580}\hphantom{0\;} & \\
5800\hphantom{0} & \\
...
5
This is number 17 of the introductory problems section in the book 102 Combinatorial Problems from the
training of the USA IMO team by Titu Andreescu and Zuming Feng.
Here is a paraphrase of their solution.
There are ${16\choose 2}=120$ pairs of numbers from $A$. Since
the absolute differences range from 1 to 99, there must be two different pairs
...
5
I think the simplest way would be to prove it wrong by assuming that the person is right.
The person claims:
2 miles are done in 7:59, but each mile of those two miles is done in at least 4 minutes. If the person disagrees at this point, then you do not have to prove anymore. Otherwise you have two miles, each not less than 4 minutes. Therefore, in total it ...
5
Here's a special case: If $k \leq n < 2k$ then $A_{k,n} = \{1, 2, \ldots, n\}$.
The OP has already shown that $A_{n,n} = \{1, 2, \ldots, n\}$, so let's assume $k < n < 2k$.
Start at the largest positive integer on the circle. Since $n > k$, this must be at least $2$. Let $s_j$, $1 \leq j \leq kn$, be the sum of the $j$ consecutive values ...
4
Follow-up, slightly too long for a comment: did some small experiments, and it appears (empirically) that $A_{k,2k}$ consists of exactly those integers having at least the $2$-adic valuation of $2k$ (e.g. $A_{6,12} = \{4,8,12\}$). The pattern holds up to $k\le 17$, after which my program takes more than a few minutes to run.
It seems things do get ...
4
Let the integers be $a_1\lt a_2\lt\cdots\lt a_{20}$, and let $b_1,b_2,\dots,b_{19}$ be given by $b_i=a_{i+1}-a_i$. Then $\sum_1^{19}b_i\le68$. But if you have $19$ positive integers, no one integer more than three times, then their sum must be at least $(1+1+1)+(2+2+2)+\cdots+(6+6+6)+7=70$. So some difference occurs at least $4$ times.
4
Consider the $n$ pairs $\{1,2n\}$, $\{2,2n-1\}$, $\{3,2n-2\}$, and so on up to $\{n,n+1\}$. The two numbers in each pair add up to $2n+1$.
If we choose $n+1$ numbers, then they cannot all belong to different pairs.
You can reword this in terms of pigeons. The pair $\{1,2n\}$ are a couple, with their own pigeonhole, as are $\{2,2n-1\}$, and so on up to ...
4
Call $i - p(i)$ an "even part" if $i$ is even and an "odd part" if $i$ is odd.
If both $i$ and $p(i)$ are odd for some $i$, then $i - p(i)$ is even, which causes $P(p)$ to be even. Since $n$ is odd, there are fewer even parts in the product (pigeonholes) than odd numbers in the set $\{1, \dots, n\}$ (pigeons). It follows that $p(i)$ is odd for at least one ...
Only top voted, non community-wiki answers of a minimum length are eligible
