Математика

Уравнения в целых числах

 

Для решения задачи мы составляем ее математическую модель. У нас есть известные и неизвестные данные. Мы записываем соотношения между ними и получаем уравнение, неравенство или их системы.

 

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

Например, неизвестная величина должна быть положительной. С таким ограничением мы сталкивались, когда решали геометрические или физические задачи: длина и время – это положительные величины. И получая при решении математической модели отрицательные значения таких величин, мы их отбрасывали.

На этом уроке мы рассмотрим математические модели с другими ограничениями – когда неизвестные величины являются целыми или натуральными числами. Такие ограничения обычно возникают в тех случаях, когда мы говорим о количестве чего-либо. Посмотрим, как повлияет это ограничение на количество решений.

Ранее мы в основном сталкивались с задачами, в которых количество уравнений было равно количеству неизвестных. Мы решали уравнение с одной неизвестной, систему двух уравнений с двумя неизвестными и т. д.:

1.

2.

3.

Обратите внимание, что в рассмотренных примерах мы получали конечное количество решений.

Пример. Для сравнения: если мы возьмем одно уравнение с двумя неизвестными, например , то получим бесконечное множество решений. Чтобы указать их все, можно, например, выразить :  и построить график соответствующей функции (см. рис. 1).

Рис. 1. График функции

Координаты всех точек функции и будут тем бесконечным множеством решений.

Но если указать, что неизвестные  и  – это натуральные числа, то количество решений будет уже конечным. Посмотрим:  может принимать значения только ,  или . Ведь если  будет равно , то  уже будет равен нулю – это не натуральное число. Если же  будет больше , то  будет отрицательным, а значит, точно не натуральным числом. Итак, получаем всего три решения:

Ответ: , , .

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

Обозначив количество пар перчаток как , а количество шапок как , мы получим уравнение  в натуральных числах. Полученное ранее решение этого уравнения в натуральных числах можно интерпретировать так: в ящике могут быть  пара перчаток и  шапок;  пары перчаток и  шапки;  пары перчаток и  шапки.

Итак, математической моделью задачи может быть уравнение в целых числах. Такие уравнения еще называют диофантовыми уравнениями в честь древнегреческого математика Диофанта (см. рис. 2).

Рис. 2. Диофант Александрийский

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

 

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

 

 

Основным методом для решения уравнений в целых числах является использование свойств делимости целых (натуральных) чисел: если одна часть равенства делится на некоторое целое число, то и другая часть должна на него делиться.

 

Задание 1. Решить уравнение в целых числах:

Решение

В левой части можем вынести за скобку :

Поскольку  и  – целые числа, то левая часть уравнения делится на . Но правая часть не делится на . Это означает, что уравнение не имеет решений в целых числах.

Ответ: нет решений.

Полученный результат можно обобщить: если имеется уравнение в целых числах вида , то мы всегда можем в левой части вынести за скобки НОД чисел  и . Если число  не будет делиться на него, то уравнение не будет иметь решений в целых числах.

Задание 2. Решить уравнение в натуральных числах:

Решение

НОД чисел  и  равен  – это взаимно простые числа, поэтому использовать сформулированное только что свойство мы не можем. Но можно обратить внимание, что два слагаемых ( и ) делятся на . Перенесем их в одну сторону:

Теперь можем вынести за скобки :

Правая часть уравнения делится на . Соответственно, и левая должна делиться на . Это возможно только в том случае, когда  делится на  (так как  на  не делится нацело и, кроме того, у  и  нет общих делителей, кроме ).

Если бы у нас было, например, уравнение , то мы не могли бы утверждать, что  обязательно должно делиться на , ведь у  и  есть общий делитель . Например, , то есть равенство возможно при , которое не делится нацело на ).

Кроме того, можно оценить, что . Иначе выражение  будет больше  и  должно быть отрицательным.

Итак:  – натуральное число, делится на , не превосходит . Этим критериям удовлетворяет только число . Подставляем это в уравнение, находим :

Ответ: .

Задание 3. Решить уравнение в целых числах:

Решение

Поскольку  и  – целые числа, то выражения  и  принимают только целые значения. Получаем, что произведение двух целых чисел равно . Теперь нам достаточно перебрать все возможные варианты разложения числа  на целые множители:

Получили четыре случая:

Найдем решения в каждом из них:

1.

Систему удобно решить методом сложения. Умножаем первое уравнение на  и складываем. Получим:

