Question

В школе 1000 учеников,которым присвоены номера от 000 до 999, и 100 учителей с номерами от 00 до 99. Учителя следят за учениками, чтобы те не списывали. При этом они договорились следовать такому правилу: за учеником следят те учителя, номера которых можно получить из номера ученика вычеркиванием ровно одной цифры. Учителя математики утверждают, что можно ровно половину учителей освободить от этой обязанности так, что все равно за каждым учеником будет следить хотя бы один учитель. Не ошибаются ли они?

Answer 1

Они правы.
Только за учениками с номерами 000, 111, 222, ..., 999 следит по одному учителю с номерами соответственно 00, 11, 22, ..., 99.
За всеми остальными следят как минимум двое за каждым.
Например, за учеником номер 001 следят и учитель 00, и 01. А за учеником номер 123 следят трое: 12, 13 и 23.
Так что действительно, половину учителей можно уволить, но номера за оставшимися нужно сохранить.

Answer 2

Да, учителя математики правы. Их утверждение верно, и ровно половину учителей можно освободить от обязанности следить за учениками, сохраняя при этом условие, что за каждым учеником будет следить хотя бы один учитель.

Давайте объясним это на примере:

У нас есть 1000 учеников с номерами от 000 до 999 и 100 учителей с номерами от 00 до 99. Мы можем представить номера учеников и учителей в виде двухзначных чисел, добавляя нули слева, чтобы добиться двух цифр. Например, ученик с номером 5 будет представлен как 05, а учитель с номером 25 будет представлен как 25.

Теперь давайте рассмотрим каждого учителя и определим, сколько учеников может ему подходить.

1. Учитель с номером 00 может следить только за учеником 0X (где X - любая цифра от 0 до 9).
2. Учитель с номером 01 может следить только за учениками 01X, где X - любая цифра от 0 до 9.
3. Учитель с номером 02 может следить только за учениками 0X2, где X - любая цифра от 0 до 9.

И так далее...

Каждый учитель будет следить за 11 учениками, и учитывая, что всего учеников 1000, значит, каждый ученик имеет ровно одного учителя, который следит за ним. Все учителя получают равное количество учеников для наблюдения.

Теперь давайте рассмотрим следующую ситуацию:

4. Учитель с номером 10 может следить только за учеником 1X (где X - любая цифра от 0 до 9).

5. Учитель с номером 20 может следить только за учениками 2X, где X - любая цифра от 0 до 9.

6. Учитель с номером 30 может следить только за учениками 3X, где X - любая цифра от 0 до 9.

И так далее...

Таким образом, учитель с номером 10 следит за теми же учениками, за которыми следят учителя с номерами 01X. То же самое верно и для учителя с номером 20 и 30, и так далее. Таким образом, можно освободить половину учителей (то есть 50 учителей) от наблюдения, и все равно каждый ученик будет иметь хотя бы одного учителя, следящего за ним.