Задачи 1006 - 1015 проекта
Условия и решения вариантов задач
1007а. В городе Кенигсберге во времена Эйлера было семь мостов. Если «сжать» сушу в точки, а мосты вытянуть в линии, то в результате получим следующую фигуру:
Однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда начиналась прогулка. Что можно ответить на этот вопрос?
Решение. Формулировать и решать некоторые математические задачи помогают специальные схемы, состоящие из точек и соединяющих их дуг или стрелок. Такие схемы называют графами, точки называют вершинами графа, а дуги – ребрами графа. Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выходит четное количество ребер, - четными. Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, свойства графа:
ª Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.
ª Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине.
ª Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
В задаче о семи кенигсбергских мостах все четыре вершины соответствующего графа нечетные, т.е. нельзя пройти по всем мостам один раз и закончить путь там, где он был начат.
Ответ: не сможет.
1009а. Расставьте в записи скобки так, чтобы получилось верное равенство:
48:8+4·4+9=25.
Ответ:48:(8+4)·4+9=25
1010а. Найдите с помощью алгоритма Евклида: а) НОД чисел 270 и 186; б) НОД чисел 234 и 180.
Решение. Алгоритм Евклида - это новый способ найти НОД 2-х чисел. Впервые этот способ нахождения НОДа был описан в книге Евклида «НАЧАЛА». Вот как он действует:
1) Разделить большее число на меньшее с остатком;
2) Разделить делитель на остаток и т.д.;
3) НОДом чисел будет являться последний ненулевой остаток.
Имеем: а) Чтобы найти НОД чисел 270 и 186, разделим 280 на 186 с остатком: 270:186=1(ост. 84). Далее делим делитель 186 на остаток 84 и т. д.:
186:84=2 (ост. 18), 84:18=4 (ост. 12), 18:12=1 (ост. 6), 12:6=2 (ост. 0). Наибольшем общим делителем чисел 270 и 186 является последний ненулевой остаток, т. е. число 6.
б) Найдем НОД чисел 234 и 180: 1) 234:180=1 (ост.54), 2)180:54=3 (ост. 18), 3) 54:18=3 (ост. 0). Следовательно, НОД (234;180)=18.
Ответ: а) 6; б) 18.