Республиканская олимпиада по математике, 2000 год, 9 класс

Столбцы и строки таблицы $n\times n$ занумерованы числами от $1$ до $n$. В каждой клетке таблицы записывается одно из чисел $1$ или $-1$.
а) Найдите все $n$, для которых можно записать числа в таблицу так, чтобы произведения чисел любой строки и столбца, с одинаковыми номерами, были различными.
б) Для всех таких $n$ (удовлетворяющих условию а)), определить наименьшее возможное количество чисел, равных $-1$.

Комментарий/решение

а) Пусть $n=2k$, тогда запишем в последний столбец только $-1$, а в остальные $+1,$ тогда произведение чисел в любом столбце будет равно $1$, в то время как произведение чисел в любой строке будет равняться $-1$, условие выполняется.

Пусть теперь $n=2k+1$, рассмотрим количество чисел $-1$, не включая тех, что расположены на главной диагонали. Пусть их количество $=S$. Заметим, что для любого столбца и строки, убрав общую клетку, получим, что произведения оставшихся чисел строки и столбца будут отличаться в любом случае, $\Rightarrow S_i=$ нечетное. Делая аналогичные команды для других номеров таблицы $2k+1$ $\times$ $2k+1$ получим, что $S=\frac{\sum \limits_{i=1}^{2k+1}{S_i}}{2}$, поскольку каждое число $-1$ считаем дважды, но $S$ - целое, противоречие

б) Для любого столбца и строки найдется хотя бы $1$ число $-1$, и это число задействовано в другом столбце/строке $1$ раз, $\Rightarrow$ Количество $-1\geq2k/2=k$, где $n=2k$ Пример для k:

$-1$ ставим на $2i$-ый столбец, $2i-1$-ую строку для каждого $i \in k$