Question

Срочно!
Докажите, что из монет в 3 и 7 туристов можно составить любую сумму, начиная с 12-ти тугриков.

Answer 1

Для доказательства этого утверждения воспользуемся алгоритмом суммирования по модулю 3 и 7.
Пусть у нас есть x монет по 3 тугрика и y монет по 7 тугриков. Цель составить сумму, начиная с 12 тугриков.
1 Начнем с предположения, что у нас есть достаточное количество монет, чтобы составить сумму, равную 12 тугрикам:
2 3a + 7b = 12
3 где a и b - некоторые целые числа.
4 Для удобства докажем данное утверждение индукцией.
• База индукции: При a=4 и b=0 у нас есть 12 монет по 3 тугрика, что дает сумму 12 тугриков.
• Предположение индукции: Пусть для некоторых a и b выполняется условие 3a + 7b = n, где n ≥ 12.
• Шаг индукции: Докажем, что для a+1 и b-2 также будет выполняться условие 3(a+1) + 7(b-2) = n + 1.
3(a+1) + 7(b-2) = 3a + 3 + 7b - 14 = (3a + 7b) - 11
Так как 3a + 7b = n (предположение индукции), то:
3(a+1) + 7(b-2) = n - 11 = n + 1
Таким образом, предположение индукции выполняется.
5 Используя индукцию, мы можем утверждать, что для любой суммы n ≥ 12 мы можем составить сумму n с помощью монет по 3 и 7 тугриков.
Таким образом, мы доказали, что из монет в 3 и 7 туристов можно составить любую сумму, начиная с 12 тугриков

Answer 2

Действительно, из монет достоинством 3 и 7 тугриков можно составить любую сумму, начиная с 12-ти тугриков. Это основано на теории чисел и конкретно на так называемой "теории Фробениуса".

В данном случае, так как у нас есть монеты достоинством 3 и 7 тугриков, мы можем составить любое число N, которое больше либо равно 12, следующим образом:

- Если N кратно 3, мы можем просто использовать N/3 монет достоинством 3 тугрика.
- Если N не кратно 3, мы можем использовать одну монету достоинством 7 тугриков и оставшуюся сумму (N-7) можем составить с помощью монет достоинством 3 и 7 тугриков.

Таким образом, мы можем составить любую сумму, начиная с 12-ти тугриков, используя монеты достоинством 3 и 7 тугриков.