Сколько всего шашек может быть на доске?

[Гость]

На квадратной доске 10×10 клеток расставлены шашки, причём во всех вертикалях стоит разное (возможно, нулевое) число шашек, и на всех горизонталях стоит разное (возможно, нулевое) число шашек. Сколько всего шашек может быть на доске?

[Гость]

Ответ: [tex]45[/tex] или [tex]55[/tex].

В каждой горизонтали от [tex]0[/tex] до [tex]10[/tex] шашек — это [tex]11[/tex] значений на [tex]10[/tex] горизонталей, значит, ровно одно значение [tex]k[/tex] пропущено и всего шашек [tex]0+1+\ldots+10-k=55-k[/tex]. То же для вертикалей, поэтому и там пропущено то же [tex]k[/tex].

Пусть [tex]k\ne 0[/tex] и [tex]k\ne 10[/tex]. Тогда есть полная горизонталь (в каждой вертикали хотя бы одна шашка) и пустая горизонталь (в каждой вертикали не больше [tex]9[/tex] шашек). Значит, у вертикалей всего [tex]9[/tex] возможных значений [tex]1,\ldots,9[/tex] на [tex]10[/tex] вертикалей — противоречие. Остаются [tex]k=0[/tex] (всего [tex]55[/tex]) и [tex]k=10[/tex] (всего [tex]45[/tex]).

Оба случая возможны: заполним клетки [tex](i,j)[/tex] с [tex]i+j\le 11[/tex] — в горизонталях и вертикалях будет [tex]10,9,\ldots,1[/tex] шашек, всего [tex]55[/tex]. Если теперь поставить шашки во все пустые клетки, а эти убрать, получим [tex]0,1,\ldots,9[/tex], всего [tex]45[/tex].