Тогда:

Оставшиеся  случая можете рассмотреть самостоятельно. Проверить себя можно ниже.

---

 

Решение систем уравнений

Рассмотрим оставшиеся три случая:

2.

Систему, как и в первом случае, удобно решать, умножив первое уравнение на  и сложив его со вторым:

3.

После аналогичного преобразования получим:

4.

Получим:

Ответ: , , , .

---

 

Уравнения с цифрами

 

 

Частным случаем уравнений в целых числах являются уравнения с цифрами или, если говорить точнее, уравнения, в которых неизвестные являются числами от  до . В таких уравнениях под неизвестной  мы будем понимать некоторое однозначное число. Чтобы обозначить двузначное число, нам потребуются уже две цифры:  и b. Число, в разряде десятков которого стоит цифра , в разряде единиц – цифра , принято обозначать как . Черта сверху нужна для того, чтобы отличать запись от умножения чисел  и .

 

С учетом разрядных слагаемых число  можно записать так: . Аналогичным образом можно записать трехзначное число (), четырехзначное () и т. д.

Задание 4. Найти все двузначные числа, которые в  раза больше суммы своих цифр.

Решение

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

Двузначное число в общем виде можно записать так: . Причем , иначе мы получим однозначное число. Сумма цифр такого числа равна . По условию, получаем соотношение:

Расписав двузначное число с помощью разрядных слагаемых, получим уравнение:

Мы получили уравнение, где неизвестными являются числа от  до . Это частный случай диофантовых уравнений, поэтому будем пользоваться теми же принципами: исследовать делимость. Преобразуем уравнение:

Левая часть делится на , значит, и правая часть также должна делиться на . Поскольку  – это число от  до , то возможны лишь  варианта:  или . При  получаем:

Но мы указали, что , значит, этот вариант не подходит. При  получаем:

Тогда двузначное число:

Ответ: .

Задание 5. Существует ли двузначное число, которое равно сумме квадратов своих цифр?

Решение

Составив математическую модель данной задачи, получим уравнение:

Или, расписав с помощью разрядных слагаемых:

Преобразуем уравнение:

Глядя на обе части уравнения, сразу нельзя сказать, на что они делятся. В таком случае начинаем проверять делимость на простые числа. Можно обратить внимание, что в правой части стоит произведение двух последовательных чисел:  и . Одно из них точно четное, другое – нечетное. Произведение четного и нечетного числа точно будет делиться на . Значит, и левая часть уравнения должна делиться на .

Число  может быть только четным. Ведь если оно нечетное, то и выражение  также нечетное. В таком случае их произведение не будет делиться на .

Получается,  может быть равно , ,  или  (как и в предыдущей задаче , чтобы число было двузначным). Соответственно, произведение  может быть равно  (при  и ) или  (при  и ). Получаем всего  случая:

 или .

Далее можно решить полученные уравнения и убедиться, что они не имеют целых решений. Или же можно просто вспомнить таблицу умножения и понять, что произведение двух последовательных натуральных чисел не будет равно ни , ни . Таким образом, уравнение не будет иметь решений в целых числах.

Ответ: не существует двузначных чисел, которые равны сумме квадратов своих цифр.

 

Решение логических задач

 

 

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

 

Задание 6. Кролик утверждает, что вчера Винни-Пух съел не менее  баночек меда, Пятачок — что не менее  баночек, ослик Иа — что не менее . Сколько баночек меда съел вчера Винни-Пух, если из трех этих утверждений истинно только одно?

Решение

Поскольку истинно только 1 утверждение, то возможно лишь 3 варианта:

1. Верно утверждение Кролика.
2. Верно утверждение Пятачка.
3. Верно утверждение ослика Иа.

Для решения задачи рассмотрим каждый из этих вариантов.

1. Верно утверждение Кролика, т. е. количество баночек не менее . Но тогда верны и остальные  утверждения, ведь это значит, что баночек было и не менее , и не менее . А это противоречит условию задачи, что верно только  утверждение.
2. Верно утверждение Пятачка. Аналогично из этого следует, что утверждение ослика Иа также верно. Это также противоречит условию задачи.
3. Верно утверждение ослика Иа. Количество съеденных баночек меда не менее . При этом утверждения Пятачка и Кролика неверны, т. е. количество баночек менее  и менее . Здесь противоречий не возникает. Эти условиям удовлетворяет только число .

