Задача, возникшая из каприза трёх девочек

27

ся на $l$? Оказывается, такое $q$ существует тогда и только тогда, когда 10 и $l$ взаимно просты*). (Попробуйте доказать это утверждение самостояльно; «в одну сторону》 оно доказывается очень легко, «в другую» — не очень.)

Легко обобщить наш признак делимости и на произвольные системы численния.

Пусть
$$n = \overline{a_1 a_2 \dots a_t}^{(r)},$$
то есть
$$n = a_t + ra_{t-1} + r^2 a_{t-2} + \dots + r^{t-1} a_1,$$
и пусть $q$ такое, что $rq - 1$ делится на $l$. Построим по $n$ числу $n^* = \overline{a_t a_{t-1} \dots a_1}^{(q)}$. Тогда, чтобы $n$ делилось на $l$, необходимо и достаточно, чтобы на $l$ делилось $n^*$.

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

Ответ на вопрос: когда существует требуемое $q$? — аналогичен: $q$ существует тогда и только тогда, когда $r$ и $l$ взаимно просты.

Упражнения

1. Докажите, что наименьшее по модулю $q$ такое, что $10q - 1$ делится на $l$, равно
   $$q = \begin{cases} k, если l = 10k - 1, \\ -k, если l = 10k + 1, \\ 3k + 1, если l = 10k + 3, \\ -3k + 1, если l = 10k - 3. \end{cases}$$
   *) To есть когда их наибольший общий делитель равен 1.

Задача, возникшая из каприза трех девочек

При девочки гуляли со своим папами. Все шестеро подошли к небольшей реке и пожелали переправиться с одного берега на другой. В их распоряжении оказались всего одна лодка без гребца, поднимающая только $\delta$ух человек. Переправу было бы, разумеется, нетрудно осуществить, если бы девочки не заявили то ли из каприза, то ли из шалости, что ни одна из них не согласна exать в lodке, или быть на берегу с одним или двумя чужими папами без своего папи. Девочки были маленькие, но не очень, так что каждая из них могла вести лодку самостояльно.

Таким образом, неожиданное возникли дополнительные условия переправы, но ради забавы путники решили попытаться их выполнить. Как они действовали?

Всеся команда благополучно переправилась на противоположный берег реки и уселась отдельным. Возникло вопрос: можно ли при тех же условиях организовать переправу четырех пар? Очень скоро выяснилось, что при сохранении условий, вывидутых девочек, переправу четырех девочек с их папами, если посредни реки есть остров, на котором можно делать промежутную остановку и высказываться. В этом случае для окончательной переправы требуется совершить не менее десяти переездов.

Найдите способ такой переправы.

Б. Кордемский