Тема ТЕОРИЯ ЧИСЕЛ

Уравнения в целых числах → .05 Линейные диофантовы уравнения

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела теория чисел

Разделы подтемы Уравнения в целых числах

Выбор модуля и перебор случаев в уравнениях над Z

Разложение на целые скобки

Оценки в уравнениях над Z

Уравнения на НОД и НОК

Линейные диофантовы уравнения

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#102755Максимум баллов за задание: 7

Решите в целых числах уравнение:

(a) $4x+ 5y = 1;$

(b) $5x− 9y = 24.$

Подсказки к задаче

Подсказка 1, пункт а

Перед нами диофантово уравнение, поэтому мы можем найти лишь одно решение, а остальные записать через него. Давайте подставим какие-то маленькие значения x и y.

Подсказка 2, пункт а

x = -1, y = 1 является решением! Осталось вспомнить, как же выражаются другие решения через него ;)

Подсказка 3, пункт а

x = -1 - 5t, y = 1 + 4t, где t -- целое.

Подсказка 1, пункт б

Давайте подбирать y небольшим, прибавлять к 9y 24 и смотреть, не делится ли число на 5.

Подсказка 2, пункт б

x = 12, y = 4 является решением! Тогда, аналогично пункту a, можно остальные решения выразить через текущее!

Показать ответ и решение

(a) Найдём частное решение уравнения. Пусть $(x;y)= (−1;1).$ Проверим, подставив в уравнение:

4⋅(−1)+ 5⋅1= 1 =⇒ 1 =1 =⇒ (− 1;1)— является реш ением.

Тогда общим решением уравнения будет:

