В каждой клетке таблицы
![$n\times n$ $n\times n$](https://dxdy-03.korotkov.co.uk/f/2/b/e/2be744f3276b5219af5f8dd5f793e02c82.png)
записано четное число. Можно ли все числа сделать нечетными в каждом из трех случаев:
а)
![$n=3$ $n=3$](https://dxdy-03.korotkov.co.uk/f/a/a/6/aa6905d780872f0007f642420d7a2d9c82.png)
, за 1-й шаг нужно изменить четность 2 чисел, за 2-й - у 2-х, за 3 - у трех и т.д.
б)
![$n=2013^{2142}$ $n=2013^{2142}$](https://dxdy-03.korotkov.co.uk/f/6/d/e/6dea3c4186bac3f6221c8f56ef62dbb482.png)
. За
![$j$ $j$](https://dxdy-04.korotkov.co.uk/f/3/6/b/36b5afebdba34564d884d347484ac0c782.png)
-й шаг нужно изменить четность
![$(n-1)^j$ $(n-1)^j$](https://dxdy-03.korotkov.co.uk/f/2/e/f/2ef0c255261ac0b7ef3e7dcc1298faba82.png)
чисел
в)
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
- произвольное натуральное. За
![$l$ $l$](https://dxdy-03.korotkov.co.uk/f/2/f/2/2f2322dff5bde89c37bcae4116fe20a882.png)
-й шаг надо поменять
![$l$ $l$](https://dxdy-03.korotkov.co.uk/f/2/f/2/2f2322dff5bde89c37bcae4116fe20a882.png)
чисел.
(Решение)
Будем называть числа, которые приобрели нечетность на каком-либо изпредыдущих шагов (и сейчас являются нечетными) - "старыми", а остальные - "новыми" (которые, возможно, ранее были нечетными). Опишем стратегию пункта в). За
![$1$ $1$](https://dxdy-01.korotkov.co.uk/f/0/3/4/034d0a6be0424bffe9a6e7ac9236c0f582.png)
-й шаг изменим любое число. На второй изменим 1 старое и одно новое число. На третий изменим 1 старое и 2 новых. Итого будет 2 нечетных. НА 4-й изменим 2 на 2. И в каждый последующий раз, на
![$2k$ $2k$](https://dxdy-04.korotkov.co.uk/f/f/1/7/f1738bbe3646e5962be59daa0aa34d5682.png)
-м шаге будем менять поровну старых и новых чисел, а на
![$2k+1$ $2k+1$](https://dxdy-04.korotkov.co.uk/f/f/c/3/fc30db31d93b89eaf5fc5090968e634a82.png)
- на 1 больше новых, увеличивая таким образом с каждый шагом на 1 число нечетных чисел. Но, в какой-то момент, оставшихся новых чисел будет меньше, чем
![$k$ $k$](https://dxdy-03.korotkov.co.uk/f/6/3/b/63bb9849783d01d91403bc9a5fea12a282.png)
(количество шагов предполагаемого достижения равно
![$m=2n^2+1$ $m=2n^2+1$](https://dxdy-03.korotkov.co.uk/f/a/9/1/a91f9bb6d9ed4ccd5e43457fc385322982.png)
). Поэтому, как только такое произойдет, изменим тактику: на четных шагах старим все новые, и обновляем оставшееся количество старых. На след. нечетном шаге старим обновленные и еще одно.
В пункте же б) у нас есть только 1 попытка (поскольку
![$(n-1)^2>n$ $(n-1)^2>n$](https://dxdy-03.korotkov.co.uk/f/a/d/6/ad63d49dea16488c84a8329a1bc13c7882.png)
при
![$n>2$ $n>2$](https://dxdy-03.korotkov.co.uk/f/2/a/9/2a9dfa29692859379213db21d3f8a1f482.png)
. Но, очевидно, что этого сделать не получится, посколько изменив 1 раз
![$n-1$ $n-1$](https://dxdy-03.korotkov.co.uk/f/e/f/c/efcf8d472ecdd2ea56d727b5746100e382.png)
число, а не
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
ничего путного не выйдет (одно-то останется).