Problem #PRU-98431

Problems Set theory and logic Algorithm Theory Game Theory Game Theory Combinatorics Dissections, partitions, covers and tilings Tilings with ordinary and domino tiles

Problem

A game takes place on a squared \(9 \times 9\) piece of checkered paper. Two players play in turns. The first player puts crosses in empty cells, its partner puts noughts. When all the cells are filled, the number of rows and columns in which there are more crosses than zeros is counted, and is denoted by the number \(K\), and the number of rows and columns in which there are more zeros than crosses is denoted by the number \(H\) (18 rows in total). The difference \(B = K - H\) is considered the winnings of the player who goes first. Find a value of B such that

1) the first player can secure a win of no less than \(B\), no matter how the second player played;

2) the second player can always make it so that the first player will receive no more than \(B\), no matter how he plays.