7

Part of 2014 Ukraine Team Selection Test

Problems(1)

k chips of two colors on cells of a nxn board

Source: Ukraine TST 2014 p7

For each natural

n \ge 4

, find the smallest natural number

k

that satisfies following condition: For an arbitrary arrangement of

k

chips of two colors on

n\times n

board, there exists a non-empty set such that all columns and rows contain even number (

0

is also possible) of chips each color.

combinatoricstableColoring