Разделы 
Дополнительно
Задача по математике - 1904
2019-01-21 
Числа от 1 до 1000000 покрашены в два цвета - черный и белый. За ход разрешается выбрать любое число от 1 до 1000000 и перекрасить его и все числа, не взаимно простые с ним, в противоположный цвет. Вначале все числа были черными. Можно ли за несколько ходов добиться того, что все числа станут белыми?
Решение:
Лемма. Пусть дан набор простых чисел $p_1, \cdots , p_n$. Тогда можно за несколько перекрашиваний добиться того, что поменяют цвет те и только те числа, которые делятся на все простые числа набора.
Доказательство. (формула включения-исключения). Для каждого непустого поднабора наших простых чисел перекрасим числа, не взаимно простые с произведением всех чисел этого поднабора. Число, делящееся на все числа набора, перекрашивалось при каждом таком перекрашивании, всего перекрашиваний было $2^n - 1$, следовательно, числа, делящиеся на все числа набора, перекрашены. Пусть некоторое число $k$ не делится хотя бы на одно из чисел набора, например, на $р_1$. Тогда оно не перекрашивалось, когда мы перекрашивали числа, не взаимно простые с $р_1$. Остальные непустые поднаборы чисел можно разбить на пары следующим образом: поднабору, не содержащему $р_1$, в пару ставится поднабор, полученный из него добавлением $р_1$. При этом число $k$ перекрашивается или при обоих перекрашиваниях пары, или ни при одном. Поэтому число $k$ не будет перекрашено.
Лемма доказана.
Первое решение. Для каждого набора простых чисел, произведение которых не больше 1 000 000, перекрасим числа, делящиеся на все эти простые числа. По лемме такая операция возможна. Докажем, что любое число $k$ при этом будет перекрашено. Пусть $k$ имеет $m$ различных простых делителей, тогда оно перекрашивалось при $2^m - 1$ операции, т. е. нечетное число раз.
Второе решение. Назовем два числа эквивалентными, если у них совпадают наборы простых делителей. Заметим, что при наших операциях классы эквивалентности перекрашиваются целиком. Будем говорить, что один класс больше другого, если все простые делители второго класса являются делителями первого. Из леммы следует, что мы можем перекрасить любой класс, перекрасив вместе с ним только большие классы.
Сначала перекрасим минимальные классы (класс называется минимальным, если он не больше никакого другого класса). Исключим их из рассмотрения. Среди оставшихся некоторые классы станут после такого исключения минимальными. При необходимости перекрасим их и тоже исключим. И так далее.
Поскольку классов конечное число, процесс закончится.
Ответ. Можно.
Числа от 1 до 1000000 покрашены в два цвета - черный и белый. За ход разрешается выбрать любое число от 1 до 1000000 и перекрасить его и все числа, не взаимно простые с ним, в противоположный цвет. Вначале все числа были черными. Можно ли за несколько ходов добиться того, что все числа станут белыми?
Решение:
Лемма. Пусть дан набор простых чисел $p_1, \cdots , p_n$. Тогда можно за несколько перекрашиваний добиться того, что поменяют цвет те и только те числа, которые делятся на все простые числа набора.
Доказательство. (формула включения-исключения). Для каждого непустого поднабора наших простых чисел перекрасим числа, не взаимно простые с произведением всех чисел этого поднабора. Число, делящееся на все числа набора, перекрашивалось при каждом таком перекрашивании, всего перекрашиваний было $2^n - 1$, следовательно, числа, делящиеся на все числа набора, перекрашены. Пусть некоторое число $k$ не делится хотя бы на одно из чисел набора, например, на $р_1$. Тогда оно не перекрашивалось, когда мы перекрашивали числа, не взаимно простые с $р_1$. Остальные непустые поднаборы чисел можно разбить на пары следующим образом: поднабору, не содержащему $р_1$, в пару ставится поднабор, полученный из него добавлением $р_1$. При этом число $k$ перекрашивается или при обоих перекрашиваниях пары, или ни при одном. Поэтому число $k$ не будет перекрашено.
Лемма доказана.
Первое решение. Для каждого набора простых чисел, произведение которых не больше 1 000 000, перекрасим числа, делящиеся на все эти простые числа. По лемме такая операция возможна. Докажем, что любое число $k$ при этом будет перекрашено. Пусть $k$ имеет $m$ различных простых делителей, тогда оно перекрашивалось при $2^m - 1$ операции, т. е. нечетное число раз.
Второе решение. Назовем два числа эквивалентными, если у них совпадают наборы простых делителей. Заметим, что при наших операциях классы эквивалентности перекрашиваются целиком. Будем говорить, что один класс больше другого, если все простые делители второго класса являются делителями первого. Из леммы следует, что мы можем перекрасить любой класс, перекрасив вместе с ним только большие классы.
Сначала перекрасим минимальные классы (класс называется минимальным, если он не больше никакого другого класса). Исключим их из рассмотрения. Среди оставшихся некоторые классы станут после такого исключения минимальными. При необходимости перекрасим их и тоже исключим. И так далее.
Поскольку классов конечное число, процесс закончится.
Ответ. Можно.
