Game replacing two numbers by mean

153 Views Asked by At

Alicia and Bart plays a game. Alicia first writes $100$ real numbers on the board. After that they move alternately; Bart goes first. In every move, the player chooses two numbers, erases them, and replaces both of them by their mean. If at any point, the numbers can be divided into two sets of $50$ numbers each such that the sums in both sets are equal, Bart wins.

Can Alicia prevent Bart from winning?

[Source: based on Hungarian competition problem]

1

There are 1 best solutions below

1
On BEST ANSWER

An equivalent question is to ask if Bob has a winning strategy. If Bob has a winning strategy, then Alicia cannot prevent Bob from winning.

I will define this in terms of "bubbles of size $n$" and "popping"

A bubble of size $2n$ will be a group of $2n$ numbers which can be separated into two groups, each of size $n$ such that their total sum is the same.

Blowing a bubble will be the action of on your turn choosing two numbers, neither of which are in a bubble.

Expanding a bubble (or combining bubbles) will be the action of combining a bubble with another one, accomplished by choosing two numbers from different bubbles.

Popping a bubble will be the action of changing the bubble in such a way that it would have decreased size, accomplished by choosing a number from a bubble and a number not from a bubble or by choosing two numbers from the same bubble. We will assume the worst case scenario most of the time and say that when a bubble popped, all numbers in the bubble were different. Notice that in doing so, a new bubble of size 2 is formed (namely the two numbers selected). Also note that this action of selecting two from the same bubble is not guaranteed to actually pop it, but we will assume that the numbers chosen will be chosen in such a way that it does.

Denote $S_2 = $the set of bubbles of size 2, $S_4 = $the set of bubbles of size 4, $S_6 = $ bubbles of size 6, $S_8 = $..., etc...

Denote $S = \cup S_{2i}$

Denote $|S_{2i}| =$ the number of bubbles of size $2i$

Denote $|S| = 2 |S_2| + 4 |S_4| + 6 |S_6| + \cdots 100 |S_{100}|$

Bob wins if at any point $|S| = 100$


On each of Bob's turns, he always chooses to "blow a bubble". In other words, he picks a vertex which is not an element of an element of $S$ and sets it equal to another element which is not an element of $S$. As a result, on every turn, $|S_2|$ is increased by one, causing $|S|$ to increase by 2.

On each of Alicia's turns, She has the following choices:

1: Blow a bubble, increasing $|S|$ by 2 (this only helps Bob accomplish his goal)

2: Expand a bubble, by taking elements from different bubbles. This does not change $|S|$. If the choices were from a bubble of size $2i$ and $2j$, the new bubble formed is of size $2(i+j)$.

3: Pop a bubble, by taking two elements from the same bubble or one from a bubble and one from outside of the bubble. If the bubble being popped is of size $2n$, this will decrease the size of $|S|$ by $(2n-2)$ (for the reason that when popping, a new bubble of size 2 is formed).

Notice that since Bob is not expanding any bubbles, for the amount that Alicia decreases the size of $|S|$ by to be positive, she must have spent a number of turns expanding bubbles. If the bubble being popped was of size 4, she needed to spend one turn combining two size2 bubbles and then popping, causing a net loss to $|S|$ of 2 over two turns. However, Bob will have increased $|S|$ by 4 in that same amount of time.

If the size of the bubble being popped was $2n$, it will have taken $n-1$ turns to expand a bubble to be of that size. Alicia spends the $n-1$ turns expanding the bubble and the $n$'th turn to pop it, providing a net loss to $|S|$ equal to $2n - 2$. During those $n$ turns however, Bob will have increased the size of $|S|$ by an amount equal to $2n$.

As a result, the hindrance that Alicia provides is never enough to completely hinder Bob's progress, and he will eventually win.


Additional details: Proof that expanding a bubble creates a new bubble and $|S|$ stays the same:

Suppose you have two bubbles, one of size $2n$ and another of size $2m$. Then the numbers in the first bubble can be written as $x^1_1, x^1_2, x^1_3,\cdots, x^1_n, y^1_1, y^1_2, y^1_3,\cdots,y^1_n$ with $\sum_{i=1}^{n} x^1_i = \sum_{i=1}^{n} y^1_i$ and the second bubble can be written as $x^2_1, x^2_2, x^2_3,\cdots, x^2_m, y^2_1, y^2_2, y^2_3,\cdots,y^2_m$ with $\sum_{i=1}^{m} x^2_i = \sum_{i=1}^{m} y^2_i$

We may assume that the two elements chosen are $x^1_1$ and $x^2_1$ (if not, then replace x's by y's and/or vice versa and reindex the numbers).

Then, $\frac{x^1_1 + x^2_1}{2} + \sum_{i=2}^{n} x^1_i + \frac{x^1_1 + x^2_1}{2} + \sum_{i=2}^{m} x^2_i = \sum_{i=1}^{n} x^1_i + \sum_{i=1}^{m} x^2_i = \sum_{i=1}^{n} y^1_i + \sum_{i=1}^{m} y^2_i$, satisfying the condition of being a bubble of size $2(n+m)$

Thus, there is one fewer bubble of size $2n$ and one fewer bubble of size $2m$, but one more bubble of size $2(n+m)$. So $|S| - 2n - 2m + 2(n+m) = |S|$

Tldr: Alicia cannot stop Bob from winning. Much of the credit goes to a classmate of mine who gave the idea of using bubbles to describe the scenario.