{ x= −1− 5t y =1 +4t , t∈ ℤ

(b) Найдём частное решение уравнения. Пусть $(x;y)= (12;4).$ Проверим, подставив в уравнение:

5 ⋅12− 9⋅4= 24 =⇒ 24= 24 =⇒ (12;4)— является реш ением.

Тогда общим решением уравнения будет:

{ x= 12+ 9t y =4 +5t , t∈ℤ

Ответ:

(a) $(−1 − 5t;1+ 2t),t∈ℤ;$

(b) $(12+ 9t;4+ 5t),t∈ℤ$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#136473Максимум баллов за задание: 7

В центре стола находятся 600 фишек, и Петя готовится играть на нем в игру под названием «Забери больше фишек». Цель игры – убрать со стола как можно больше фишек, соблюдая правило: за один ход можно убрать со стола ровно 154 фишки (или не брать ни одной), а вернуть на стол только 105 (или не возвращать ни одной). Какое наибольшее число фишек может убрать со стола Петя, соблюдая правила? Своих фишек в карманах Пети нет.

Источники: Росатом - 2024, 10.3 (см. olymp.mephi.ru)

Подсказки к задаче

Подсказка 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 фишек!

Показать ответ и решение

Поскольку $154 =2⋅7⋅11,$ а $105= 3⋅5⋅7,$ то числа $154$ и $105$ имеют общий делитель $7.$ Таким образом, общее число фишек, которое Петя уберет со стола, делится на $7.$

Наибольшее число, делящееся на $7$ и не превосходящее $600,$ равно $595$ (поскольку $600= 7⋅85+5).$ Значит, более $595$ фишек Петя забрать не сможет.

Покажем, что собрать $595$ фишек возможно. Пусть для этого ему придется $k$ раз забрать $154$ фишки и $m$ раз вернуть на стол $105$ фишек. Имеем:

154k− 105m = 595

22k − 15m = 85

Из уравнения $22k= 85+ 15m$ следует, что $22k$ делится на $5.$ Так как числа $22$ и $5$ взаимно просты, $k$ должно делиться на $5.$

Пусть $k= 5s$ для некоторого целого $s.$ Подставив это в уравнение, получим:

22⋅(5s)− 15m = 85

110s− 15m = 85

22s− 3m = 17

Это линейное диофантово уравнение. Его частное решение можно найти подбором, например, $s= 2,$ $m= 9$ (проверка: $22⋅2− 3⋅9= 44− 27= 17$ ). Общее решение в целых числах имеет вид:

({s= 2+ 3t ( m = 9+22t

Поскольку $k= 5s,$ то общее решение для $k$ и $m$ в неотрицательных целых числах:

({ k =5(2+ 3t)= 10+15t , (m = 9+ 22t

где $t$ может принимать значения $0,1,2,...22.$

Видим, что убрать со стола $595$ фишек можно различными способами. Например, при $t= 0$ получаем $k= 10$ и $m =9.$ Этот вариант соответствует $19$ ходам. Схема действий может быть такой:

(◟154-− 105)+⋅◝⋅◜⋅+-(154−-105◞)+154 =9⋅49+ 154 =595 9 раз

Этот вариант возможен: после каждой из девяти пар ходов (взять $154,$ вернуть $105)$ число фишек на столе уменьшается на $49.$ После этого делается десятый ход (взять $154$ фишки). Итоговое изменение составит $595$ фишек, а на столе останется $600 − 595= 5$ фишек.

Ответ: 595

Ошибка.
Попробуйте повторить позже

Задача 3#116004Максимум баллов за задание: 7

Среди всех обыкновенных дробей, числитель и знаменатель которых являются двузначными числами, найдите наименьшую дробь, большую, чем $3 4.$

Подсказки к задаче

Подсказка 1

Попробуем поискать дроби, которые отличаются от 3/4 на дробь, вид которой мы знаем. Причем нам хочется, чтобы это отличие было как можно меньше.

Подсказка 2

Найдите дробь, которая отличается от 3/4 на 1/k, где k — целое. Что можно сказать про k?

Подсказка 3

Итак, мы знаем, что числитель и знаменатель искомой дроби выражаются через k. Может ли такая дробь быть несократимой, если мы минимизируем k?

Подсказка 4

Хотелось бы сделать дробь сократимой! Тогда нужно аккуратно найти НОД числителя и знаменателя ;)

Показать ответ и решение

Требуется найти такую дробь $a, b$ при которой

a 3 4a−-3b b − 4 = 4b

достигает минимума. Поэтому хотим максимизировать двузначное число $b.$ Заметим, что если $b≥50,$ то минимум $4a−3b -4b-$ достигается при

4a− 3b= 1

Так как в ином случаи, если возьмём дробь с неединичным числителем, то мы можем сравнить её с дробью с единичным числителем, домножив числитель и знаменатель дроби с единичным числителем и сравнив только знаменатели получившихся дробей. Но знаменатель заведомо будет больше у дроби, получившейся из дроби с единичным числителем, засчёт большего числа разрядов в числе, ибо $b≥ 50.$

Решаем уравнение $4a− 3b= 1.$ Так как $4a−1- a−1 b= 3 =a+ 3$ — целое, то $a= 1+ 3k,$ где $k$ — произвольное целое число. Поэтому $b= 1+ 4k.$

Максимальным $k,$ при котором $a$ и $b$ двузначные, будет $k =24.$ Поэтому $b= 97$ и $a =73,$ то есть искомая дробь: $a 73 -b = 97.$

Ответ:

$73 97$

Ошибка.
Попробуйте повторить позже

Задача 4#115887Максимум баллов за задание: 7

Перед чемпионатом мира по футболу тренер сборной России решил провести три тренировочных матча (каждый продолжительностью $90$ минут) с участием семи игроков, чтобы оценить их навыки. В любой момент времени во время матча на поле находится ровно один из них. Суммарное время (измеряемое в минутах), проведённое на поле каждым из четырёх первых игроков, должно быть кратно $7,$ а для каждого из трех оставшихся — кратно $13.$ Количество замен игроков во время каждого матча не ограничено. Сколько существует возможных распределений игрового времени между игроками при заданных условиях?