Tag Info

83

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

81

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

64

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 (\mod 100)$. Hence, 100 divides $a^2-b^2$. Here are the 22 squares mod 100: 0,1,4,9,16,21,24,25,29,36,41,44,49,56,61,64,69,76,81,84,89,96. ...

52

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.

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.

47

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

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

29

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

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: ... 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 ... 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 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. ... 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 ... 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 ... 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 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 ... 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 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 The squares of the board can be divided into six subsets, each one consisting of a NE-SW diagonal that wraps around the board if necessary. Mathematically, the jth subset (0\le j\le5) consists of those squares in the rth row and cth column such that r-c\equiv j\pmod 6. These subsets are pictured below. Since there are 13 rooks and 6 such subsets, ... 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, ... 8 Assume n points in the cube are each at distance at least 1 from the others. Then the balls of radius \frac12 centered at these points are disjoint. Their total volume is n times the volume \frac43\pi\left(\frac12\right)^3=\frac16\pi of a ball of radius \frac12. On the other hand every point in one of these balls is at distance at most \frac12 ... 8 Divide the 400 integers into 20 groups g_1\ldots g_{20}, where n\in g_i if i\le\sqrt n\lt i+1. That is:$$\begin{align} g_1 & = \{\mathbf{1}, 2, 3\} \\ g_2 & = \{\mathbf{4}, 5, 6, 7, 8\} \\ g_3 & = \{\mathbf{9}, 10, \ldots, 15\} \\ & \;\vdots \\ g_{19} & = \{\mathbf{361}, 362, \ldots, 399\} \\ g_{20} & = \{\mathbf{400}\} ...

8

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

For III, the Pigeonhole Principle will work nicely. Call the sectors, in counterclockwise order, $1$, $2$, $3$, $4$, $5$. Let $P_1$, $P_2$, and so on up to $P_5$ be the number of points in these sectors. Look at the sum $$(P_1+P_2)+(P_2+P_3) +(P_3+P_4) +(P_4+P_5)+(P_5+P_1)$$ which is the sum of the numbers of points in adjacent sectors. It is easy to ...

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

7

If there would exist such a configuration with all distances $>1$ one could place 1981 balls of radius ${1\over2}$ in a cube $Q$ of side length 10 (move all faces of the given cube ${1\over2}$ outwards). But these balls have a total volume of $1037.24\ldots\$. In fact the number $1981$ can be improved to $1415$: If there are $N$ points with mutual ...

7

As Ross and others have noted, your argument for 10 people is fine. To show that it's not possible to find two such groups out of 9 or fewer people, you should either exhibit a 9-person set that does not have two such subsets, or at least somehow prove that such a 9-person set exists. Unfortunately, according to a brute force computer search I ran, such a ...

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