General Information

---

Project Description

• There are 2N gold coins sitting on a table, of different weights. Alice and Bob know all the weights, and they are going to split these coins up between themselves so they each get N coins. The way they will do so is as follows. Alice first picks a coin on the table, say x, Bob chooses who gets to keep x (him or Alice). Then Bob picks another coin y on the table, now Alice chooses who gets to keep y, and so on back and forth, until one player has N coins, at which point all the remaining coins go to the other player. Each player wants to maximise the sum of the weights of the coins that they get. It seems to be true, but we don’t yet know how to prove, that Bob is always better off than Alice in this game!

Research Log

Week 1 (06/01-06/02)

We became familiar with the definition of our problem and its basic properties. First, we showed results of trivial instances of the problem, e.g. of a game with only two coins or a game with an infinitely large coin. Then, we proved that Bob is always better on so-called mirrored games, which are games with coins that are symmetrically distributed around their total mean.

Week 2 (06/05-06/09)

We generalized the definition of the original problem to so-called (a,b)-games where a and b are sizes of Alice's and Bob's buffer, respectively. This allows us to use proofs by induction more conveniently. We showed results for special cases here as well, e.g. for a = 1 or b = 1.

We came up with a concept of ranks that we used to state a conjecture stronger than the original one. After finishing a simple solver, we disproved this conjecture easily. Then, we formulated several other conjectures which also turned to be false. Finally, we formulated a conjecture that Alice's sum of coins on an (a,b)-game is less than or equal to Bob's sum of coins on a (b,a)-game with the same set of coins. For this, we showed that the validity of cases with an odd number of coins implies cases with an even number of coins.

Week 3 (06/12-06/16)

We proved the last conjecture about the sums of coins for the case a = 2. Then, we stated Pumping and Threshold lemma that could help us proving the case for a = 3. Using these, Ondra S. constructed a program that is able to eliminate most of the possible strategies that Alice can play simultaneously in (a, b, C) and (b, a, C) games. After exploring the remaining strategies, we proved that the conjecture also holds for the case a = 3.

Week 4 (06/19-06/23)

Unfortunately, we found mistakes in our proof for a = 3. We were able to fix them by taking a slightly different approach. We also started rewriting our notes of everything we did so far. At the end of the week, we also formally proved the Pumping and Threshold lemma.

Week 5 (06/26-06/30)

After finishing the revision of our notes, we found other algebraic mistakes in our proof for a = 3. We are not able to fix the proof for all the possible settings of Alice's threshold and we also cannot imagine how to generalize our approach for other values of a. We are now studying notes that our mentor sent us to the problem and we are trying to come up with new ideas.

Week 6 (07/03-07/07)

We finished reading of our mentor's notes that contain similar ideas to ours except for better bounds and proof for a = 3. Then, we returned to the concept of lattices which allowed us a more general view on properties of games. Using cut on lattices, we were able to reduce the number of games that need to be verified by a solver for a given number of coins. This led to a computer proof for up to 10 coins.

We also proved the main conjecture for two types of coins and disproved our conjecture that Bob can draw duplicated games by stealing strategies.

Week 7 (07/10-07/14)

We tried to revise our "Massacre of Alice's strategies" to prove the main conjecture. Unfortunately, we found out that there exist games where Alice can win if Bob uses the same threshold as Alice did in the first round. Therefore, we had to generalize our massacre so that Bob considers more settings of the threshold. However, too many strategies remained preventing us to prove the conjecture.

Week 8 (06/17-07/21)

We proved the case with at most three types of coins. Then, we completed our notes and prepared the final presentation. At the end of the week, we returned to Prague.

Week 9 (06/24-07/28)

We participated in the continuation of the REU program in Prague. We also finalized our paper concluding our research project.

Acknowledgements

This work was carried out while the author Tomáš Čížek was a participant in the 2023 DIMACS REU program, supported by CoSP, a project funded by European Union’s Horizon 2020 research and innovation programme, grant agreement No. 823748.