|
|
 |
Условие
Даны числа 1, 2, ..., N, каждое из которых окрашено либо в чёрный, либо в белый цвет. Разрешается перекрашивать в противоположный цвет любые три числа, одно из которых равно полусумме двух других. При каких N всегда можно сделать все числа белыми?
Решение
Если k – наибольшее чёрное число, то можно перекрасить тройку чисел (k – 2, k – 1, k) и далее действовать аналогично до тех пор, пока все числа, кроме, быть может, 1 и 2, не станут белыми.
Если число 2 после этого будет чёрным, то при N ≥ 8 перекрашиванием троек (2, 5, 8), (5, 6, 7) и (6, 7, 8) его можно сделать белым (цвет остальных чисел не изменится); затем, если нужно, можно изменить и цвет числа 1 (перекрасив тройки (1, 4, 7), (4, 5, 6) и (5, 6, 7)).
Случаи N = 1 и N = 2 очевидны, а для случаев 3 ≤ N ≤ 7 заметим, что чётность числа чёрных чисел, принадлежащих множеству {2, 3, 5, 6}, при перекрашиваниях не изменяется.
Поэтому, если первоначально число 2 – чёрное, а остальные – белые, то все числа белыми сделать нельзя.
Ответ
При N ≥ 8.
