# Tag Info

88

Look at your $52$ integers mod $100$. Look at the pairs of additive inverses $(0,0)$, $(1,99)$, $(2,98)$, etc. There are $51$ such pairs. Since we have $52$ integers, two of them must belong to a pair $(x,-x)$. Then $x^2 - (-x)^2 = 0 \pmod{100}$, so that the difference of their squares is divisible by $100$.

83

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$ ...

67

Only 23 numbers are needed. There are only $22$ squares mod $100$, so if you have $23$ integers, two must be yield the same square mod $100$. That is, you must have two different values, $a$ and $b$, such that $a^2 \equiv b^2 \pmod {100}$. Hence, $100$ divides $a^2-b^2$. Here are the $22$ squares : ...

53

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.

52

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

Pick two distinct points out of your 5 (if all 5 are identical then they clearly all lie in a single hemisphere). These two points define at least one great circle (if they're antipodal, they define infinitely many); pick a great circle they define. This circle then cuts the sphere into two hemispheres. Now pigeonhole the other three points between these ...

47

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, ...

37

Every square is congruent to either $0$ or $1$ modulo $4$. Also, there are $11$ distinct squares modulo $25$. By the Chinese remainder theorem, there are only $2\cdot11=22$ distinct squares modulo $100$. So the $52$ in the problem can be improved to $23$.

30

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 ...

29

As the wikipedia article describes, Dirichlet's approximation theorem is a foundational result in diophantine approximation. For a real number $x$, let $\|x\|$ denote the distance from $x$ to its closest integer. Then the theorem states that for any irrational number $\alpha$, there exists infinitely many $q \gt 0$ such that $$\| q\alpha \| \leqslant ... 28 Given five points on a sphere, there is a closed hemisphere containing at least four of them. 21 One fairly interesting result is that it is impossible to create a lossless data compression algorithm that shortens every input file. If it is lossless, it must actually make some files longer. The proof of this is outlined very nicely on wikipedia. 21 Look at the extended diagonals, which I’ve numbered from 1 through 8 in the diagram below:$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline 1&2&3&4&5&6&7&8\\ \hline 2&3&4&5&6&7&8&1\\ \hline 3&4&5&6&7&8&1&2\\ \hline 4&5&6&7&8&1&2&3\\ \hline ...

17

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: ...

15

One application that I like involves the case when $m$ is finite, but $n = \infty$. It will require a certain level of maturity for your students to appreciate this case of the principle, but (for me) the appeal is that it takes what looks like a very discrete math/combinatorical principle, and allows one to apply it to apparently quite different areas. ...

14

This is a cute application of pigeonholing. Find the size of the largest subset $A$ of $\{ 1,2 ,\ldots, 2n \}$ satisfying the following condition: if $a$ and $b$ are distinct elements of $A$, then $a$ does not divide $b$. After some thought, one can come up with the example $A = \{ n+1, n+2, \ldots, 2n \}$ containing $n$ elements. But is this the best ...

14

In 26 integers, by Pigeonhole Principle you have at least two whose difference is zero when divided by 25. In 52 integers you have at least 3 such integers. Pick those three integers. Again, by Pigeonhole, two of them will have the same parity. Let them be $a$ and $b$. Thus $2|(a+b)$ and $2|(a-b)$ as such $4|(a+b)(a-b)$. Since 25|(a+b)(a-b) also and 4 and 25 ...

13

I'm not sure where it is that you're getting that formula. It seems to me like it was the application of the Pigeonhole Principle to a different question. The Pigeonhole Principle states—in laymen's terms—that if you have $N + 1$ objects and $N$ places to put them, then there must be at least one place that has more than one object. Here, we ...

12

Break the equilateral triangle into four smaller triangles by joining the midpoints of the sides. Now we have four holes and five pegions hence three must be at least one triangle which contains at least two points. The distance between the two points cannot exceed the side of the triangle.Also the side of the triangles formed is $\frac1{2}$ and the result ...

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 ...

12

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. ...

11

This can be used to prove that the decimal form of a rational number either terminates or recurs (apply to the remainders).

11

Every graph with two or more vertices has two vertices with the same degree.

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?

10

Proof by contradiction: If he/she had needed more than (or exactly) 4 minutes for the first and for the second mile, then he/she would have needed more than (or exactly) 8 minutes for both.

10

Here's Dedekind's definition: A set $S$ is said to be infinite if there is an injection from $S$ to one of its proper subsets. There is a hidden other half implied by this definition, namely that a finite set is one that is not infinite. One might imagine that it also says: A set $S$ is said to be finite if there is no injection from $S$ to any of ...

10

Let $S$ be a set consisting of ten distinct positive integers, each of them less than or equal to $100$. How many subsets does $S$ have? How big can the sum of the elements of $T$ possibly get, for any subset $T\subseteq S$? By showing that $S$ has more subsets than possible sums-of-subsets, the pigeonhole principle then tells you that there are two ...

10

** In a group of six people, there will always be three people that are mutual friends or mutual strangers. ** (Assume that “friend” is symmetric-if x is a friend of y, then y is a friend of x.) The problem can be thought of geometrically. Imagine the six people as points and let an edge between points indicate friendship. No matter how the graph is drawn, ...

10

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 ...

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