A group of $100$ kids has a deck of $101$ cards numbered by $0, 1, 2,\dots, 100$. The first kid takes the deck, shuffles it, and then takes the cards one by one; when he takes a card (not the last one in the deck), he computes the average of the numbers on the cards he took up to that moment, and writes down this average on the blackboard. Thus, he writes down $100$ numbers, the first of which is the number on the first taken card. Then he passes the deck to the second kid which shuffles the deck and then performs the same procedure, and so on. This way, each of $100$ kids writes down $100$ numbers. Prove that there are two equal numbers among the $10000$ numbers on the blackboard.
Problem
Source: All-Russian MO 2023 10.2, 11.2
Tags: combinatorics, Average, ilostthegame
24.04.2023 14:57
Consider the pattern $0,101,2,99,3,98,\ldots,50,51$. Every other sum has an average of $50.5$. At some point this pattern will be attained as each kid runs through all possible combinations of cards in the $100 \cdot 100 = 10000$ numbers.
25.04.2023 05:14
Quidditch wrote: A group of $100$ kids has a deck of $101$ cards numbered by $0, 1, 2,\dots, 100$. The first kid takes the deck, shuffles it, and then takes the cards one by one; when he takes a card (not the last one in the deck), he computes the average of the numbers on the cards he took up to that moment, and writes down this average on the blackboard. Thus, he writes down $100$ numbers, the first of which is the number on the first taken card. Then he passes the deck to the second kid which shuffles the deck and then performs the same procedure, and so on. This way, each of $100$ kids writes down $100$ numbers. Prove that there are two equal numbers among the $10000$ numbers on the blackboard. Consider the numbers $49.5, 50, 50.5$. At least 2 of them will appear as the last average. At least 2 of them will appear as the first card/average of first 2 cards (these are in the form $\frac{n}{2}$ where $0\le n\le 200$). Hence contradiction.
24.07.2023 03:03
hahahahahahhahahahahahahahahahhahahahahahaha Suppose that the numbers are all distinct. The first and second averages written for each kid are clearly of the form $\frac{k}{2}$, where $0 \leq k \leq 200$. The $100$-th average is solely based on the last card in the shuffle order, so there are exactly $101$ possible averages that can be written down last. Therefore, among the $100$ averages actually written last, at least two of $\frac{5050-0}{100}=\frac{101}{2},\frac{5050-50}{100}=\frac{100}{2},\frac{5050-100}{2}=\frac{95}{2}$ must appear. Hence, combining with this with the $200$ distinct averages written first and second, we find that there should be at least $202$ distinct averages of the form $\frac{k}{2}$. But clearly we must have $0 \leq k \leq 200$, so there are only $201$ possibilities—contradiction. $\blacksquare$
31.03.2024 13:03
OK, I'm fairly sure this isn't a fakesolve by it's different from the above ones. Assume that all the 10000 numbers were distinct. We look at the numbers on the cards as set of natural numbers. Let the set \[A_n=\{a_{n,0},a_{n,1},\dots,a_{n,100}\}\]be the set of the numbers on the cards of the $n^{\text{th}}$ kid in the order in which they appeared. We now have two cases to explore. Case 1 : There exists $i\in\{0,1,2,\dots,100\}$ such that $a_{i,100}=50$. In this case note that, \[\frac{a_{i,0}+a_{i,1}+\dots,a_{i,99}}{100}=\frac{0+1+\dots+49+51+\dots+100}{100}= 50\]Thus, the number 50 is written on the blackboard (as the last number of the list of the $i^{\text{th}}$ kid.) Note that one of 0 and 100 must also be in the set $\{a_{1,100},a_{2,100},\dots,a_{100,100}\}$ (since this set has 100 numbers among $0,100$). Thus, one of $\frac{101}{2}$ (if 0 is in this set) or $\frac{99}{2}$ (if 100 is in this set) is written as the last number of the list of some student (the average of all numbers besides the last). Now, this means that 50 cannot be written on the top (first) card of any of the 100 kids (since then his list of numbers will start with 50). So, the first numbers of the 100 students (which clearly must be distinct since the lists of each kid starts with the number on the top card). So, the numbers $0,1,\dots,100$ are all written in the list of some student (all number except 50 as a starting number and 50 as the last number of the $i^{\text{th}})$ student. This means, the second number of the list of each student (which is of the form $\frac{a}{2}$ for some natural number $1\leq a \leq 199$) cannot be a whole number. Thus, the only possible values for this list are $\frac{1}{2} , \frac{3}{2} , \dots , \frac{199}{2}$, which includes 100 numbers. But, one of $\frac{101}{2}$ and $\frac{99}{2}$ is in fact invalid, which implies that we have at most 99 valid numbers for the set $\{a_{1,2},a_{2,2},\dots,a_{100,2}\}$ which is a clear contradiction. Case 2 : There does not exist $i\in\{0,1,2,\dots,100\}$ such that $a_{i,100}=50$. Thus, the set of last card numbers $\{a_{1,100},a_{2,100},\dots,a_{100,100}\} = \{0,2,\dots,49,51,\dots,100\}$. Now, the set of first numbers, $\{a_{1,1},a_{2,1},\dots,a_{100,1}\}$ consists of 100 whole numbers and thus, 100 natural numbers are written on the blackboard (as the average of the first number of each student). So, the $\{a_{1,2},a_{2,2},\dots,a_{100,2}\}$ can include at most 1 whole number. Further, this set cannot include $\frac{101}{2}$ nor $\frac{99}{2}$ as we established above that both $0,100$ are a last card number of some student. Thus, this set can include numbers of the form $\frac{a}{2}$ for all odd $a=1,3,\dots,97,103,\dots,199$ (98 possibilities) and one number of the form $\frac{a}{2}$ for even $a$. This means a total of 99 possibilities which is a contradiction since we need 100 numbers. Thus, we have exhausted all cases and indeed our assumption must have been false. Thus, there are two equal numbers among the $10000$ numbers on the blackboard as desired.