Ответ:  баночек.

Задание 7. Из пяти следующих утверждений о результатах матча хоккейных команд «Медведи» и «Металлист» четыре истинны, а одно – ложно. Определить, с каким сче­том закончился матч, и указать победителя (если матч завершился победой одной из команд).

1. Выиграли «Медведи».
2. Всего в матче было заброшено менее  шайб.
3. Матч закончился вничью.
4. Всего в матче было заброшено более  шайб.
5. «Металлист» забросил более  шайб.

Здесь у нас 5 возможных вариантов: каждое из 5 утверждений может быть ложным. Как и в предыдущей задаче, рассмотрим каждый вариант и будем искать противоречия.

1. Ложно утверждение 1, остальные утверждения истинны. Тогда из 2 и 4 условий следует, что было заброшено  шайб: это единственное число, меньшее  и большее . Но из утверждения 3 следует, что команды забросили одинаковое число шайб, то есть общее количество должно быть четным. Получаем противоречие.

2. Ложно утверждение 2, остальные истинны. Но в этом случае утверждения 1 и 3 противоречат друг другу.

Аналогично можно отбросить варианты, когда ложно утверждение 4 и ложно утверждение 5.

3. Остается лишь один возможный вариант: утверждение 3 ложно, остальные истинны. Тогда из условий 2 и 4 следует, что всего было заброшено  шайб. Из условия 5 следует, что «Металлист» забросил минимум  шайбы. Но при этом  шайб он забросить не мог, ведь тогда был бы счет  в пользу «Металлиста», что противоречит условию 1. Аналогично и больше  шайб эта команда забросить не могла. Получаем, что команда «Металлист» забросила  шайбы. Тогда команда «Медведи» –  шайб.

Ответ: счет  в пользу «Медведей».

 

Таблицы

 

 

Для решения многих задач удобно визуализировать условие. Это же относится и к решению логических задач. Для их наглядного представления можно использовать таблицы.

 

Задание 8. Три друга: Андрей, Борис и Аркадий – живут в трех разных городах: Архангельске, Брянске и Белгороде. Один из них архитектор, другой – бизнесмен, третий – актер. Определить город проживания и профессию каждого из них, если:

1. Андрей раз в год ездит в гости к своему другу-бизнесмену в Белгород;
2. Борис всегда хотел стать актером, но так и не осуществил свою мечту;
3. только у одного из друзей имя, город и профессия начинаются на одну и ту же букву.

Решение

Для удобства решения составим таблицу:

Имя	Андрей	Борис	Аркадий
Город	Архан., Бр., Бел.	Архан., Бр., Бел	Архан., Бр., Бел
Профессия	Арх., акт., бизн.	Арх., акт., бизн.	Арх., акт., бизн.

Составив таблицу именно таким образом, мы уместили в нее все возможные варианты. Теперь будем вычеркивать варианты, не соответствующие условию. Из первого утверждения можно сделать вывод, что Андрей точно не бизнесмен и не живет в Белгороде. Из второго условия следует, что Борис не актер.

Имя	Андрей	Борис	Аркадий
Город	Архан., Бр., Бел.	Архан., Бр., Бел.	Архан., Бр., Бел.
Профессия	Арх., акт., бизн.	Арх., акт., бизн.	Арх., акт., бизн.

Дальше однозначных выводов мы сделать не можем. Продолжим анализировать условие 1. Этим другом может быть или Борис, или Аркадий. Рассмотрим каждый из вариантов.

1. Борис живет в Белгороде и является бизнесменом.

Имя	Андрей	Борис	Аркадий
Город	Архан., Бр., Бел.	Архан., Бр., Бел.	Архан., Бр., Бел.
Профессия	Арх., акт., бизн.	Арх., акт., бизн.	Арх., акт., бизн.

То есть именно он является тем человеком из условия 3. Остались Андрей с Аркадием и архитектор с актером, т. е. у них имена точно совпадают с названием профессии. При этом кто-то из них точно живет в Архангельске, т. е. у этого человека также будут совпадать первые буквы имени, профессии и города. Получаем противоречие с условием 3. Этот вариант не подходит.

2. Остается только второй вариант – Аркадий живет в Белгороде и является бизнесменом.

Имя	Андрей	Борис	Аркадий
Город	Архан., Бр., Бел.	Архан., Бр., Бел.	Белгород
Профессия	Арх., акт., бизн.	Арх., акт., бизн.	Бизнесмен

