|
|
 |
Условие
Числа от 1 до 1000000 покрашены в два цвета – чёрный и белый. За ход разрешается выбрать любое число от 1 до 1000000 и перекрасить его и все числа, не взаимно простые с ним, в противоположный цвет. Вначале все числа были чёрными. Можно ли за несколько ходов добиться того, что все числа станут белыми?
Решение
Лемма. Пусть дан набор простых чисел p1, ..., pn. Тогда можно за несколько перекрашиваний добиться того, что поменяют цвет те и только те числа, которые кратны всем простые числа этого набора.
Доказательство. Для каждого непустого поднабора наших простых чисел перекрасим числа, не взаимно простые с произведением всех чисел этого поднабора.
Число, кратное всем числам набора, перекрашивалось при каждом таком перекрашивании, всего перекрашиваний было 2n – 1, следовательно, все эти числа перекрашены.
Пусть некоторое число k не делится хотя бы на одно из чисел набора, например, на p1. Тогда оно не перекрашивалось, когда
мы перекрашивали числа, не взаимно простые с p1. Остальные непустые поднаборы чисел можно разбить на пары следующим образом: поднабору, не
содержащему p1, в пару ставится поднабор, полученный из него
добавлением p1. При этом число k перекрашивается или при обоих перекрашиваниях пары, или ни при одном. Поэтому число k не будет перекрашено.
Первый способ. Для каждого набора простых чисел, произведение которых не больше 1000000, перекрасим числа, кратное всем этим простым числа.
По лемме такая операция возможна.
Докажем, что каждое число k при этом будет перекрашено. Пусть k имеет m различных простых делителей, тогда оно перекрашивалось при 2m – 1 операции, то есть нечётное число раз.
Второй способ. Назовём два числа эквивалентными, если у них совпадают наборы простых делителей. Заметим, что при наших операциях классы эквивалентности перекрашиваются целиком. Будем говорить, что один класс больше другого, если все простые делители второго класса являются делителями первого.
Из леммы следует, что мы можем перекрасить любой класс, перекрасив вместе с ним только большие классы.
Сначала перекрасим минимальные классы (класс называется минимальным,
если он не больше никакого другого класса). Исключим их из рассмотрения.
Среди оставшихся некоторые классы станут после такого исключения минимальными. При необходимости перекрасим их и тоже исключим. И так далее.
Поскольку классов конечное число, процесс закончится.
Ответ
Можно.
