General Information
| Student: | Volodymyr Kuznietsov |
|---|---|
| Office: | CoRE 446 |
| School: | Faculty of Mathematics and Physics, Charles University |
| Contact: | kuzvladim7@gmail.com |
| Project: | Division Game |
| Collaborators: | O. Chwiedziuk, T. Cizek and O. Sladky. |
| Mentor: | Bhargav Narayanan |
I am a part of a group of students from Charles University that includes Ondrej Chwiedziuk, Barbora Dohnalova, Jiri Kalvoda, Kyrylo Karlov, Gaurav Kucheriya, Tomas Cizek, Josef Matejka, Jakub Petr, G.A. Gamboa Quintero and Ondrej Sladky.
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)
- Considered trivial cases, like game with only two and four coins and game with coin of infinite weight. Also, proved the statement for mirrored games, i.e. such games where coins' weights are symmetrically distributed around their total mean.
Week 2 (06/05-06/09)
- We tried to think on a little harder concept, called an (a, b)-game, where Alice needs to pick a coins and Bob needs to pick b coins. The results for a = 1 or b = 1 were trivial.
- After some false conjectures, we came up with conjecture that Alice's sum of coins in (a, b)-game is less than or equal to Bob's sum of coins in (b, a)-game with the same set of coins. For this was shown that cases with odd number of coins imply cases with even number of coins..
Week 3 (06/12-06/16)
- We proved the last conjecture about the sums of coins for cases when a = 2 or b = 2 and for a = 3 or b = 3.
Week 4(06/19-06/23)
- Tried to prove a conjecture for larger a, but could not succed at it. Also, we have found some small mistakes in the proof for a = 3, which we menaged to fix.
Week 5(06/26-06/30)
- Spent time on proof of a = 3. Could proof the case when Alice's threshold is not among the middle four values. Could not cover all possible responses. Also, I had a trip to Philadelphia.
Week 6(07/03-07/07)
- We came up with new idea - lattices. Could prove some small comjectures about them, but nothing important. Also, we finished reading Bhargav's notes, so we understood a proof for a = 3. Also, I had a great time on 4th July at Philadelphia.
Week 7 (07/10-07/14)
- We again took a look on lattices, defined the cuts and using computer we were able to proof the theorem for at most 10 coins. We focused again on "massacre of Alice's strategies" 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.
Week 8 (07/10-07/14)
- Proved the case with at most three types of coins and also started preparing our final presentation. Also, in the end of the week, we had a first live meeting with Bhargav.
Acknowledgements
- This work was carried out while the author Volodymyr Kuznietsov 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.