-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
211 lines (177 loc) · 9.87 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
<!DOCTYPE html>
<html lang="cs">
<head>
<base href="./" target="_blank">
<script src="panel.js"></script>
<script>Head('REU')</script>
</head>
<body onresize="Margin()">
<div class="inner" id="inner">
<h2>
About project
</h2>
<p>
<img class="fullobr" src="images/dimacs-logo.png" alt="DIMACS logo" title="DIMACS logo">
Research Experience for Undergraduates (REU) is a special program by DIMACS, Rutgers University,
which helps students to start their own research. It covers projects from math and theoretical
computer science to machine learning and bioinformatics.
</p>
<p>
Students from Charles University have participated this project since 1999. Group leader of this year is
<button class="innerlink" onClick="ClickOn('https://sites.google.com/view/gauravkucheriya/home')">
Gaurav Kucheriya
</button>. Other participants from Czech Republic are:
<button class="innerlink" onClick="ClickOn('http://reu.dimacs.rutgers.edu/~tc1005/')">
Tomáš Čížek
</button>, <button class="innerlink" onClick="ClickOn('http://reu.dimacs.rutgers.edu/~bd539/')">
Barbora Dohnalová
</button>, <button class="innerlink" onClick="ClickOn('http://reu.dimacs.rutgers.edu/~gg730/')">
Guillermo Gamboa
</button>, <button class="innerlink" onClick="ClickOn('http://reu.dimacs.rutgers.edu/~jk2089/')">
Jiří Kalvoda
</button>, <button class="innerlink" onClick="ClickOn('http://reu.dimacs.rutgers.edu/~kk1317/')">
Kyrylo Karlov
</button>, <button class="innerlink" onClick="ClickOn('http://reu.dimacs.rutgers.edu/~vk499/')">
Vova Kuznietsov
</button>, <button class="innerlink" onClick="ClickOn('http://reu.dimacs.rutgers.edu/~jm2972/')">
Josef Matějka
</button>, <button class="innerlink" onClick="ClickOn('http://reu.dimacs.rutgers.edu/~jp2274/')">
Jakub Petr
</button> and <button class="innerlink" onClick="ClickOn('http://reu.dimacs.rutgers.edu/~os274/')">
Ondřej Sladký
</button>.
</p>
<h2>
Division game
</h2>
<p>
This project is under supervision of
</button> and <button class="innerlink" onClick="ClickOn('https://sites.math.rutgers.edu/~narayanan/')">
Bhargav Narayanan
</button>. I collaborate with
<button class="innerlink" onClick="ClickOn('http://reu.dimacs.rutgers.edu/~tc1005/')">
Tomáš Čížek
</button>, <button class="innerlink" onClick="ClickOn('http://reu.dimacs.rutgers.edu/~vk499/')">
Vova Kuznietsov
</button> and <button class="innerlink" onClick="ClickOn('http://reu.dimacs.rutgers.edu/~os274/')">
Ondřej Sladký
</button>. The main goal of the project is to find a winning strategy in a game called Division game.
</p>
<h3>
Introduction
</h3>
<p>
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!
</p>
<h2>
Progress of research
</h2>
<h3>
Week 1
</h3>
<p>
We started thinking about our problem. At first, we solved some trivial examples.
We played various games manually and we were thinking about general behavior of the problem.
</p>
<h3>
Week 2
</h3>
<p>
We defined rank and we tried to describe the problem using ordering.
We made a lot of conjenctures, but most of them failed after we had finished a solver.
After a day of the lost hope, we came up with a conjencture that wasn't instantly disprooved via solver.
We also prooved a theorem about values of coins. Since that moment,
we could thinking just about distinct games with positive integer values.
We also tried to find upper bounds for games, but all estimations were
both true but useless, either useful but false.
</p>
<h3>
Week 3
</h3>
<p>
<img class="smallobr" src="images/lattice.png" alt="L(3,3)" title="L(3,3)">
We prooved our conjencture for a = 2. It was trivial, but we were too much
focused on general proof and we didn't think about that problem trivially. We
discovered two different branches research. Ondra Sladký tried prove a conjencture
by two-step induction. This leads to proof of case where a = 3. I tried study
a base structure of distinct games. This leads to a interesting problem in a lattice theory.
However it seems that it isn't a way how to prove our conjecture.
</p>
<h3>
Week 4
</h3>
<p>
We continued in proof of case a = 3. We had to deal with a lot of mistakes in algebraic manipulations.
We formulated and proved lemma about estimating games by given subset of coins. We finally proved
treshold lemma and pumping lemma.
</p>
<h3>
Week 5
</h3>
<p>
Proof of case a = 3 is mostly finished. Unfortunately, it seems that we cannot generalize this technique.
Bhargav sent us his notes to his proof of case a = 3. It looks like similar mess full of estimations.
I started to think about lattice from week 3. I found some literature that can be helpful in our
problem. General (n,n,C) game lattice (denoted like L(n, n)) is finite young lattice, so it has very nice properties.
L(1,n) is just linear order. We can get better estimations using finding downsets in lattices.
</p>
<h3>
Week 6
</h3>
<p>
We made a great deal of progress in lattices. Using a structure we call a cut, we are able to
do computer proving. We are using a lot of tools like linear programming and SAT solvers.
We can make a proof for n = 5 with this method.
We also read Bhargav's notes. He did similar things as we did, but he has a bit better bounds
and a bit less messy proof of case a = 3. We also fixed something we called Alice's massacre,
which says that most of Alice's strategies immidiately leads to that she will lose by induction.
There are only 2 valid strategies left.
</p>
<h3>
Week 7
</h3>
<p>
We found out, that we cannot prove division game using massacre, so we came up with a conjecture which says
treshold is changing only by one if game is played optimally. We extended massacre to cover changing a treshold,
but we got stuck on that now Alice still has 128 valid strategies.
</p>
<h3>
Week 8
</h3>
<p>
We decided to no longer continue in massacre and we focused on special types of games. We found a proof that Bob will
always win a game with two and three types coins. We were thinking again about games with doubled coins. Earlier,
we had a disproof to our conjecture that Alice can always draw this game for 14 coins. However, I was was trying
to understand what is going on in this case and I find out that there is probably problem with our solver.
I guess caching isn't going well since there are too much coins. We didn't have to explore this more, because we
ran out of time and we had to make our final presentation and return home right after that.
</p>
<h2>
Photos
</h2>
<p>
Photos from my journey across the US.
</p>
<button class="button" onClick="ClickOn('https://chwiedziuk.cz/foto/reu/index.html')">
REU photos
</button>
<h2>
Support
</h2>
<p>
<img class="microb" src="images/eu-flag.png" alt="flag" title="EU flag">
This project has received funding from the European Union’s
Horizon 2020 research and innovation programme under the Marie
Skłodowska-Curie grant agreement No 823748.
</p>
</div>
<script>Panel('REU')</script>
</body>
</html>