Skip to main content
OlympiadHQ

Browse · MathNet

Print

69th Belarusian Mathematical Olympiad

Belarus counting and probability

Problem

Peter and Andrey play the game on the board, making moves alternate. Peter starts, and on his turn he places «+» to any empty cell. Andrey on his turn places «-» to any empty cell. The game is finished when all cells are filled. Peter's prize equals to the greatest number such that for each from 1 to there are successive cells, the amount of pluses on which is greater than the amount of minuses. Find the maximal prize which Peter can guarantee for himself.
Solution
Answer: .
Final answer
n + (-1 + (-1)^{n+1})/2

Techniques

Games / greedy algorithmsInvariants / monovariants