Тогда из всех профессий для Бориса остается лишь архитектор. Тогда Андрей – актер.

Имя	Андрей	Борис	Аркадий
Город	Арх. Бр. Бел	Арх. Бр. Бел	Белгород
Профессия	Актер	Архитектор	Бизнесмен

Дальше 2 варианта: Андрей живет в Архангельске, а Борис – в Брянске или наоборот. Но во втором случае условие 3 не будет выполнено ни для одного из друзей. В итоге получаем ответ:

Имя	Андрей	Борис	Аркадий
Город	Архангельск	Брянск	Белгород
Профессия	Актер	Архитектор	Бизнесмен

 

Графы

 

 

Еще одним наглядным представления информации в логических задачах являются графы. Граф представляет собой множество точек (вершин), соединенных линиями (ребрами) (см. рис. 3). Вершины графов обычно соответствуют некоторому объекту, а ребра – связями между объектами.

 

Рис. 3. Графы

Сейчас мы рассмотрим лишь простейшее применение графов. Но в целом теория графов – это мощнейший инструмент, используемый в различных областях: логистике, базах данных, нейронных сетях и пр. А возникла эта теория при построении математической модели к задаче о мостах в городе Кенигсберге (сейчас Калининград). Подробнее об этом вы можете узнать ниже.

---

 

Задача Эйлера про мосты

Мы уже много раз говорили о том, что решение любой практической задачи начинается с построения математической модели.

Но иногда модель сводится к эквивалентной математической задаче, которая оказывается важнейшим инструментом для решения целого класса других, совершенно не похожих на первый взгляд задач. Одним из таких примеров является задача Эйлера про мосты.

Издавна среди жителей Кенигсберга (сейчас Калининграда) была распространена такая загадка: как пройти по всем городским мостам (через реку Преголя), не проходя ни по одному из них дважды (см. рис. 4).

Рис. 4. Иллюстрация к задаче Эйлера про мосты

В  году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук, Леонарда Эйлера (см. рис. 5). Он доказал, что сделать это было нельзя.

Рис. 5. Леонард Эйлер

Но важно, конечно, не само решение этой шуточной задачи, а то, что, решая ее, Эйлер свел ее к эквивалентной формулировке, которая помогла разработать принципиально новый математический инструмент – теорию графов, которая сейчас повсеместно используется, например в программировании.

Основная идея Эйлера: нам не важны размеры мостов, значит, их можно считать линиями, а также размеры частей города – их можно считать точками (см. рис. 6). Тогда задача сводится к такой: можно ли нарисовать такой граф, не отрывая карандаша от бумаги.

Рис. 6. Мосты можно считать линиями, а города – точками, т. к. их размеры не важны

Решая задачу семи мостов, Эйлер вывел несколько важных теорем, касающихся различных графов. Одна из них говорила, что граф с более чем двумя нечетными вершинами (т. е. вершинами, к которым ведет нечетное число ребер) нельзя начертить одним росчерком.

Интуитивное доказательство этого утверждения несложное: рисуя граф, не отрывая руки, мы должны входить и выходить из каждой точки одинаковое количество раз, т. е. в точке должно сходиться только четное количество ребер (см. рис. 7).

Рис. 7. Чтобы граф можно было нарисовать, не отрывая руки, у него должно быть не более двух нечетных вершин

Исключение составляют две вершины – начало (из этой точки мы выходим на один раз больше, чем входим) и конец (для него все наоборот). Если же таких вершин больше, то начертить граф одним росчерком не получится. У графа из задачи о  мостах все  вершины нечетные (см. рис. 8), поэтому задача не имеет решения.

Рис. 8. У графа из задачи о  мостах все  вершины нечетные

Для нас важнее отметить, что правильная эквивалентная формулировка условия и упрощение модели – залог решения любой задачи.

---

Задание 9. В чашке, стакане, кувшине и банке находятся молоко, лимонад, квас, вода. Известно следующее:

1. Вода и молоко находятся не в чашке.
2. Сосуд с лимонадом стоит между кувшином и сосудом с квасом.
3. В банке не лимонад и не вода.
4. Стакан стоит около банки и сосуда с молоком.

В каком сосуде какая жидкость?

Решение

