MathDB

Sarah and Darah play the following game. Sarah puts

n

coins numbered with

1,\dots,n

on a table (Each coin is in HEAD or TAIL position.) At each step Darah gives a coin to Sarah and she (Sarah) let him (Dara) to change the position of all coins with number multiple of a desired number

k

. At the end, all of the coins that are in TAIL position will be given to Sarah and all of the coins with HEAD position will be given to Darah. Prove that Sarah can put the coins in a position at the beginning of the game such that she gains at least

\Omega(n)

coins. [hide="Hint:"]Chernov inequality!

Problem Statement