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!

esearch Log

Week 1 (01/06-02/06)

We proved the theorem for a special class of games -- mirrored games. We proved the theorem for other special cases and disprooved several conjectures we had. We considered the generilization of the problem to cases where the two players take non necesarilly the same number of coins and we found out closed formulas for the result for games in which Alice or Bob take only one coin.

During the weekend we visited New York, to see the Statue of Liberty and a musical on Broadway.

Week 2 (05/06-09/06)

We had our initial presentation. We formulated a conjecture about ranks that is stronger than the original conjecture. Later we disproved the conjecture and formulated its weaker version about sums of pair a,b and b,a games. We proved induction step from odd to even.

We visited Baltimore and Washington D.C.

Week 3 (12/06-16/06)

We attended the Workshop on Modern Techiniques in Graph Algorithms. We proved the conjecture about sums for a=2. We formulated intuitive lemmata about threshold -- if a player keeps a coin in an optimal strategy they want to keep all the coins with higher value in the same situation -- and about exchanging a coin for a one with higher value. With this all Alice's optimal strategies fall into one of 256 categories and using computer we've shown that if Alice can win, her strategy must fall into only 6 out of these 256 categories. At the end of the week using all this we were able to prove the conjecture about sums for a=3.

We again visited New York.

Week 4 (19/06-23/06)

We spent the beginning of the week trying to generalize the proof for larger a. Later during the week, when we tried to formally write the proof for a=3, it turned out that there were several of by one errors in some of the algebraic manipulations which were part of the proof. We were able to fix some of them using a different idea for the proof.

We visited Philadelphia.

Week 5 (26/06-30/06)

We spend time on the proof for a=3. After fixing other mistakes in algebraic manipulations, we were able to get the proof for cases when Alice's threshold is not among the middle four values. Unfortunately we were not able to cover those in all cases of Alice's possible responses.

We went for a round trip to Canada, mostly to see Niagara Falls and Toronto.

Week 6 (03/07-07/07)

We read Bhargav's notes on the problem. We then focused on lattices of solutions, trying to think about playing Division game on these lattices. We proved the theorem for two types of coins and disproved conjecture about games with duplicated coins.

Week 7 (10/07-14/07)

We continued the work on lattices, defined the cuts and using computer we were able to proof the theorem for at most 10 coins. At the end of the week we focused again on "massacre of Alice's strategies" (our original approach to case with a=3) as we realized that it could be simplified. Unfortunately this was without a success as we were able to proof that Bob is not fine with setting his threshold the same as Alice's, on which the massacre relied. We generalized massacre, but unfortunately too many Alice's strategies survived and we were not able to do any progress with it.

We once again visited New York to see The Book of Mormon on Broadway.

Week 8 (10/07-14/07)

We spent the week mostly by wrapping our notes up, and by preparing our presentation. We proved the case with at most three types of coins. We had our final presentation.

We once again visited New York to see The Book of Mormon on Broadway.

Acknowledgements

This work was carried out while the author Ondřej Sladký 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.