정수 \( n\ge 2\)에 대하여, $ n^2$개의 단위 정사각형으로 이루어진 $n\times n$ 체스판 위에 $n$개의 체스말이 놓여 있고 각각의 체스말은 단위정사각형 안에 놓여 있다. 체스판의 각 행과 열에 체스말이 정확히 하나씩 포함되어 있을 때, $n$개의 체스말이 놓인 형태를 ‘좋은’ 형태라고 부르자. 다음의 조건을 만족하는 양의 정수 $k$의 최댓값을 구하여라:
(조건) 모든 좋은 형태에 대하여, 어떠한 체스말도 포함하지 않는 ($k^2$의 단위정사각형으로 이루어진) $k\times k$ 정사각형 블록이 존재한다.
$n\times n$ 모양의 체스판이 있다. 체스판에 있는 $n^2$개의 정사각형 칸 각각에는 $0$부터 $k$까지의 번호 중 하나가 나타나도록 되어 있다. 체스판의 각 행, 각 열에는 버튼이 하나씩 있는데, 버튼들 중 하나를 한번 누를 때마다 그 행(또는 그 열)에 있는 $n$개의 정사각형 칸에 나타나 있던 번호가 모두 $1$씩 늘어난다. 단, 나타나 있던 번호가 $k$인 경우는 $0$으로 바뀐다. 이렇게 버튼을 누르는 행위를 `시행’이라고 하자. 처음에는 $n^2$개의 정사각형 칸에 모두 $0$이 나타나 있었으나, 지금은 몇 번의 시행을 거쳐 번호들이 바뀐 상태이다. 지금 상태가 어떤 상태이든, $kn$번 이하의 시행으로 모든 칸의 번호가 다 $0$인 처음의 상태로 만들 수 있음을 보여라.
(2008년 3월 23일, 출처4시간 30분)