Нарисуем граф, вершинам которого будут все жидкости и сосуды. Если жидкость находится в указанном сосуде, то мы будем соединять соответствующие вершины ребром черного цвета. А чтобы откинуть лишние варианты, будет соединять вершины красным ребром в том случае, если жидкость точно не находится в этом сосуде.

Условия 1 и 3 говорят нам, каких жидкостей нет в чашке и стакане (см. рис. 9).

Рис. 9. Иллюстрация к заданию 9

Из условия 2 можно сделать вывод, что в кувшине нет ни лимонада, ни кваса. А из условия 4, что молоко – не в банке и не в стакане (см. рис. 10):

Рис. 10. Иллюстрация к заданию 9

Итак, мы с помощью графа эквивалентно переписали условие задачи. Поскольку в каждом сосуде есть какая-то из жидкостей, то из каждой вершины должно в итоге выходить по 3 красных и 1 черному ребру. Дорисуем недостающие ребра. Сразу можем сказать, что в банке находится квас, а молоко находится в кувшине (см. рис. 11):

Рис. 11. Иллюстрация к заданию 9

Значит, в кувшине нет воды. Получается, что вода в стакане. Тогда для лимонада остается чашка (см. рис. 12).

Рис. 12. Иллюстрация к заданию 9

Ответ: лимонад в чашке, вода в стакане, молоко в кувшине, квас в банке.

---

 

Другой способ решения задачи

Задачу про сосуды и жидкости можно решить и с помощью таблицы. Идея будет точно такой же, как и в случае с графами, но кому-то такой способ может показаться более наглядным.

Изобразим в таблицу, в которой по строкам будут жидкости, а по столбцам – сосуды. «Плюс» на пересечении будет означать, что в данном сосуде находится именно эта жидкость. «Минус» – что этой жидкости в этом сосуде нет.

	Чашка	Стакан	Кувшин	Банка
Молоко
Лимонад
Квас
Вода

Первое условие говорит нам, что вода и молоко находятся не в чашке, из второго условия можно сделать вывод, что в кувшине не лимонад и не квас, третье условие говорит, что в банке не лимонад и не вода, а из четвертого можно сделать вывод, что молоко не в стакане и не в банке. Занесем эти выводы в таблицу:

	Чашка	Стакан	Кувшин	Банка
Молоко
Лимонад
Квас
Вода

Поскольку в каждый сосуд налита ровно одна жидкость, то в каждом столбце должен быть ровно один «плюс» и, соответственно, в каждой строке должен быть ровно один «плюс». Сразу видим, что в кувшине – молоко. Ставим «плюс», а оставшуюся в столбце кувшина ячейку заполняем «минусом»:

	Чашка	Стакан	Кувшин	Банка
Молоко
Лимонад
Квас
Вода

Тогда сразу понятно, что вода в стакане, ставим «минусы» в оставшихся ячейках столбца стакана и получаем, что лимонад в чашке. Значит, квас в банке:

	Чашка	Стакан	Кувшин	Банка
Молоко
Лимонад
Квас
Вода

---

 

Список литературы

1. Никольский С.М., Решетников Н.Н., Потапов М.К., Шевкин А.В. Алгебра, 8 класс. Учебник. – М.: ФГОС, издательство «Просвещение», 2018.
2. Дорофеев Г.В., Суворова С.Б., Бунимович Е.А. Алгебра, 8 класс. Учебник. – М.: издательство «Просвещение», 2018.
3. Макарычев Ю.Н., Миндюк Н.Г., Нешков К.И., Суворова С.Б./Под ред. Теляковского С.А. Алгебра, 8 класс. Учебник. – М.: издательство «Просвещение», 2018.

 

Дополнительные рекомендованные ссылки на ресурсы сети Интернет

1. Интернет-портал math4school.ru (Источник)
2. Интернет-портал mir-logiki.ru (Источник)
3. Интернет-портал globallab.org (Источник)

 

Домашнее задание

1. Найти пятизначное число, если известно, что при умножении этого числа на  получается пятизначное число, записанное теми же цифрами, но в обратном порядке.
2. На школьном вечере четыре юноши: Валентин, Николай, Владимир и Алексей (все из разных классов) – и их одноклассницы танцевали в парах, но каждый юноша танцевал не со своей одноклассницей. Лена танцевала с Валентином, Аня – с одноклассником Наташи, Николай – с одноклассницей Владимира, а Владимир танцевал с Олей. Кто с кем танцевал?
3. Решить уравнение в целых числах: .