LET BOB COOK!!!
Разница между en2 и en3, 1589 символ(ов) изменены
Finally, justice has been served to Bob!! 😭↵
↵
In [2272F — Tree Reduction Game](https://codeforces.me/contest/2272/problem/F), Alice still gets the first move, but Bob finally gets some compensation: he can choose the initial root of the tree!↵
↵
With the right choice, Bob can guarantee his victory even when playing second. No more suffering from always going second — **Bob is finally getting his chance to shine!**↵
↵
Come on, Bob, you got this! 🗿
↵
↵
Upd: Bob really cooked this game. =DD↵
<br>↵
After a lot of research, the result surprised me↵
↵
<spoiler summary="chart:">↵
n is the number of nodes in the tree↵
↵
|n|samples|bob wins|alice wins|bob win rate|↵
|-------|-----|-----------|-----|-----------|↵
|2|1000|0|1000|0%|↵
|3|1000|1000|0|100%|↵
|4|1000|0|1000|0%|↵
|5|1000|1000|0|100%|↵
|6|1000|282|718|28.2%|↵
|7|1000|1000|0|100%|↵
|8|1000|463|537|46.3%|↵
|9|1000|1000|0|100%|↵
|10|1000|629|371|62.9%|↵
|11|1000|1000|0|100%|↵
|12|1000|735|265|73.5%|↵
|13|1000|1000|0|100%|↵
|14|1000|805|195|80.5%|↵
|15|1000|1000|0|100%|↵
|16|1000|875|125|87.5%|↵
|17|1000|1000|0|100%|↵
|18|1000|905|95|90.5%|↵
|19|1000|1000|0|100%|↵
|20|1000|934|66|93.4%|↵
|21|1000|1000|0|100%|↵
|22|1000|955|45|95.5%|↵
|23|1000|1000|0|100%|↵
|24|1000|967|33|96.7%|↵
|25|1000|1000|0|100%|↵
|26|1000|970|30|97%|↵
|27|1000|1000|0|100%|↵
|28|1000|979|21|97.9%|↵
|29|1000|1000|0|100%|↵
|30|1000|989|11|98.9%|↵
|....|....|....|....|....|↵
|90|1000|1000|0|100%|↵
|91|1000|1000|0|100%|↵
|92|1000|1000|0|100%|↵
|93|1000|1000|0|100%|↵
|94|1000|1000|0|100%|↵
|95|1000|1000|0|100%|↵
|96|1000|1000|0|100%|↵
|97|1000|1000|0|100%|↵
|98|1000|1000|0|100%|↵
|99|1000|1000|0|100%|↵
|100|1000|1000|0|100%|↵
</spoiler>↵
↵
It is easy to see that when n is odd, Bob always wins. If n is even, Bob's win rate increases gradually until it reaches 100%, regardless of the number of nodes (I tested n up to $10^5$).↵
↵
<spoiler summary="proof:">↵
If anyone has found any proofs for this "interesting thing", feel free to share them in the comment, I will add them here. :)↵
</spoiler>↵
↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский __Dangcoder__ 2026-10-29 15:11:38 1589 Tiny change: ' &#128511;' -> ' &#128511;\n\n<spoiler summary="hi">\n...\n</spoiler>'
en2 Английский __Dangcoder__ 2026-10-28 13:25:30 62
en1 Английский __Dangcoder__ 2026-10-26 19:50:09 497 Initial revision (published)