Problem 6

Part of 2001 Mongolian Mathematical Olympiad

Problems(2)

marking cells on a board, maxmizing # of marked cells

Source: Mongolia MO 2001 Grade 10 P6

Some cells of a

10\times10

board are marked so that each cell has an even number of neighboring (i.e. sharing a side) marked cells. Find the maximum possible number of marked cells.

minimization of # of upset wins in tournament

Source: Mongolia MO 2001 Teachers P6

In a tennis tournament, any two of the

n

participants played a match (the winner of a match gets

1

point, the loser gets

0

). The scores after the tournament were

r_1\le r_2\le\ldots\le r_n

. A match between two players is called wrong if after it the winner has a score less than or equal to that of the loser. Consider the set

I=\{i|r_1\ge i\}

. Prove that the number of wrong matches is not less than

\sum_{i\in I}(r_i-i+1)

, and show that this value is realizable

combinatoricsgame