Линейные диофантовы уравнения
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В центре стола находятся 600 фишек, и Петя готовится играть на нем в игру под названием «Забери больше фишек». Цель игры – убрать со стола как можно больше фишек, соблюдая правило: за один ход можно убрать со стола ровно 154 фишки (или не брать ни одной), а вернуть на стол только 105 (или не возвращать ни одной). Какое наибольшее число фишек может убрать со стола Петя, соблюдая правила? Своих фишек в карманах Пети нет.
Источники:
Подсказка 1
Может ли Петя забрать все 600 фишек, если его возможные действия: 0, +154, -105? Что общего у этих чисел?
Подсказка 2
Они делятся на 7. Что это говорит о количестве фишек, которые могут оказаться у Пети?
Подсказка 3
Итоговое число фишек тоже будет делиться на 7. Мы построили оценку, надо разобраться, есть ли пример. Как перевести полученную задачу на язык математики?
Подсказка 4
Больше 595 фишек Петя забрать не сможет. Нулевые ходы можем не считать, пусть k раз Петя взял 154 фишки и m раз вернул на стол 105 фишек. Сокращаем полученное уравнение на 5, что можем сказать про k?
Подсказка 5
Мы решаем в целых неотрицательных числах, k делится на 5, сделаем замену k = 5s и получим уравнение 22s - 3m = 17, которое можно решить в общем виде для целых чисел.
Подсказка 6
Перейдем опять к k и найдем пример, показывающий, что возможно набрать 595 фишек!
Поскольку 
а 
то числа 
и 
имеют общий делитель 
Таким образом, общее число фишек, которое
Петя уберет со стола, делится на 
Наибольшее число, делящееся на 
и не превосходящее 
равно 
(поскольку 
Значит, более 
фишек Петя
забрать не сможет.
Покажем, что собрать 
фишек возможно. Пусть для этого ему придется 
раз забрать 
фишки и 
раз вернуть на стол 
фишек. Имеем:
Из уравнения 
следует, что 
делится на 
Так как числа 
и 
взаимно просты, 
должно делиться на
Пусть 
для некоторого целого 
Подставив это в уравнение, получим:
Это линейное диофантово уравнение. Его частное решение можно найти подбором, например, 
(проверка:
). Общее решение в целых числах имеет вид:
Поскольку 
то общее решение для 
и 
в неотрицательных целых числах:
где 
может принимать значения 
Видим, что убрать со стола 
фишек можно различными способами. Например, при 
получаем 
и 
Этот вариант
соответствует 
ходам. Схема действий может быть такой:
Этот вариант возможен: после каждой из девяти пар ходов (взять 
вернуть 
число фишек на столе уменьшается на 
После
этого делается десятый ход (взять 
фишки). Итоговое изменение составит 
фишек, а на столе останется 
фишек.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
