12. (Московская устнам алимпиада, 2003, 7.3) На каждом километре между облами Марьино и Рощино стоит столб с табличкой, на одной стороне которой написамо расстояние до Марьино, на другой - расстояние до Рощино. Гуляя по этой дороге, Бобик для каждой таблички подечи- тал наибольший общий делитель записанных на ней чисел. Оказалось, что среди полученных им чисел встретились только 1, 3 или 5 (каждое хотя бы по одному разу). Найдите расстояние между сёлами.

Для решения этой задачи будем обозначать расстояние от села Марьино до села Рощино как \( D \) километров. Табличка на каждом километре будет показывать расстояние до Марьино как \( d_M = k \) и расстояние до Рощино как \( d_R = D - k \), где \( k \) — номер километра от Марьино (значения \( k \) варьируются от 0 до \( D \)).

На каждой табличке мы должны вычислить наибольший общий делитель (НОД) \( \text{gcd}(k, D - k) \). Мы можем использовать свойство НОД:

\[ \text{gcd}(k, D - k) = \text{gcd}(k, D) \]

Таким образом, для каждого \( k \) из \( 0 \) до \( D \) мы должны получить \( \text{gcd}(k, D) \). Учитывая, что среди всех возможных значений НОД могут встречаться только 1, 3 или 5, нам нужно выяснить, какие значения \( D \) могут привести к этому.

1. Если \( D \) является простым числом или содержит только простые делители, не превышающие 5, то возможные значения НОД будут ограничены.
2. Возьмем \( D \) кратное 3 и 5, поскольку эти числа могут давать различные НОД.

Поскольку в диапазоне от 0 до \( D \) НОД может быть самым большим, когда \( k \) — кратное либо 3, либо 5. Мы начнем с чисел, кратных 15 (так как 15 — наименьшее общее кратное 3 и 5):

Подождем, пока проверим \( D = 15 \):

• Для \( k = 0 \): \( \text{gcd}(0, 15) = 15 \)
• Для \( k = 1 \): \( \text{gcd}(1, 15) = 1 \)
• Для \( k = 2 \): \( \text{gcd}(2, 15) = 1 \)
• Для \( k = 3 \): \( \text{gcd}(3, 15) = 3 \)
• Для \( k = 4 \): \( \text{gcd}(4, 15) = 1 \)
• Для \( k = 5 \): \( \text{gcd}(5, 15) = 5 \)
• Для \( k = 6 \): \( \text{gcd}(6, 15) = 3 \)
• Для \( k = 7 \): \( \text{gcd}(7, 15) = 1 \)
• Для \( k = 8 \): \( \text{gcd}(8, 15) = 1 \)
• Для \( k = 9 \): \( \text{gcd}(9, 15) = 3 \)
• Для \( k = 10 \): \( \text{gcd}(10, 15) = 5 \)
• Для \( k = 11 \): \( \text{gcd}(11, 15) = 1 \)
• Для \( k = 12 \): \( \text{gcd}(12, 15) = 3 \)
• Для \( k = 13 \): \( \text{gcd}(13, 15) = 1 \)
• Для \( k = 14 \): \( \text{gcd}(14, 15) = 1 \)

Таким образом, для \( D = 15 \) мы получаем НОД только равные 1, 3 и 5, что соответствует условию задачи.

Следовательно, расстояние между селами Марьино и Рощино равно \( 15 \) километров.