Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Другие методич. материалы / Дидактический материал. "Олимпиадные задачи и методы их решения"

Дидактический материал. "Олимпиадные задачи и методы их решения"


  • Математика

Название документа ГРАФЫ.doc

Поделитесь материалом с коллегами:

Графы и их применение


Что такое граф?

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

На рисунке 1 показан пример графа.

Кhello_html_m1155540c.gifак вы видите, ребрами соединены не все вершины графа. Вершины, из которых не выходит ни одного ребра, называют изолированными. (На рисунке изолированная вершина это точка G).

С помощью графов удобно и наглядно изображается информация о разных объектах и отношениях между ними. Рассмотрим пример.

Пhello_html_45b1de08.gifример 1. В розыгрыше финальной части турнира участвуют семь команд: шесть команд, набравших наибольшее количество очков в предварительной части турнира и команда – победитель прошлого года. Сначала играют друг с другом первые шесть команд, затем три команды, одержавшие победы и команда, победитель прошлого года, играют друг с другом. Два победителя этого тура встречаются в финале.

Понять о чем идет речь в этом тексте нелегко. Попробуем представить его в виде наглядной схемы (смотри рисунок 2) и порядок организации финальной части розыгрыша станет очевидным.


Обратимся теперь к истории появления графов. Впервые в рассмотрение их ввел великий математик Леонард Эйлер. В популярной литературе часто упоминается его задача о Кенигсбергских мостах. Смысл задачи таков: в городе Кенигсберге (ныне это город Калининград) протекает река Прегель. Сам город расположен на берегах этой реки и ее островах. Естественно, что в городе построены мосты, связывающие все его районы (смотри рисунок 3). Во время прогулки по городу Эйлер захотел пройти по всем мостам, причем по каждому только один раз. Однако ему это не удалось. Вернувшись домой, ученый составил схему, изобразив участки суши точками, а мосты отрезками (рисунок 4). Это и был первый граф.

hello_html_m653807a0.gifМы ответим на вопрос, можно ли осуществить пешую прогулку по указанному правилу, в конце статьи, а сейчас рассмотрим некоторые важные свойства графов.



Определение 1. Степенью вершины графа называется число выходящих из него ребер.

Степени вершин А, В и D на рисунке 4 равны трем, а степень вершины С равна 5.

В графе на рисунке 1 степень вершины G равна нулю, так как из нее не выходит ни одно ребро.

Дhello_html_m75a736c.gifля степени вершины принято следующее обозначение: deg(A).

Рассмотрим некоторый граф G. Обозначим количество его вершин буквой p, а количество ребер буквой q. Сформулируем в виде теорем простейшие свойства степени.


Теорема 1. Сумма степеней всех вершин графа G равна удвоенному количеству его ребер (2q).


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


Теорема 2. В простом графе найдется не менее двух вершин с одинаковыми степенями.


Теорема 3. В простом графе с p вершинами число ребер не большеhello_html_66865472.gif:

hello_html_6bdca55c.gif.

Доказательство. Всего p вершин, каждая из них может быть соединена не более чем с (p-1) остальными вершинами. Таким образом, получаем (p-1)p ребер, но каждое из них посчитано ровно два раза, так как соединяет две вершины. Поэтому делим полученное выражение пополам.


Определение 2. Граф называется полным, если каждая его вершина соединена со всеми другими вершинами графа.


Примеры полных графов вы можете построить сами: нарисуйте выпуклый многоугольник и постройте все его диагонали. Из доказательства теоремы 2 вытекает, что в полном графе с p вершинами hello_html_66865472.gif ребер.


Пути, циклы, связность

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


Определение 3. Путем (из вершины А в вершину В) в графе называется последовательная цепочка смежных ребер, которая начинается в вершине А и заканчивается в вершине В. Путь может проходить через ребро только один раз.


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


Рhello_html_788921ae.gifассмотрим примеры. На рисунке 5 жирными линиями показан путь из точки А в точку В, который мы можем записать так: (AEDB). Другой путь из А в В показан пунктирными линиями, его можно записать как (l1l2l3).

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

Рассмотрим теперь специфический случай, когда начало и конец пути совпадают.


Определение 4. Циклом называется путь, у которого начало и конец совпадают.


На рисунке 5 циклами являются следующие пути: (AEFDA), (EFBCADE).


Упражнение. Попробуйте перечислить как можно больше циклов, содержащих точку А.

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


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


Граф на рисунке 1 несвязен, так как нет ни одного пути, соединяющего точку G с остальными вершинами, графы на рисунках 2, 4, 5 - связные.

Вам уже, наверное, приходилось встречать задачи, в которых предлагается обвести ту или иную фигуру, не отрывая карандаш от бумаги. При этом запрещается проводить карандаш по одной линии несколько раз. Понятно, что аналогичное задание может быть дано и относительно некоторого графа. Далеко не все графы можно построить описанным выше способом. Те, для которых это требование выполняется, называются уникурсальными или эйлеровыми. Эти графы непосредственно связаны с задачей о Кенигсбергских мостах и впервые описаны Леонардом Эйлером. Сам Эйлер доказал следующую теорему.


Теорема 4 (Эйлера). Связный граф уникурсален тогда и только тогда, когда степени всех его вершин четны или у него ровно две вершины нечетной степени.


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

Рассмотрим случай, когда все вершины четны. Применим «метод стирания». Выберем некоторую точку и начнем строить путь. Так как степени всех вершин четны, то они не меньше двух. Поэтому, войдя по некоторому ребру в данную точку, мы всегда можем выйти из нее по второму ребру. Будем отмечать пройденные вершины. Так как число вершин конечно, то на каком то шаге мы перейдем в одну из уже отмеченных вершин и таким образом замкнем цикл. Теперь сотрем этот цикл (естественно, запомнив его где-то) и рассмотрим получившийся граф. Он может оказаться несвязным, но, тем не менее, все его вершины будут иметь четную степень. Применим к этому графу ту же процедуру, и будем это делать до тех пор, пока остается хотя бы один нетривиальный подграф. В результате мы получим несколько циклов, которые не имеют общих ребер, а все вместе образуют исходный граф. Нам остается только склеить эти циклы в один. Возьмем два цикла (…ВАС…) и (…НАМ…), имеющие общую вершину А, разрежем их в этой вершине и склеим по такому правилу: сначала выписываем вершины первого цикла, потом, дойдя до точки А, записываем все вершины второго цикла, а затем продолжаем выписывать оставшиеся вершины первого цикла. Очевидно, что в итоге у нас получится один цикл, который содержит все ребра исходного графа.

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

Предположим теперь, что граф уникурсален. Докажем, что в нем не более двух нечетных вершин. Очевидно, что рисовать такой граф нужно, начиная с нечетной вершины. Причем завершить маршрут нужно в другой нечетной вершине. Если же имеется еще одна нечетная вершина, то она не может быть ни начальной, ни конечной. Поэтому, когда мы в нее заходим, то должны обязательно выйти. Каждый проход через вершину уменьшает число не пройденных ребер, связанных с этой вершиной, ровно на два. В итоге, на каком то шаге в нечетной вершине останется только одно не пройденное ребро, зайдя по которому в вершину мы уже не сможем из нее выйти. Теорема доказана полностью.

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


Существует еще одна очень интересная задача, связанная с графами. В ней требуется отыскать простой цикл, который проходит через все вершины данного связного графа. Эта задача является частным случаем «задачи коммивояжера1», суть которой в следующем. Коммивояжер (разъездной торговец) должен проехать по всем городам некоторого региона и вернуться в исходный пункт. При этом целесообразно так составить маршрут, чтобы в каждом городе побывать ровно один раз (иначе покупатели могут предъявить счет за некачественный товар). У коммерсанта естественно, имеется карта дорог региона.

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

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


Теорема 5. Пусть связный граф имеет не меньше четырех вершин (p>3) и степень каждой вершины не меньше p/2, тогда в графе имеется гамильтонов цикл.


Рассмотрим граф на рисунке 5. У него 6 вершин, при этом пять вершин имеют степень три, и одна степень пять. Согласно теореме, в этом графе существует гамильтонов цикл. Нетрудно проверить, что таким циклом является цикл (AEFDBCA).

Рассмотрим теперь какой-нибудь выпуклый многоугольник. Его вершины будем считать вершинами, а стороны – ребрами, некоторого графа. Степень каждой вершины такого графа равна двум, и для него, очевидно, не выполняются требования теоремы 5. Но, тем не менее, этот граф является гамильтоновым.

Деревья

hello_html_3230241a.gifВажным частным случаем графа является дерево. Это название связано с типичным видом некоторых представителей данного класса. Дадим определение.


Определение 6. Деревом называется связный граф, не содержащий циклов. Несвязный граф, не имеющий циклов, называют лесом. (В лесу, как известно, не меньше двух деревьев.)


На рисунках 6 и 7 приведены примеры деревьев. Как видит читатель, далеко не все они напоминают по форме дерево. Тем не менее, можно так деформировать граф на рисунке 7, что он станет полностью похож на граф с рисунка 6. Нас естественно будет интересовать вопрос о том, когда граф является деревом. Ответ на него сформулируем ниже, а сейчас укажем одно интересное свойство деревьев.


Тhello_html_m5195fa16.gifеорема 6. В любом дереве существует хотя бы одна вершина степени единица. (Такие вершины называют «висячими».)


Доказательство. Используем метод «от противного». Предположим, что в графе нет вершин степени единица. Тогда все вершины имеют степень не меньше двух. Когда мы доказывали теорему 5, то показали, что в подобных графах обязательно существую циклы. Это противоречит тому, что исходный граф – дерево.


Теперь сформулируем теорему, являющуюся признаком дерева.

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

hello_html_6f75503b.gif.


Доказательство. Покажем вначале, что любое дерево обладает указанным свойством. Применим метод «стирания». Так как в дереве (смотри теорему 6) всегда имеются «висячие» вершины, мы сотрем одну такую вершину вместе с выходящим из нее ребром. В результате мы вновь получим дерево, у которого на одно ребро и на одну вершину меньше. Будем продолжать эту процедуру до тех пор, пока граф не превратится в одно единственное ребро, которым соединены две вершины. Для такого графа наша формула очевидна. Заметим также, что процедура стирания на каждом шаге не изменяла разность hello_html_m44299b10.gifp и q на каждом шаге уменьшались ровно на единицу), поэтому исходная разность также равнялась единице.

Теперь объясним идею доказательства того, что из свойства hello_html_6f75503b.gif следует, что граф является деревом. Используем метод «от противного». То есть, будем считать, что в графе имеются циклы. Рассмотрим один из них. Удалим любое ребро, принадлежащее данному циклу, при этом граф останется связным. Будем удалять ребра из графа до тех пор, пока в нем будет хотя бы один цикл. (Пусть таким образом мы удалили hello_html_23584d82.gif ребер.) Когда в графе не останется ни одного цикла, он превратится в дерево, для которого выполняется формула hello_html_m6e84754f.gif, из которой следует, что hello_html_6045105e.gif. Таким образом, мы доказали, что для графов, имеющих циклы, указанная в условии теоремы формула не выполняется.


Одна из важных прикладных задач, относящихся к графам, это отыскание минимального остова2 графа. Поясним, о чем идет речь. Пусть имеется связный граф hello_html_m4794c1bc.gif, необходимо найти такой его подграф, который связен, содержит все вершины исходного графа, и при удалении любого ребра становится несвязным (в этом и заключено условие минимальности). Нетрудно догадаться, что такой минимальный остов является деревом.


Упражнение. Найдите три минимальных остова графа на рис.5.

Планарные графы. Раскраски

Исторически планарные графы связаны с одной знаменитой задачей.

Задача о домиках и колодцах. В некоторой деревне есть три колодца. Трое жителей, живущие в трех стоящих рядом домиках перессорились, и решили так протоптать тропинки от своих домов к каждому из трех колодцев, чтобы они не пересекались. Удастся ли им выполнить свой план?

hello_html_m9a98cba.gif

Пhello_html_68d07694.gifопробуем решить эту задачу. Проведем тропинки так, как это показано на рисунке 8. Как видно, нам удалось провести только восемь тропинок, а девятая должна пересечься хотя бы с одной. Можно доказать (мы не будем приводить строгое доказательство), что эта задача не имеет решения. Дело в том, что по мере проведения тропинок из двух первых домиков, будет получаться некоторый замкнутый контур, внутри которого будет стоять один из колодцев, при этом третий домик будет находиться снаружи от этого контура. Для того чтобы соединить этот домик с колодцем, обязательно потребуется пересечь новой тропинкой одну из уже проложенных.



Можно предложить еще одну задачу.

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

Эта задача также не может быть решена.



На рисунке 9 построены графы hello_html_m63b26e0a.gif и hello_html_m6a86bf44.gif, соответствующие задаче о домиках и колодцах и задаче о пяти хуторах. Оказывается, что проблема укладки графа на плоскости тесно связана с этими типами графов.

Перейдем теперь к более строгим формулировкам.

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



Нhello_html_m73d692fd.gifа рисунке 10 изображен полный граф hello_html_m514e3c16.gif и его плоская укладка.

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



Бhello_html_6a339f64.gifудем говорить, что два графа гомеоморфны, если один из них получен из другого, путем добавления новых вершин на уже имеющиеся ребра.



На рисунке 11 показаны два гомеоморфных графа. Граф справа получен из первого графа добавлением четырех вершин. На практике бывает довольно трудно увидеть, что два графа гомеоморфны.



Теперь сформулируем условие планарности графов.



Теорема 8. Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных hello_html_m63b26e0a.gif и hello_html_m6a86bf44.gif.



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



Замечание. Доказать что граф планарен и построить его плоскую укладку – это две независимых задачи. Заметим, что если граф не имеет пяти вершин, степень которых не меньше четырех, то он наверняка не имеет подграфа, гомеоморфного hello_html_m6a86bf44.gif. Если в графе нет шести вершин, степень которых не меньше трех, то он гарантированно не имеет подграфа, гомеоморфного hello_html_m63b26e0a.gif. Однако построить плоскую укладку графа с достаточно большим количеством вершин бывает непросто.



Рассмотрим теперь еще одну классическую задачу теории графов.



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



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

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



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



Еще одна интересная проблема: сколькими способами можно раскрасить граф3, если имеется n красок.

Оказывается, что число способов раскрашивания является многочленом от n, коэффициенты этого многочлена можно вычислить с помощью специального алгоритма.



Укажем еще одно обобщение задачи о раскрасках. Известно, что граф без самопересечений располагается на некоторой поверхности (на сфере, на торе, на бутылке Клейна и т.п.), какое минимальное количество красок нужно для его раскрашивания?

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

Двудольные графы

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


Определение 8. Граф называется двудольным, если его вершины можно разбить на два класса таким образом, что вершины каждого класса несмежны.

Если каждая вершина одной доли соединена ребром с каждой вершиной другой доли, то такой граф называют полным двудольным графом класса hello_html_2b00cdad.gif, где n и m – количество вершин в каждой доле.



Упражнение. Найдите количество ребер в графе hello_html_d8b09.gif.



Для произвольного графа естественно поставить вопрос: является ли он двудольным? Имеется точное условие, определяющее это свойство. Сформулируем это условие в виде теоремы.



Теорема 10. Граф является двудольным тогда и только тогда, когда все простые циклы, содержащиеся в этом графе, имеют четную длину. (То есть, все простые циклы состоят из четного количества ребер).

Напомним, что простой цикл проходит через каждую свою вершину ровно один раз.

Следует заметить, что, зная, что граф двудольный, весьма непросто разделить вершины этого графа по долям. Укажем один из методов, как это сделать (он, кстати, по сути, является доказательством теоремы).



Разобьем граф на простые циклы. Выберем один из циклов, и будем помечать его вершины через одну двумя разными цветами. Выберем теперь следующий цикл, если у него нет помеченных вершин, то раскрасим их так, как в первом случае, если есть помеченные вершины, то раскраску начнем со смежных им вершин, чередуя цвета так, чтобы соседние вершины были разного цвета. Будем продолжать этот процесс до тех пор, пока не будут покрашены все вершины. (Замечание: целесообразно выбирать новые циклы так, чтобы одна из их вершин уже была помечена.) Вершины одного цвета будут принадлежать одной доле графа, а вершины второго цвета – другой.

Примеры решения задач

Рассмотрим несколько примеров, при решении которых успешно применяются графы.


Задача 1. Один из ребят сказал: «А у нас в классе 25 человек, и каждый дружит ровно с семью одноклассниками!»

«Не может быть этого», - ответил приятелю Витя Иванов, победитель олимпиады. Почему он так ответил?


Решение. Представим всех ребят в классе в виде вершин графа. Получим 25 вершин. Соединим вершины, обозначающие друзей, ребрами. Тогда из каждой вершины будет выходить по семь ребер. Сумма степеней вершин графа будет равна 25x7=175. Это нечетное число. А нам известно, что сумма степеней вершин графа должна быть четна. Получили противоречие.


Задача 2. В стране 15 городов, каждый соединен дорогами не менее чем с 7-ю другими. Докажите, что из любого города можно проехать в любой другой либо напрямую, либо через один промежуточный город.


Решение. Рассмотрим город А. Он соединен дорогами с не менее чем семью городами В1, В2, …, В7, … Всего получилось не меньше 8 городов. Предположим, что есть город С, не связанный ни с А ни с В1, В2, …, В7, … Значит он связан только с теми городами, которые остались вне этого списка. Но таких городов меньше 7, что противоречит условию.


Задача 3. В классе 28 человек. Каждая девочка дружит с 4 мальчиками, а каждый мальчик – с 3 девочками. Сколько в классе мальчиков и девочек?

Решение. В графе, для этой задачи вершины, соответствующие мальчикам, выкрасим синим цветом, а вершины, соответствующие девочкам – красным. Каждое ребро графа соединяет ровно две вершины: одну синюю и одну красную. Пусть всего x красных и y синих вершин (x+y=28 – уравнение №1). Выразим количество ребер в графе. С одной стороны, оно равно 3x, с другой – 4y. Получим уравнение №2: 3x=4y. Решая систему из двух уравнений, легко найти, что x=16 а y=12.

Задача 4. Докажите, что среди учеников любого класса найдутся двое, имеющие одинаковое число знакомых в этом классе (если, конечно, в этом классе не менее двух учеников).

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


Задача 5. Расположите на плоскости 6 точек и соедините их непе­ресекающимися линиями так, чтобы из каждой точки вы­ходили четыре линии.

Решение. Смотри рисунок 12.


Задача 6. В марсианском метро 100 станций. От любой станции до любой другой можно проехать. Забастовочный комитет хочет закрыть проезд через одну из станций так, чтобы между всеми остальными станциями был возможен проезд. Докажите, что такая станция найдётся.

Решение. План марсианского метро является связным графом. Возможны два варианта:

1 случай. Граф является деревом. Тогда этот граф имеет «висячую» вершину. Ее и следует перекрыть.

2 случай. Граф имеет циклы. Тогда нужно перекрыть одну из станций, принадлежащих этому циклу.


Контрольное задание

Представленные ниже задачи являются контрольным заданием для учащихся 8-9 классов. Решения необходимо оформить в отдельной тетради и выслать по адресу:68000, г. Хабаровск, ул. Дзержинского 43, ХКЦТТ.

Для зачета нужно набрать не менее 20 баллов (количество баллов за каждую задачу указано в конце условия), но если вы решите задачи, оцененные ровно в 20 баллов, этого может оказаться недостаточно, так как за недочеты и ошибки баллы снимаются.


М8.3.1. В трёх вершинах правильного пятиугольника располо­жили по фишке. Разрешается передвигать их по диагонали в любую свободную вершину. Можно ли таким образом до­биться того, чтобы одна из фишек вернулась на свое место, а две другие поменялись местами? (5 баллов)

Указание: нетрудно заметить, что ребра такого графа образуют простой цикл, поэтому изменить порядок точек нельзя.


М8.3.2. На математической олимпиаде было предложено 20 за­дач. На закрытие пришло 20 школьников. Каждый из них решил по две задачи, причём выяснилось, что среди при­шедших каждую задачу решило ровно два школьника. До­кажите, что можно так организовать разбор задач, чтобы каждый школьник рассказал одну из решенных им задач, и все задачи были разобраны.(5 баллов)

Указание: постройте двудольный граф, одна доля которого – задачи, а другая – ученики. Каждая вершина этого графа будет иметь степень два. Поэтому данный граф может «развалиться» на несколько непересекающихся простых циклов. Распределите задачи между учениками внутри каждого цикла.


М8.3.3. В спортклубе тренируются 100 толстяков, веса которых равны 1 кг, 2 кг, ..., 100 кг. На какое наименьшее число команд их можно разделить, чтобы ни в какой команде не было двух толстяков, один из которых вдвое тяжелее другого? (10 баллов)


М8.3.4. В тридевятом царстве каждые два города соединены до­рогой с односторонним движением. Докажите, что суще­ствует город, из которого можно проехать в любой другой не более чем по двум дорогам. (10 баллов)


М8.3.5. В городе на каждом перекрестке сходится чётное число улиц. Известно, что с любой улицы города можно проехать на любую другую. Докажите, что все улицы города можно объехать, побывав на каждой по одному разу.(5 баллов)

Указание: используйте признак Эйлерового графа.


М8.3.6. Последовательность из 36 нулей и единиц начинается с пяти нулей. Среди пятёрок подряд стоящих цифр встреча­ются все 32 возможные комбинации. Найдите пять послед­них цифр последовательности. (10 баллов)


М8.3.7. Дан правильный 45-угольник. Можно ли так расста­вить в его вершинах цифры от 0 до 9 так, чтобы для любой пары различных цифр нашлась сторона, концы которой за­нумерованы этими цифрами. (10 баллов)

Указание: рассмотрите полный граф, вершины которого суть цифры от 0 до 9. Задача сводится к его обходу.


М8.3.8. Докажите, что можно расположить по кругу символы 0 и 1 так, чтобы любой возможный набор из n символов, идущих подряд, встретился. (10 баллов)

Указание: рассмотрите граф, вершины которого суть сло­ва длины п-1. Две вершины и и v соединяются стрелкой, если существует слово длины п, у которого и является на­чалом, a v - концом.


М8.3.9. Рёбра дерева окрашены в два цвета. Если в какую-то вершину приходят рёбра только одного цвета, то их все можно перекрасить в другой цвет. Можно ли все дерево сделать одноцветным? (10 баллов)

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


1 В более сложной формулировке этой задачи требуется найти наиболее короткий маршрут

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

3 Здесь граф необязательно должен быть планарен.

Название документа Геометрические задачи.doc

Поделитесь материалом с коллегами:

Математика, 8-10 классы

Геометрические задачи на математических олимпиадах школьников

На любой математической олимпиаде предлагаются геометрические задачи.

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


В этой статье мы рассмотрим несколько примеров таких задач.

Задача 1. Существует ли выпуклый четырехугольник, диагонали которого перпендикулярны, а стороны равны 3, 5, 7, 4.

Решение.

  1. Во-первых, заметим, что рассматриваемый четырехугольник с перпендикулярными диагоналями не обязан быть ромбом или квадратом. Что бы это понять, достаточно построить два взаимно перпендикулярных отрезка, пересекающихся по середине (см. рисунок 1).

  2. Иhello_html_m36bd75e6.gifсследуем свойства, которыми обладают такие четырехугольники.

Запишем теорему Пифагора для прямоугольных треугольников АОВ, ВОС, СОD и DОА:

АВ2=АО2+ВО2, ВС2=ВО2+СО2,

CD2=CO2+DO2, DA2=DO2+AO2. Сложим первую формулу с третьей, а вторую с четвертой:

АВ2+CD2=AO2+BO2+CO2+DO2,

BC2+DA2=AO2+BO2+CO2+DO2.

Правые части в этих уравнениях равны, поэтому приравняем левые части:

АВ2+СD2=BC2+DA2 (1)

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

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

Теперь рассмотрим пример того, как геометрические методы позволяют решать тригонометрические уравнения (и даже системы) и неравенства. Предварительно установим несколько элементарных фактов, касающихся координат векторов.


  1. Вектор hello_html_m602511e.gif имеет единичную длину

  2. Если hello_html_2800003b.gifи hello_html_4d7c4048.gif имеют единичную длину, а вектор hello_html_165cb75c.gif имеет длину два, то hello_html_m58a57b4d.gif.

(это свойство распространяется на любую конечную сумму единичных векторов).


А теперь рассмотрим задачу.

Задача 2. Решите систему уравнений:hello_html_76fc1c18.gif

Решение. Рассмотрим два единичных вектора hello_html_46a27f60.gif и hello_html_m40ff9bef.gif. Левые части уравнений – это координаты суммы hello_html_165cb75c.gif. С другой стороны у вектора hello_html_1e52693b.gif координаты hello_html_7e3af0fc.gif. Найдем длину этой суммы:

hello_html_64dd88a3.gif.

Из этого следует, что векторы hello_html_2800003b.gif и hello_html_4d7c4048.gif – равные, значит, равны и их координаты: hello_html_45cb57d2.gif. Поэтому система сводится к уравнению hello_html_281a0b5d.gif,

hello_html_5d8fa750.gif,

hello_html_6b059156.gif.

Аналогично находим b:

hello_html_69e7b935.gif.

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



Задача 3. Внутри квадрата с единичной стороной построено несколько окружностей, сумма длин которых равна 20. Докажите, что существует прямая, пересекающая по крайней мере 7 окружностей.

Решение. Напомним, что длина окружности вычисляется по формуле hello_html_2f70ced.gif, где hello_html_m3007e811.gif, а hello_html_3c1af8ed.gif – диаметр окружности.

По условию:

hello_html_m36b59f7.gifили

hello_html_m60295db4.gifили

hello_html_4fa33c6c.gifhello_html_4eec69d6.gif
.

Разделим левую и правую части последнего равенства на hello_html_m203e801b.gif. Получим:

hello_html_m5bf77f48.gif.

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

Спроектируем эти окружности на одну из сторон квадрата. Проекцией каждой окружности будет отрезок с длиной, равной диаметру проектируемой окружности. Сумма длин получившихся отрезков больше 6,3 (она равна hello_html_m151794cc.gif).

Это означает, что единичный отрезок покрыт отрезками, сумма длин которых больше 6,3. Следовательно, сторона квадрата «покрыта» в некоторых точках более чем шестью «слоями». Если мы проведем через такую точку прямую, перпендикулярную стороне квадрата, то она «проткнет» больше 6 окружностей. Что и требовалось доказать.



Задачи для самостоятельного решения

  1. Пусть АВCD – выпуклый четырехугольник, стороны которого имеют целочисленную длину. Периметр этого четырехугольника – нечетное число.

а) Могут ли у четырехугольника ABCD быть взаимно перпендикулярные диагонали?

б) Можно ли в этот четырехугольник вписать окружность?

Указание: воспользуйтесь идеей из задачи № 1.

  1. Докажите, что из неравенства hello_html_5234ffbb.gif следует неравенство hello_html_1eeefa69.gif.

Указание: левые части обоих неравенств можно рассматривать как соответственно первые и вторые координаты суммы n единичных векторов с координатами hello_html_m65da5f49.gif. Эта сумма имеет длину не больше n.

  1. Из какого наименьшего количества фигурок вида:

Мhello_html_m43b1e1e4.gif
ожно сложить квадрат (фигурки нельзя накладывать друг на друга. Квадрат не может иметь «дырок»).

Указание: нужно не только представить пример, но и доказать, что не существует конструкций с меньшим числом фигурок.

  1. Докажите, что любой треугольник можно разрезать не более чем на три части, из которых складывается равнобедренный треугольник.

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

Название документа Графы и их применение.doc

Поделитесь материалом с коллегами:

Учащимся 8 - 9 классов

Графы и их применение

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

С помощью графов удобно и наглядно изображается информация о разных объектах и отношениях между ними. Рассмотрим пример.


hello_html_23396a93.gifПример 1. В розыгрыше финальной части турнира участвуют семь команд: шесть команд, набравших наибольшее количество очков в предварительной части турнира и команда – победитель прошлого года. Сначала играют друг с другом первые шесть команд, затем три команды, одержавшие победы и команда, победитель прошлого года, играют друг с другом. Два победителя этого тура встречаются в финале.

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


Определение 2. Степенью вершины графа называется число выходящих из него ребер.

Для степени вершины принято следующее обозначение: deg(A).

Рассмотрим некоторый граф . Обозначим количество его вершин буквой p, а количество ребер буквой q. Сформулируем в виде теорем простейшие свойства степени.


Теорема 1. Сумма степеней всех вершин графа равна удвоенному количеству его ребер (2q).

Граф называют простым, если две вершины соединяет не более одного ребра, в противном случае, граф называют мультиграфом.


Теорема 2. В простом графе найдется не менее двух вершин с одинаковыми степенями.

Теорема 3. В простом графе с p вершинами число ребер не большеhello_html_66865472.gif:

hello_html_6bdca55c.gif.

Определение 3. Граф называется полным, если каждая его вершина соединена со всеми другими вершинами.


Примеры полных графов вы можете построить сами: нарисуйте выпуклый многоугольник и постройте все его диагонали. В полном графе с p вершинами hello_html_66865472.gif ребер.

Пути, циклы, связность

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


Определение 4. Путем (из вершины А в вершину В) в графе называется последовательная цепочка смежных ребер, которая начинается в вершине А и заканчивается в вершине В. Путь может проходить через ребро только один раз.


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



Определение 4. Циклом называется путь, у которого начало и конец совпадают.


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


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


Теорема 4 (Эйлера). Связный граф уникурсален тогда и только тогда, когда степени всех его вершин четны или у него ровно две вершины нечетной степени.


Существует еще одна очень интересная задача, связанная с графами. В ней требуется отыскать простой цикл, который проходит через все вершины данного связного графа. Эта задача является частным случаем “задачи коммивояжера”, суть которой в следующем. Коммивояжер (разъездной торговец) должен проехать по всем городам некоторого региона и вернуться в исходный пункт. При этом целесообразно так составить маршрут, чтобы в каждом городе побывать ровно один раз (иначе покупатели могут предъявить счет за некачественный товар). У коммерсанта, естественно, имеется карта дорог региона.

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

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


Теорема 5. Пусть связный граф имеет не меньше четырех вершин (p>3) и степень каждой вершины не меньше p/2, тогда в графе имеется гамильтонов цикл.


hello_html_76e4b5f.gifДеревья

Важным частным случаем графа является дерево. Это название связано с типичным видом некоторых представителей данного класса. Дадим определение.


Определение 7. Деревом называется связный граф, не содержащий циклов. Несвязный граф, не имеющий циклов, называют лесом. (В лесу, как известно, не меньше двух деревьев.)


Нhello_html_46666a57.gifа рисунках 2 и 3 приведены примеры деревьев. Как видите, далеко не все они напоминают по форме дерево. Тем не менее, можно так деформировать граф на рисунке 3, что он станет полностью похож на граф с рисунка 2. Нас будет интересовать вопрос о том, когда граф является деревом. Ответ на него сформулируем ниже, а сейчас укажем одно интересное свойство деревьев.


Теорема 6. В любом дереве существует хотя бы одна вершина степени единица. (Такие вершины называют “висячими”.)



Теперь сформулируем теорему, являющуюся признаком дерева.

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

hello_html_6f75503b.gif.

Одна из важных прикладных задач, относящихся к графам, это отыскание минимального остова1 графа. Поясним, о чем идет речь. Пусть имеется связный граф hello_html_m4794c1bc.gif, необходимо найти такой его подграф, который связен, содержит все вершины исходного графа, и при удалении любого ребра становится несвязным (в этом и заключено условие минимальности). Нетрудно догадаться, что такой минимальный остов является деревом.

Пhello_html_6493ee31.gif
ланарные графы. Раскраски

Исторически планарные графы связаны с одной знаменитой задачей.

Задача о домиках и колодцах. В некоторой деревне есть три колодца. Трое жителей, живущие в трех стоящих рядом домиках перессорились, и решили так протоптать тропинки от своих домов к каждому из трех колодцев, чтобы они не пересекались. Удастся ли им выполнить свой план?


Попробуем решить эту задачу. Проведем тропинки так, как это показано на рисунке 4. Как видно, нам удалось провести только восемь тропинок, а девятая должна пересечься хотя бы с одной. Можно доказать (мы не будем приводить строгое доказательство), что эта задача не имеет решения. Дело в том, что по мере проведения тропинок из двух первых домиков, будет получаться некоторый замкнутый контур, внутри которого будет стоять один из колодцев, при этом третий домик будет находиться снаружи от этого контура. Для того чтобы соединить этот домик с колодцем, обязательно потребуется пересечь новой тропинкой одну из уже проложенных.


Можно предложить еще одну задачу.

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

Эта задача также не может быть решена.


На рисунке 5 построены графы hello_html_m63b26e0a.gif и hello_html_1990f2ed.gif, соответствующие задаче о домиках и колодцах и задаче о пяти хуторах. Оказывается, что проблема укладки графа на плоскости тесно связана с этими типами графов.


Перейдем теперь к более строгим формулировкам.

hello_html_3781799c.gif

Определение 8. Граф называется планарным, если его можно изобразить на плоскости без самопересечений. Такое изображение называют плоской укладкой графа.


На рисунке 6 изображен полный граф hello_html_m514e3c16.gif и его плоская укладка.

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


Бhello_html_m4aaeed32.gif
удем говорить, что два графа
гомеоморфны, если один из них получен из другого, путем добавления новых вершин на уже имеющиеся ребра.

На рисунке 7 показаны два гомеоморфных графа. Граф справа получен из первого графа добавлением четырех вершин. На практике бывает довольно трудно увидеть, что два графа гомеоморфны.

Теперь сформулируем условие планарности графов.

Теорема 8. Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных hello_html_m63b26e0a.gif и hello_html_m6a86bf44.gif.


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


Замечание. Доказать что граф планарен и построить его плоскую укладку – это две независимых задачи. Заметим, что если граф не имеет пяти вершин, степень которых не меньше четырех, то он наверняка не имеет подграфа, гомеоморфного hello_html_m6a86bf44.gif. Если в графе нет шести вершин, степень которых не меньше трех, то он гарантированно не имеет подграфа, гомеоморфного hello_html_m63b26e0a.gif. Однако построить плоскую укладку графа с достаточно большим количеством вершин бывает непросто.


Рассмотрим теперь еще одну классическую задачу теории графов.


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


Еще одна интересная проблема: сколькими способами можно раскрасить граф2, если имеется n красок.

Оказывается, что число способов раскрашивания является многочленом от n, коэффициенты этого многочлена можно вычислить с помощью специального алгоритма.

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

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


Формула Эйлера

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

Теорема 10. В любом плоском графе выполняется соотношение: pq + r =2.


З

Рисунок 8. Граф для примера 2.

амечание. Внешняя грань также считается.


Пример 2. Проверим формулу Эйлера для графа, изображенного на рис. 8.

Число вершин р = 7, число ребер q = 11, число граней r = 6. Подставим в формулу и получим верное равенство: 7 -11 +6 = 2.


Дополнение графа. Регулярный граф

О

Рисунок 9. Граф Г и его дополнение


hello_html_50f49bae.png
пределение 9.
Дополнением hello_html_m34a6f1d0.gif графа Г с множеством вершин p и множеством ребер q называется простой граф со множеством вершин p, в котором две вершины смежны тогда и только тогда, когда они не смежны в Г.

На рис.9 изображен граф Г и его дополнение hello_html_m34a6f1d0.gif.


Определение 10. Граф, у которого все вершины имеют одну и ту же степень, называется регулярным.

Примерами регулярных графов являются полные графы.

Примеры решения задач

Рассмотрим несколько примеров, при решении которых успешно применяются графы.

Задача 1. На небольшом предприятии каждый рабочий имеет по 2 специальности. Всего специальностей 4, причем на каждой специальности занято по 3 рабочих. Сколько рабочих на предприятии? Изобразите решение в виде графа.


Р


Рисунок 10. К задаче № 1



hello_html_25658aaa.png
ешение.
В графе для этой задачи вершины, соответствующие рабочим, обозначим звездочкой, а вершины соответствующие специальностям – кружочком. Каждое ребро графа соединяет ровно две вершины: одну звездочку и один кружочек, причем количество кружочков - 4. Обозначим за
х количество рабочих, тогда 2х = hello_html_7e0730ec.gifhello_html_63a65cb4.gif= 6. Решение в виде графа изображено на рис. 10.


Задача 2. Удалите ребро (А,У) графа рис.11 и начертите полученный после этого планарный граф (т.е. граф, у которого ребра – непересекающиеся прямолинейные отрезки).


Рhello_html_m33b955dd.png
ешение.
На рис.12 изображен граф без ребра (А,У), чтобы получить планарный граф (т.е. чтобы ребра (Z,B) и (G.,X) не пересекались) нужно расположить вершины так, как показано на рис. 13.

Рисунок 11 Рисунок 12 Рисунок 13


Задача 3. Нарисовать все регулярные графы степени 3 с не более чем 8 вершинами.


Решение. Нам нужно изобразить такие графы, чтобы из каждой вершины выходило по три ребра. Это легко сделать для графов, у которых 4, 6 или 8 вершин ( смотри рис. 14).

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

hello_html_2afe3266.gif

Рисунок 14. Примеры регулярных графов.


Контрольное задание

Представленные ниже задачи являются контрольным заданием для учащихся 8-9 классов. Решения необходимо оформить в отдельной тетради и выслать по адресу:68000, г. Хабаровск, ул. Дзержинского 43, ХКЦТТ.

Для зачета нужно набрать не менее 20 баллов (количество баллов за каждую задачу указано в конце условия), но если вы решите задачи, оцененные ровно в 20 баллов, этого может оказаться недостаточно, так как за недочеты и ошибки баллы снимаются.

  1. Найдите минимальное количество вершин, необходимых для построения простого графа с шестью ребрами. Изобразите его. (5 баллов)


  1. Проверьте формулу Эйлера для графа на рисунке 13. Выполнима ли она для графов на рис. 11,12? (5 баллов)


  1. Изобразите все возможные простые графы, имеющие 4 вершины. (5 баллов)


  1. Сколькими способами можно нарисовать домик (рис. 15) не отрывая карандаш от бумаги. Напишите пути прохождения. (Замечание: каждое ребро можно пройти только один раз). (5 баллов)


  1. Докажите формулу Эйлера для дерева. (10 баллов)

Уhello_html_41dfe21a.png
казание:
Воспользуйтесь методом стирания, т.е. постепенно удаляйте «висячие» вершины и соответствующие им ребра.


  1. Докажите, что дополнение полного графа является полностью несвязным графом. (10 баллов)


  1. Найдите минимальное количество цветов, необходимых для раскраски каждой вершины дерева так, чтобы смежные вершины всегда имели различные цвета. (10 баллов)



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

2 Здесь граф необязательно должен быть планарен.

Название документа ЗАДАЧИ.doc

Поделитесь материалом с коллегами:

Задачи и решения МАТЕМАТИЧЕСКОЙ олимпиады

9 Класс

Задача 1. Доказать, что

hello_html_m46a50677.gif

для любого вещественного x. (Напомним, что [x] – это целая часть вещественного числа.)

Решение. Положим, что hello_html_594adb26.gif, где a - целая, а - дробная часть этого числа. Рассмотрим три случая.

1. hello_html_26035b42.gif. Тогда левая часть выражения равна:

hello_html_m7c05f0a0.gif.

2. hello_html_324a3f7f.gif. Тогда левая часть выражения равна:

hello_html_590ce213.gif.

hello_html_613130.gif. Тогда левая часть выражения равна:

hello_html_5ef87c17.gif.

Нужное тождество доказано.


Задача 2. Доказать, что для любых натуральных n и m выполнено:

hello_html_6faf1ad6.gif

Решение. Заметим, что

hello_html_m6412d6b9.gif

Так как hello_html_1caef8ee.gif - иррационально, то hello_html_485f0256.gif. Поэтому

hello_html_m1529b178.gif

что и требовалось доказать.

Задача 3. Пусть сумма n действительных чисел hello_html_1ce85488.gifhello_html_m2d64bf8c.gifнеотрицательна. Доказать, что среди этих чисел можно выбрать такое, что сумма оставшихся будет неотрицательна.

Решение. Доказательство легко получить методом «от противного».


Задача 4. Пусть АВС – остроугольный треугольник и D – середина BC. Выберем на отрезке AD произвольную точку E и обозначим через M ее проекцию на BC. В свою очередь, точки P и N есть проекции M на AC и AB. Доказать, что угол MPE равен углу MNE.

Решение. Пусть B и C – точки пересечения со сторонами AC и AB прямой, проходящей через E и параллельной BC. Так как hello_html_m551dee49.gif, а отрезок EM перпендикулярен BCи BC, то треугольник BCM – равнобедренный. Кроме того, четырехугольники MPBE и MECN вписаны в окружности (у них по паре прямых противоположных углов). Поэтому имеет место цепочка равенств для углов:

hello_html_m7e5fa8db.gif.

Что и требовалось доказать.


10 класс

Задача 1. В прямоугольнике ABCD точка M – середина стороны BC, N – середина стороны CD. P – точка пересечения отрезков DM и BN. Докажите, что угол MAN равен углу BPM.

Решение. Пусть точка N – середина стороны AB. Отрезок DN параллелен отрезку BN. Поэтому последовательно равны углы

hello_html_27175209.gif.

А это и требовалось доказать.


Задача 2. На плоскости имеются правильные многоугольники с числом сторон 34 и 55. Построить с помощью циркуля и линейки правильный 3455=1870 – угольник.

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

hello_html_m4b8da124.gifи hello_html_7f1ab9a1.gif.

Заметим, что

hello_html_m30e9eca1.gif

Поэтому, отложив угол 13 раз, и угол 21 раз, с последующим вычитанием, получим нужный угол, определяющий правильный 1870 – угольник.


Задача 3. Пусть x и y - положительные числа, для которых выполнено:

hello_html_m70713197.gif

Доказать, что

hello_html_m40432ad5.gif

Решение. Неравенство легко преобразуется к виду

hello_html_m3d345d6b.gif

Поскольку

hello_html_55dd0e09.gif

то

hello_html_9743680.gif

А это и требовалось доказать.


Задача 4. Обозначим через hello_html_m4ce40cef.gifhello_html_m242d4ef9.gif количество всех пар простых чисел hello_html_m37317a52.gif, сумма которых равна m. Иными словами:

hello_html_m13111d4.gif, hello_html_m37317a52.gif - простые числа.

Например hello_html_m31190093.gif, поскольку 4=2+2; hello_html_m22afd8e1.gif, поскольку 5=2+3=3+2. Доказать, что для любого натурального hello_html_3f4a573f.gifвыполняется равенство

hello_html_fbe2c4.gif

где суммирование проводится по всем простым числам hello_html_7b948384.gif

Решение. Заметим, что интересующая нас сумма равна

hello_html_1f34cfb.gif

где в каждой из четырех сумм суммирование производится по всем возможным разбиениям hello_html_7c06db6e.gif на три простых. Поскольку hello_html_2fa1253c.gif входят в разбиение симметрично, то все эти суммы равны между собой. Следовательно, исходная сумма равна нулю и тождество доказано.


11 Класс

Задача 1. Пусть O – внутренняя точка квадрата ABCD со стороной AB=1, для которой выполняется равенство

hello_html_m3e7fd164.gif

Доказать, что O – центр квадрата.

Решение. Пусть x и y – расстояния от точки O до сторон AD и AB соответственно. С помощью теоремы Пифагора выразим через эти числа искомое выражение и преобразуем его к виду:

hello_html_55ca41bd.gif

Как видно из этого выражения, оно рано 2 только если оба квадрата равны нулю, то есть, если hello_html_m7542cbc7.gif. А это и требовалось доказать.


Задача 2. Доказать, что hello_html_m7d129a2e.gif - иррациональное число.

Решение. Предположим, что это верно, и

hello_html_m9cada3f.gif- рациональное число.

Поскольку hello_html_m383ffc9e.gif то рациональными будут также числа:

hello_html_5e66590b.gif

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


Задача 3. Величины и острых углов удовлетворяют равенству

hello_html_m2a998ed2.gif

Доказать, что hello_html_257346f5.gif.

Решение. Из условия следует, что

hello_html_515dca70.gif.

Если hello_html_34803fbb.gif и hello_html_m9392c42.gif, то hello_html_738dbeab.gif - противоречие. Точно также получается противоречие, если обратить знаки в двух предыдущих неравенствах. Значит, hello_html_m15a5cd15.gif и hello_html_m1e06b986.gif. Следовательно hello_html_257346f5.gif. Что и требовалось доказать.


Задача 4. Бесконечная последовательность натуральных чисел hello_html_m4ece3b21.gif такова, что для любого целого hello_html_580a006e.gif выполнено

hello_html_5c9c9deb.gif

Доказать, что hello_html_m223e1762.gif делится на hello_html_3b9a83e.gif при всех натуральных m.

Решение. Заметим, что

hello_html_476c1c46.gif

Математической индукцией по m можно легко показать, что второй множитель в правой части полученного выражения делится на hello_html_3b9a83e.gif.Что и требовалось доказать.


Название документа Задачи для подготовки к олимпиаде.doc

Поделитесь материалом с коллегами:















































Задачи

для подготовки к олимпиадам

по математике



hello_html_483a9622.gif












  1. В лесу растет миллион елок. Известно. Что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым количеством иголок.

  2. В классе 35 учеников. Можно ли утверждать , что среди них найдутся хотя бы два ученика, фамилии которых начинаются с одной буквы?

  3. В мешке лежат 10 белых и 10 черных шаров. Они тщательно перемешаны и неразличимы на ощупь. Какое наименьшее число шаров нужно вынуть из мешка вслепую, чтобы среди них наверняка оказались два шара: 1) одного цвета. 2) разного цвета.

3)белого цвета ?

  1. Верно ли , что из любых трех целых чисел можно выбрать два, сумма которых четна?

  2. В школе 33 класса, 1150 учеников. Найдется ли класс, в котором меньше 35 учеников ?

  3. Можно ли увезти 50 камней весом 370, 372, 374, 376, … , 466, 468 кг на семи трехтонках ?

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

  5. Можно ли доску размером 5×5 заполнить доминошками размером 1×2 ?

  6. 16 корзин расположили по кругу. Можно ли в них расположить 55 арбузов так, чтобы количество арбузов в соседних клетках отличалась на 1 ?

  7. Можно ли выпуклый девятиугольник разрезать на четырехугольники ?

  8. Сумма 2006 натуральных чисел – нечетное число. Каким числом: четным или нечетным является произведение этих чисел?

  9. На доске написано в строку 2003 целых числа. Докажите, что из них можно стереть одно число так, чтобы сумма остальных чисел будет четной.

  10. Учитель написал на листе бумаги число 10. 25 учеников передают листок друг другу, и каждый прибавляет или отнимает единицу- как хочет. Может ли после того, как последний ученик проделает свою операцию над числом, на листе оказаться число 0 ?



14) Можно ли по правилам игры в домино выложить костей в одну цепочку так, что бы сумма на ее концах была

нечетной ?

  1. Страницы книги пронумерованы подряд с первой до последней. Хулиган Вася вырвал из разных мест книги 17 листов и сложил

номера всех страниц. У него получилось 2002. Правильно ли сосчитал Вася?

  1. Сравните: 792 и 891

  2. На какую цифру оканчивается число 19992007 ?

  3. Вычислите: hello_html_m37ed852.gif

  4. Вычислите:

hello_html_m6db979be.gif


  1. Вычислите: -90-89-88-…-1+0+1+2+…+98+99+100

  2. докажите , что 13+132+133+134+…+132001+132002 делится на 7.

  3. Сравните: hello_html_m3ae9c776.gif+ hello_html_4017b095.gif и 2hello_html_7fbe0b4e.gif

  4. Сравните: hello_html_m15394a32.gif и hello_html_896ba37.gif.

  5. ( Древняя китайская задача) 5 буйволов и 2 барана стоят 10 ланов золота. 2 буйвола и 5 баранов стоят 8 ланов золота. Сколько стоят буйвол и баран?

  6. Магазин продал одному покупателю 25% имеющегося в куске полотна, второму -30% остатка, а третьему – 40% нового остатка. Сколько % полотна осталось непроданным?

  7. Однажды балда предложил черту заработать. «Как только перейдешь этот мост, - сказал он, - твои деньги удвоятся. Можешь переходить по нему сколько хочешь раз, но после каждого раза отдавай мне за это 24 копейки» черт согласился и … после третьего перехода остался без денег. Сколько денег было у черта сначала?

  8. Три землекопа за три часа выкопали три ямы. Сколько ям выкопают шесть землекопов за пять часов?

Название документа Задачи и решения.doc

Поделитесь материалом с коллегами:

ЗАДАЧИ И РЕШЕНИЯ

9 КЛАСС

Задача 1. Найти все решения системы

hello_html_m7cc0e4e4.gif

Решение. Из первого уравнения следует, что hello_html_564cdb90.gif и hello_html_7b24b480.gif. Посколькуhello_html_m3fec9196.gif то hello_html_m3e92f923.gif и hello_html_m30b925cd.gif. Если x и y одновременно больше нуля, то каждое из них строго меньше единицы. Тогда hello_html_m180d5a31.gif чего не может быть. В оставшихся случаях получаем пары решений x=0, y=1; x=1, y=0.

Задача 2. Доказать, что любой треугольник можно разрезать на четыре равнобедренных треугольника.

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

Задача 3. Найти пять натуральных чисел n, которые нельзя представить в виде суммы простого числа и квадрата натурального.

Решение. Докажем, что среди чисел 22, 32,…, k2,…,142 пять не представляются суммой простого и квадрата. Предположим, что это не так и k2=p+l2, где p - простое и l - натуральное. Тогда p=k2-l2=(k-l)(k+l).

Поскольку p - простое, то k-l=1, k+l=p. Отсюда следует, что hello_html_3621a17c.gif.

Легко проверить, что при k=5,8,11,13,14 число p=2k-1- не простое. Следовательно, 52, 82, 112, 132, 142 не представляются суммой простого и квадрата натурального.

З

hello_html_4cbcbd90.pngРисунок 1

адача 4. Какое максимальное количество точек можно расположить на плоскости так, чтобы любые две из них были соединены отрезками, попарно не пересекающими друг друга. (Внимание! Концы отрезков могут совпадать.)

Решение. На рисунках видно, как располагаются соответствующие системы точек при n=3 и n=4. Пятую точку нельзя добавить при любом расположении A1, A2, A3, A4. Дело в том, что если она располагается вне треугольников, то ее нельзя соединить с A4, а если она находится внутри одного из них, то ее нельзя соединить без пересечений сторон с оставшейся четверкой.


ЗАДАЧИ И РЕШЕНИЯ

10 КЛАСС

Задача 1. Найти все решения системы

hello_html_m4252dff7.gif

Решение. Заметим, что из hello_html_m5269a224.gif. Поэтому

hello_html_m7ea60639.gif.

Следовательно, hello_html_60a65c6c.gif,

hello_html_77439cca.gif

Для z=1 из второго уравнения исходной системы немедленно следует, что x=y=0.

В случае hello_html_m4de93524.gif

hello_html_m256d6e29.gif.

При этом

hello_html_2f70e847.gif

Если x=0, то y=1. Если x=1, то y=0. Окончательно находим, что x=1, y=0, z=0; x=0, y=1, z=0; x=0, y=1, z=0 - все решения системы уравнений.


З

hello_html_m31c18c42.pngРисунок 2

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

Решение. Пусть ABC - прямоугольный треугольник с прямым углом при вершине C, для которого ABC больше СAB. Отметим на AC точку K так, чтобы AK=KB. Выберем на AB точки M и N из условий AM=MK и BN=NK. В этом случае треугольник BKC - прямоугольный, а треугольники AMK, KMN, KNB - равнобедренные. Это и требовалось доказать.


Задача 3. Найти десять натуральных чисел, которые нельзя представить в виде суммы простого числа и куба натурального числа.

Решение. Докажем, что среди кубов k3 можно выбрать десять чисел, не представимых в виде суммы простого и куба натурального. Если k3=p+l3, то p=k3-l3=(k-l)(k2+kl+l2). Поскольку p - простое, то k-l=1, p=k2+kl+l2. То есть, l=k-1 и p=k2+k(k-1)+(k-1)2= 3k2-3k+1. Последнее число не простое при k=7n-1 (n=1,2,3,…), поскольку

p=3(7n-1)2-3(7n-1)+1=372n2-67n+3-37n+3+1=7(21n2-9n+1).

То есть, оно делится на 7. Поэтому десять чисел 6, 13, 20, …, 69 удовлетворяют условиям задачи.


Задача 4. Построить две последовательности строго возрастающих натуральных чисел

an (n=1,2,…) bn (n=1,2,…), для которых an-bn=(-1)nn (n=1,2,…).

Решение. Положим a(n)=2n2+(-1)nn и b(n)=2n2. Для них a(n)-b(n)=(-1)nn. Последовательность b(n) строго возрастает.

Докажем то же самое про a(n). Заметим, что a(n+1)-a(n)=2(n+1)2+(-1)n+1(n+1)-2n2-(-1)n= =2n2+4n+2-(-1)nn-(-1)n-2n2-(-1)nn= 4n-2(-1)nn+2-(-1)n 2n+1.

Следовательно, a(n+1)>a(n) для любого натурального n. То есть, a(n) строго возрастает.


ЗАДАЧИ И РЕШЕНИЯ

11 КЛАСС


Задача 1. Решить систему уравнений

hello_html_58f82483.gif

Решение. Из уравнений следует, что |x| 1. Если |x|=1, то y=z=0. Пусть |x|<1. Поскольку |y|<1 и |z|<1, то 1=x4+2y4+3z4>x6+2y6+3z6=1. Мы получили противоречие. Следовательно, x=1, y=0, z=0; x=-1, y=0, z=0 - все решения системы.


Задача 2. Построим из рациональных чисел r=a/q (a - целое, q - натуральное) лабиринт по следующим правилам:

1) любое рациональное число r - комната лабиринта;

2) две комнаты r1 и r2 соединены проходом, если r1 r2=1 или разность (r1-r2) - целое число.

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

Решение. Сначала докажем, что любую рациональную точку r=a/q00 можно соединить с нулем некоторым путем. Разделив целое a на натуральное q0 с остатком, получим

hello_html_502ef395.gifс hello_html_m552b7ac1.gif.

Здесь q1 - остаток от деления. При этом для r1=q1/q0 разность hello_html_18ebc20a.gif- целое число. Если r1=0 (a делится на q0), то r и r1 соединены проходом.

Пусть теперь r10. Тогда q10 и для r2=q0/q1 выполняется равенство r1r2=1. Следовательно,

hello_html_m342e6cf5.gif

- путь из r в r2. Напомним, что при этом hello_html_m552b7ac1.gif. Повторяя это рассуждение с r2 вместо r и так далее, мы в конце концов попадем в ноль, поскольку знаменатели получающихся дробей на каждом шаге уменьшаются. Для произвольных ненулевых рациональных r и r' (по доказанному) найдутся пути

hello_html_1d1d24a3.gif

hello_html_m4cfea8bd.gif

Обращая стрелки во втором, получим путь

hello_html_26cc63dc.gif

из r в r'. Утверждение полностью доказано.


Задача 3. Пусть в треугольнике ABC AB=15, BC=7, AC=20. Доказать, что

hello_html_2ee01ac3.gif.

Р

hello_html_8c823c2.pngРисунок 3

ешение. Поскольку 72+152<202, то угол B- тупой.

На продолжении AB отметим точку H - основание высоты из вершины C. Применяя два раза теорему Пифагора, получим равенства

(15+BH)2+HC2=202, BH2+HC2=72.

Вычитая из первого второе, находим

hello_html_m46188f00.gif.

Поэтому

hello_html_m6981c4b1.gif

Из этих вычислений следует, что

hello_html_m5d093b72.gif

То есть, BC - биссектриса угла ACH в прямоугольном треугольнике AHC. Следовательно, hello_html_2ee01ac3.gif. А это и требовалось доказать.


Задача 4. Многочлен ax3+bx2+cx при целых значениях x принимает только целые значения. Доказать, что 6a - целое число.

Решение. Пусть f(x)=ax3+bx2+cx. Заметим, что

hello_html_m33d05942.gif

hello_html_4082d352.gif

hello_html_e472d3e.gif

Поскольку при целых x f(x) принимает только целые значения, то этим же свойством обладают g(x), h(x), r(x). Значит 6a=r(x)- целое число.


Название документа МЕТОД ИНДУКЦИИ.doc

Поделитесь материалом с коллегами:

МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ

I. Введение

Утверждения подразделяются на общие и частные. Приведем пример общего утверждения: во всяком параллелограмме диагонали в точке пересечения делятся пополам.

Соответствующим примером частного утверждения является следующее: в параллелограмме ABCD диагонали в точке пересечения делятся пополам.

Переход от общих утверждений к частным называется дедукцией. Рассмотрим пример:

Все числа, оканчивающие нулем, делятся на 5. (1)

140 – число, оканчивающееся на ноль. (2)

140 делится на 5. (3)

Из общего утверждения (1) при помощи утверждения (2) получено частное утверждение (3).

Переход от частных утверждений к общим называется индукцией. Индукция может привести как в верным, так и к неверным выводам. Разберем два примера:

140 делится на 5. (1)

Все числа, оканчивающиеся нулем, делятся на 5. (2)

Из частного утверждения (1) получено общее утверждение (2). Утверждение (2) верно.

140 делится на 5. (1)

Все трехзначные числа делятся на 5. (2)

Из частного утверждения (1) получено общее утверждение (2). Утверждение (2) неверно.

Спрашивается, как пользоваться в математике индукцией, чтобы получать только верные ответы? Ответ на этот вопрос и дается в этой статье.

Если имеется утверждение, справедливое в нескольких частных случаях, а все частные случае рассмотреть невозможно. Как же узнать, справедливо ли вообще это утверждение?

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

В основе этого метода лежит принцип математической индукции, заключающийся в следующем:

Утверждение справедливо для всякого натурального n, если:

  1. оно справедливо для n = 1

  2. из справедливости утверждения для какого-либо произвольного натурального n = k следует его справедливость для n = k+1.

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

Теорема 1. Утверждение справедливо для n = 1.

Теорема 2. Утверждение справедливо для n = k+1, если оно справедливо для n = k, где k – какое-либо произвольное натуральное число.

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

Пример 1. Вычислить сумму

Sn = 1/1*2 + 1/2*3 + 1/3*4 + … + 1/n(n+1).

Мы знаем, что

S1 = ½; S2 = 2/3; S3 = ¾; S4 =4/5.

Рассмотрение сумм S1, S2, S3 и S4 позволяет высказать гипотезу, что Sn = n/n+1, при всяком натуральном n. Для проверки гипотезы воспользуемся методом математической индукции.

Теорема 1. Для n = 1 гипотеза верна, так как S1 = ½.

Теорема 2. Предположим, что гипотеза верна и для n = k, т.е. что

Sk = 1/ 1*2 + 1/2*3 + … + 1/k(k+1) = k/(k+1),

Где k – некоторое натуральное число. Докажем, что тогда гипотеза обязана быть верной и для n = k+1, т.е. что

Sk+1 = Sk +1/(k+1)(k+2);

Следовательно, по условию теоремы,

Sk+1 = k/(k+1) + 1(k+1)(k+2) = (k2 + 2k +1)/(k+1)(k+2) = (k+1)/ (k+2).

Обе теоремы доказаны. Теперь на основании принципа математической индукции мы утверждаем что

Sn =n/n+1.

Замечание. Необходимо подчеркнуть, что доказательство методом математической индукции, безусловно, требует доказательства обеих теорем 1 и 2.


Пример 2. Теорема. Всякое натуральное число равно следующему за ним натуральному числу.

Доказательство проведем методом математической индукции. Предположим, что

k = k + 1 (1)

Докажем, что

k + 1 = k + 2 (2)

Действительно, прибавив к каждой части равенства (1) по 1, получим равенство (2). Выходит, что если утверждение справедливо для n= k, то оно справедливо и для n = k+1. Теорема доказана.

Следствие. Все натуральные числа равны.

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

Теоремы 1 и 2 имеют свое особое значение. Теорема 1, так сказать, создает базу для проведения индукции. Теорема 2 дает право неограниченного автоматического расширения этой базы, право перехода от данного частного случая к следующему, от n к n+1.

Если не доказана теорема 1, а доказана теорема 2, то, следовательно, не создана база для проведения индукции, и тогда бессмысленно применять теорему 2, так как и расширять-то, собственно, нечего.

Если не доказана теорема 2, а доказана только теорема 1, то, хотя база для проведения индукции и создана, право расширения этой базы отсутствует.

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

Чтобы не повторять без конца слова «Теорема 1» и «Теорема 2», мы условимся в дальнейшем помечать первую и вторую части доказательства по индукции знаками 1° и 2°.

II. Доказательства тождеств: задачи арифметического характера

Пример 1. Выпишем в порядке возрастания положительные нечетные числа 1, 3, 5, 7, … Обозначим первое из них u1, второе u2, третье u3 и т. д., т .е.

u1 = 1, u2 = 3, u3 = 5, u4 = 7, ..……

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

Решение: Первое нечетное число u1 можно записать так:

u1= 2*1 – 1; (1)

второе нечетное число можно записать так:

u2 = 2*2 – 1; (2)

третье нечетное число можно записать так:

u3 = 2*3 – 1. (3)

Внимательно рассматривая равенства (1), (2), (3), можно высказать гипотезу, что для получения любого нечетного числа, достаточно от удвоенного номера его отнять 1, т.е. для n-го нечетного числа имеем формулу

un = 2n – 1. (4)

Докажем, что эта формула справедлива.

1°. Равенство (1) показывает, что для n = 1 формула (4) справедлива.

2°. Предположим, что формула (4) справедливо для n = k, т.е. k-е нечетное число имеет вид

uk = 2k – 1.

Докажем, что тогда формула (4) обязана быть справедливой и для (k+1)-го нечетного числа, т.е. что (k+1)-е нечетное число имеет вид

uk+1 = 2(k+1) – 1,

или, что все равно,

uk+1 = 2k + 1.

Для получения (k+1)-го нечетного числа достаточно к k-му нечетному числу прибавить 2, т.е.

uk+1 = uk + 2.

Но, по условию, uk+1 = (2k-1). Значит,

uk+1 = (2k-1) + 2 = 2k +1,

что и требовалось доказать.

Ответ: un = 2*n – 1.


Пример 2. Вычислить сумму первых n нечетных чисел.

Решение. Обозначим искомую сумму Sn, т.е.

Sn = 1 + 3 + 5 + … (2n – 1).

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

Придаем n последовательно значения 1, 2, 3, … до тех пор, пока у нас не накопится достаточно материала, чтобы на основе его построить более или менее надежную гипотезу. После этого останется только эту гипотезу проверить методом математической индукции.

Имеем,

S1 =1, S2 = 4, S3 = 9,

S4 = 16, S5 = 25, S6 = 36.

Теперь все зависит от наблюдательности решающего задачу, от его способности по частным результатам угадать общий.

Полагаем, что в данном случае легко заметить, что

S1 = 12, S2 = 22, S3 = 32, S4 = 42.

На основе этого можно предположить, что вообще

Sn = n2.

Докажем, что эта гипотеза справедлива.

1°. При n = 1 сумма представляется одним слагаемым, равным 1. Выражение n2 при n = 1 также равно 1. Значит, при n = 1 гипотеза верна.

2°. Допустим, что гипотеза верна для n = k, т.е. Sk = k2. Докажем, что тогда гипотеза должны быть верна и для n = k +1, т.е.

Sk+1 = (k + 1)2.

Действительно,

Sk+1 = Sk +(2k + 1).

Но Sk = k2 и потому

Sk+1 = k2 + (2k + 1) = (k + 1)2,

Что и требовалось доказать

Ответ: Sn = n2.


Пример 3. Доказать, что сумма квадратов n первых чисел натурального ряда равно n(n+1)(2n+1)/6.

Решение. Пусть

S2 (n) = 12 + 22 +32 +…+n2.

1°. S2 (1) = 12 = 1(1+1)(2*1+1)/6.

2°. Предположим, что

S2 (n) = n(n+1)(2n+1)/6.

Тогда

S2 (n+1) = 12 + 22 +32 +…+n2+(n+1)2 = (n(n+1)(2n+2)/6)+(n+1)2

и окончательно

S2 (n+1) = (n+1)[(n+1)+1][2(n+1)+1]/6.


III. Тригонометрические и алгебраические задачи1

Пример 4. Доказать тождество

cos (a)cos (2a) cos(4a)…cos(2na) = sin(2n+1a)/2n+1sina.

Решение.

1°. При n = 0 тождество справедливо, так как

cos(a) = sin (2a)/2sin(a)

Пусть тождество справедливо при n = k, т.е.

cos (a)cos (2a) … cos(2ka) = sin(2k+1a)/2k+1sina.

Тогда оно справедливо и при n = k +1. Действительно,

cos(a)cos(2a) … cos(2ka)cos(2k+1a) = sin(2k+1a)cos(2k+1a)/2k+1sina = sin(2k+2a)/2k+2sina.


Пример 5. Доказать, что Ak = cos n q, если известно, что A1 = cosq; A2 = cos2q и для всякого натурального k > 2 имеет место соотношение:

Ak = 2 cosq Ak-1Ak-2.

Решение.

1°. Утверждение справедливо при n = 1 и n = 2.

2°. Пусть

Ak-2 = cos (k – 2) q,

Ak-1 = cos (k – 1) q.

Тогда

Ak = 2 cos q cos (k – 1) q - cos (k – 2) q = cos k q.


Пример 6. Доказать, что

sin x + sin 2x + … + sin nx = [sin(n+1)x/2][sin(nx/2)]/sin(x/2).

Решение.

1°. При n = 1 утверждение справедливо.

2°. Пусть

sin x + sin 2x + … sin kx = [sin(k+1)x/2][sin(kx/2)]/sin(x/2).

Тогда

sin x + sin 2x + … + sin kx + sin (k+1)x = [sin(k+1)x/2][sin(kx/2)]/sin(x/2) + sin (k+1) x =


= [sin(k+1)x/2][sin(kx/2)]/sin(x/2) + 2[sin((k+1)x/2)] [cos ((k+1)x/2)] =


= [sin(k+2)x/2][sin((k+1)x/2)]/sin(x/2),

ибо

2cos((k+1)x/2) sin (x/2) = sin ((k+2)[/2) – sin kx/2.


IV. Задачи на доказательство неравенств

Пример 7. Доказать, что при любом натуральном n > 1

1/(n+1) + 1/(n+2) + … + 1/2n < 13/24.

Решение. Обозначим левую часть неравенства через Sn.

1°. S2 = 7/12 = 14/24, следовательно, при n = 2 неравенство справедливо.

2°. Пусть Sk.> 13/24 при некотором k. Докажем, что тогда и Sk+1 > 13/24. Имеем,

Sk = 1/(k+1) + 1/(k+2) + … + 1/2k,

Sk+1 =1/(k+2) + 1/(k+3) + … + 1/2k + 1/(2k+1) + 1/(2k+2).

Сравнивая Sk и Sk+1, имеем

Sk+1 – Sk = 1/(2k+1) + 1/(2k+2) + 1/(k+1),

т.е.

Sk+1 – Sk = ½(k+1)(2k+1).

При любом натуральном k правая часть последнего неравенства положительна. Поэтому

Sk+1> Sk.

Но Sk > 13/24, значит, и Sk+1 > 13/24.

Пример 8. Доказать, что (1+a)n > 1 + ka, где a > -1, a ¹ 0, n – натуральное число, большее 1.

Решение. 1°. При n = 2 неравенство справедливо, так как +a2 > 0.

2°. Пусть неравенство справедливо при n = k, где k – некоторое натуральное число, т.е. (1+a)k > 1 + ka. (1)

Покажем, что тогда неравенство справедливо и при n = k + 1, т.е.

(1+a)k+1 > 1 + (k+1)a. (2)

Действительно, по условию, 1+a > 0, поэтому справедливо неравенство

(1+a)k+1 > (1 + ka)(1 + a), (3)

полученное из неравенства (1) умножением каждой его части на (1 + a).

Перепишем неравенство (3) так:

(1+a)k+1 > 1 + (k+1)a + ka2.

Отбросив в правой части последнего неравенства положительное слагаемое ka2, получим справедливое неравенство (2).

КОНТРОЛЬНЫЕ ЗАДАНИЯ

Предлагаемые ниже задачи являются контрольным заданием по математике для учащихся 8 и 9 классов. Для зачета восьмиклассникам рекомендуется решить не менее 5 задач, а девятиклассникам – не менее 7. Правила оформления, адрес и другая полезная информация – в конце журнала. Желаем Вам успехов.

  1. Найти un2, если известно, что u1 = 1 и что при всяком натуральном

k>1uk = uk-1 +3.

  1. Найти сумму Sn = 1 + 2 + 22 + 23 + … + 2n-1.

  2. Доказать, что сумма кубов n первых чисел натурального ряда равна

[n(n+1)/2]2.

  1. Доказать, что

1 + x +x2 + … + xn = (xn+1-1)/(x-1) (x¹1)

  1. Доказать, что

½ + cos x + cos 2x + … + cos nx = [sin(2n+1/2)x]/2sin x/2

  1. Доказать, что

cos x + 2cos 2x +…+ ncos nx = [(n+1)cos nx – ncos (n+1)x –1]/4sin2 x/2.

  1. Доказать, что

arctg3 + arctg5 + … + arctg(2n+1) = arctg2 + arctg3/2 +…+ arctg((n+1)/n) – n arctg1.

  1. Найти ошибку в доказательстве.

Утверждение. При любом натуральном n справедливо неравенство

2n > 2n + 1.

Доказательство. Пусть неравенство справедливо при n = k, где k – некоторое натуральное число, т.е.

2k > 2k + 1. (1)

Докажем, что тогда неравенство справедливо и при n = k+1, т.е.

2k > 2(k+1) + 1. (2)

Действительно, 2n не меньше чем 2 при любом натуральном k. Прибавим в левой части неравенства (1) 2k, а к правой 2. Получим справедливое неравенство.

2k + 2k > 2k + 1 + 2,

или 2k+1 > 2(k+1) + 1. Утверждение доказано.

  1. При каких натуральных n справедливо неравенство 2n > 2n + 1?

  2. Доказать, что при любом натуральном n > 1

1/Ö1 + 1/Ö2 + … + 1/Ön > Ön



1 Материал этого пункта, а так же задачи 5, 6 и 7 из контрольного задания, рассчитаны только на учащихся 9 класса.

Название документа ПРИНЦИП ДИРИХЛЕ (2).doc

Поделитесь материалом с коллегами:

Математика, 8-10 класс

Принцип Дирихле

(Материалы для подготовки к олимпиадам школьников по математике)

Принцип Дирихле утверждает следующее:

Утверждение 1. Если m>n, то при отнесении каждого из m предметов к одному из n классов хотя бы в один класс попадет не менее двух предметов.

В популярной литературе принцип Дирихле объясняется на примере «зайцев и клеток»: если в клетках больше nk зайцев, то хотя бы в одной клетке сидит больше n зайцев.

Подобные соображения используются в различных задачах для доказательства существования.

Самая популярная задача на прямое применение принципа Дирихле такова: на Земле живет 3 млрд. человек, у каждого на голове – не более миллиона волос. Нужно доказать, что обязательно найдутся два человека с одинаковым числом волос. Приняв в качестве «классов» возможное число волос от 0 до 1 000 000 (всего 1 000 001 класс), а в качестве «предметов» население Земли (всего 3 000 000 000 предметов) и применив принцип Дирихле, получим, что обязательно найдутся, по крайней мере, 2 000 людей, имеющих одинаковое число волос на голове.

Приведем еще несколько похожих на принцип Дирихле утверждений, используемых в геометрических и аналитических задачах.

Утверждение 2. Если сумма площадей нескольких фигур меньше S, то ими нельзя покрыть фигуру площади S.

Утверждение 3. Если на отрезке длины 1 расположено несколько отрезков с суммой длин L, то найдется точка, покрытая не более чем L этими отрезками.

Утверждение 4. Если среднее арифметическое нескольких чисел больше a, то хотя бы одно из этих чисел больше a.

Рассмотрим задачи, при решении которых применяется принцип Дирихле.

Задача 1. В розыгрыше кубка по футболу (в один круг) участвуют 30 команд. Доказать, что в любой момент найдутся две команды, сыгравшие одинаковое число игр.

Решение. Рассмотрим два случая.

  1. Хотя бы одна из 30 команд не сыграла еще ни одной игры.

  2. Каждая команда сыграла хотя бы одну игру.

Докажем утверждение для I-го случая.

Так как хотя бы одна из 30 команд не сыграла еще ни одной игры, то число игр у любой команды не более 28, то есть возможное число игр у каждой из команд может быть: 0, 1, 2, …, 28 (всего 29 чисел), а команд по условию 30. Тогда по принципу Дирихле, приняв в качестве «классов» числа проведенных игр (всего 29 «классов»), а в качестве «предметов» - команды (всего 30 «предметов»), получим, что хотя бы 2 команды будут соответствовать одному числу проведенных игр, а значит, хотя бы 2 команды сыграли одинаковое число игр.

Докажем утверждение для II-го случая.

Так как каждая из 30 команд сыграла хотя бы одну игру, то число проведенных игр может принимать значения: 1, 2, …, 29 (всего 29), я команд 30, тогда по принципу Дирихле найдутся хотя бы 2 команды, сыгравшие одинаковое число игр.


Задача 2. Доказать, что среди шести любых чисел найдутся два, разность которых делится на пять.

Решение.

  1. Из теории делимости известно, что разность чисел (a –b) делится на m тогда и только тогда, когда a и b при делении на m дают одинаковые остатки. Учитывая это утверждение, переформулируем задачу:

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

  3. Докажем это утверждение.

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

6>5, по принципу Дирихле получаем, что, приняв в качестве «классов» – остатки, в качестве «предметов» - числа, учитывая, что хотя бы два числа из шести имеют одинаковые остатки при делении на пять, а значит, их разность делится на пять.


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

Решение.

  1. Каждая из девяти прямых разбивает квадрат либо на два прямоугольника, либо на две трапеции.

  2. Площадь трапеции равна hello_html_4e5770fc.gif, где h – высота трапеции (в нашем случае сторона квадрата), C – длина средней линии трапеции (отрезок на средней линии квадрата).

  3. Тhello_html_m65da09ad.gifак как по условию площади получившихся трапеций или прямоугольников делятся как 2:3, то в том же отношении (п.2) прямая делит и среднюю линию квадрата.

  4. Таких точек, которые делят одну из средних линий квадрата в отношении 2:3 всего 4 (см. рис.), прямых по условию 9, и каждая из них должна пройти через одну из этих точек.

  5. И так «классов» – 4, «предметов» –9>2×4, тогда по принципу Дирихле, найдется три прямых проходящих через одну из этих четырех точек.


Задача 4. Доказать, что найдется число вида 200120012001…2001001…0, которое делится на 2002.

Решение.

  1. Рассмотрим 2002 числа 2001, 20012001, …, hello_html_m60a51f39.gif

  2. Рассмотрим остатки от деления каждого числа на 2002: ни одно из этих чисел не делится на 2002, так как это число четное, а числа п.1 нечетные, поэтому возможные остатки: 1, 2, …, 2001 (всего 2001).

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

  4. Разносить чисел, имеющих одинаковые остатки при делении на 2002, делится на 2002 и имеет вид 20012001…2001000…0. Утверждение доказано.


Теория делимости на множество целых чисел.

Определение 1. Пусть даны числа a, b ÎZ, причем b ¹ 0. Тогда числа q, r ÎZ; hello_html_2463c477.gif называются соответственно частным и остатком от деления числа a на число b, если выполняется равенство hello_html_m496a0b38.gif.

При этом, если r = 0, то говорят, что число a делится на число b (обозначают hello_html_7ae656f5.gif) или a кратно b, или b делится на a (обозначается b|a).

Замечание. В теории доказывается теорема (о делении с остатком) утверждающая, что для любых a, b ÎZ, b¹0 числа q и r из определения 1 всегда существуют, причем для пары чисел a, b пара q и r – единственная.

На основании этой теоремы можно утверждать:

Утверждение 1. Среди m последовательных целых чисел найдется ровно одно число, делящееся на m. Причем, если m – фиксированное целое число, m>0, то любое целое число a можно представить как

hello_html_457dfe10.gif

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


Утверждение 2. Два целых числа a и b при делении на hello_html_6848b9d4.gif дают одинаковые остатки в том и только в том случае, когда их разность (a-b) делится на m.

Перечислим простейшие свойства делимости на множество целых чисел:

  1. Для любого целого числа a, hello_html_m3b550d7a.gif

  2. Для любых целых чисел a, b, c, если hello_html_m4031eea3.gif, то hello_html_6c97dd1d.gif

  3. Для любых целых чисел a и b, если hello_html_b57fd33.gifи hello_html_1ed9837b.gif, то hello_html_m38353796.gif.

  4. Для любых целых чисел a, b, если hello_html_b57fd33.gifи hello_html_mc3f00b7.gif, то a=0

  5. Для любых целых чисел a, b, если hello_html_b57fd33.gif и hello_html_4047c655.gif, то hello_html_7221c596.gif

  6. Для любых целых чисел a, b, hello_html_b57fd33.gif тогда и только тогда, когда hello_html_4f2017e0.gif

  7. Если hello_html_4fd278c0.gif то hello_html_m6447684f.gif.

  8. Если hello_html_11a62593.gifи hello_html_me094b43.gif, то hello_html_1eecb077.gif

  9. Если один из сомножителей произведения делится на a, то и все произведение делится на a.


Определение 2. Натуральное число hello_html_m526f5e77.gif называется простым, если оно имеет ровно два делителя: единицу и само себя.


Определение 3. Натуральное числоhello_html_363287a0.gif называется составным, если оно имеет, по крайней мере, один делитель отличный от 1 и m.

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

  1. простые числа

  2. составные числа

  3. единица

Перечислим свойства простых и составных чисел.

  1. Число 2 – единственное простое четное число.

  2. Если hello_html_m2b80261.gif - простые числа, то hello_html_5a8bc662.gif (не делится)

  3. Если произведение нескольких целых чисел, делится на простое число p, то, по меньшей мере, один из сомножителей делится на p.

  4. Множество простых чисел бесконечно (теорема Евклида).

  5. Каждое натуральное число единственным образом представляется в виде произведения простых чисел (основная теорема арифметики).



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

Задача 1. Доказать, что число hello_html_m220ea231.gif оканчивается на ту же цифру, что число N.

Решение. (основано на свойствах делимости, теореме о делимости с остатком)

Заметим, что hello_html_m220ea231.gif и N будет заканчиваться на одну и ту же цифру в том и только том случае, когда hello_html_3bf31049.gif будут делится на 10, поэтому переформулируем задачу: доказать, что hello_html_8e50563.gif.

1. Разность hello_html_m36ea4879.gif представим в виде произведения сомножителей: hello_html_m67dd9162.gif

2. Число 10 тоже разложим на множители 10 = 2*5, причем числа 2 и 5 - взаимно простые. Поэтому, если мы докажем, что hello_html_m36ea4879.gif делится на 2 и на 5, тем самым мы докажем утверждение.

  1. Рассмотрим произведение hello_html_47668361.gif - произведение двух последовательных чисел, следовательно, одно из них – четное, то есть делится на два, а значит, (св.9), hello_html_5c16351.gif.

  2. Докажем, что один из сомножителей числа hello_html_m703e9716.gif делится на 5 согласно утверждению 1, число N может быть представлено как hello_html_7af18544.gifили hello_html_40a5d7e9.gif или hello_html_m9ee1553.gif или hello_html_m51677822.gif или hello_html_m11648606.gif.

Рассмотрим каждый из этих случаев отдельно:

Если hello_html_325c06c2.gif

Если hello_html_3b4f9be3.gif

Если hello_html_m59f11561.gif

hello_html_1871d2b1.gif

Если hello_html_m478f0da0.gif

hello_html_2c8d64b3.gif

Таким образом, мы получили, что каково бы ни было натуральное число N, hello_html_4add1c7c.gif

  1. Так как hello_html_m67ecb692.gif и hello_html_4add1c7c.gif, то hello_html_6874bea6.gif оканчиваются на одну и ту же цифру.

Замечание.

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

  2. При доказательстве делимости некоторого выражения на число часто используют утверждение 1, сводя рассмотрение бесконечного множества целых чисел к конечному множеству классов (в задаче 1 этих классов 5 (п.4))


Задача 2. Найти все простые числа p, которые можно записать в виде hello_html_517eff92.gif с натуральными m и n. Доказать, что других таких чисел нет.

Решение. (основано на свойствах простых и составных чисел).

  1. По определению p – простое, если оно имеет ровно два делителя 1 и само себя. Поэтому разложим hello_html_517eff92.gif на множители.

  2. hello_html_77b987c4.gif

  3. Итак hello_html_517eff92.gif - простое, если hello_html_6ba1ccef.gif или hello_html_2581205d.gif, но первое равенство не выполняется ни при каких натуральных m и n.

  4. Найдем такие m и n, что hello_html_m5f6514c.gif. В левой части равенства выделим полный квадрат hello_html_6126e01a.gif.

  5. Тогда hello_html_301b988.gif, но первая система не имеет решений в натуральных числах. Решим вторую систему: из второго уравнения имеем: n=1, тогда из первого: m=n=1.

  6. Получаем hello_html_m4d89f433.gif - простое число, и так как m=n=1 – единственная пара, удовлетворяющая второй системе (п.4), то это единственное простое число, представимое в виде hello_html_517eff92.gif.


Задача 3. Найти все простые числа, которые являются одновременно суммой двух простых чисел и разностью двух простых чисел.

Решение. (основано на свойствах простых чисел и свойствах делимости).

  1. Обозначим искомое число через p. Так как по условию p – разность и сумма двух простых чисел, то p>2, а, следовательно (свойство 1 простых чисел) p – нечетное.

  2. Так как p – сумма двух слагаемых и p – нечетное, то одно из слагаемых четно, а так как оно простое, то оно равно 2. Так как p – разность двух слагаемых и p – нечетно, то вычитаемое в представлении числа p в виде разности двух простых чисел равно 2. Таким образом, мы получаем hello_html_2be5c7fb.gif и hello_html_67ef9808.gif, где q и r – простые.

  3. Выразим q и r через p, hello_html_7b9da8b.gif. Тогда мы имеем три последовательных простых числа hello_html_m68073745.gif. Причем все эти простые числа – нечетные, но одно из трех последовательных нечетных чисел делится на 3, действительно: любое число (утверждение 1) может быть записано или как hello_html_m20fb22dc.gifили hello_html_66de09aa.gif или hello_html_m193afa28.gif. Если hello_html_m20fb22dc.gif, то следующее за ним нечетное число имеет вид hello_html_6a73daff.gif, следующие hello_html_m7a04b684.gif, из этих трех чисел hello_html_m3450c0aa.gif. Если hello_html_160de22b.gif, следующее нечетное hello_html_35fcc3.gif, а следующее hello_html_205c4b82.gif, и hello_html_830a8f2.gif. Если hello_html_m193afa28.gif, то hello_html_3343a00c.gif и hello_html_2ca94aa.gif. На основании этих рассуждений и того, что hello_html_m68073745.gif - простые, имеем: одно из этих чисел равно 3.

  4. Рассмотрим, какое из этих трех чисел равно 3. Если p=3, то p-2=3-2=1 –не простое число; если p-2=3, то p=3+2=5, p+2=7, если p+2=3, то p=1 – не простое число, следовательно, p-2=3, при этом p=5. Следовательно, только простое число p=5 есть сумма и разность двух простых чисел: p=5=7-2 p=5=3+2

Замечание. При решении этой задачи и многих других используется особая роль простого числа 2, как единственного четного числа.


Задача 4. Существуют ли целые числа x и y, удовлетворяющие уравнению

hello_html_m71fb3c4d.gif

Решение. (основано на свойствах делимости).

  1. Число 7 – простое нечетное число, являющееся разностью двух чисел, поэтому эти числа разной четности, но hello_html_77fe2f9a.gif - четное, тогда hello_html_20533a55.gif - нечетное.

  2. hello_html_20533a55.gif- нечетное, 5 – нечетное Þ hello_html_m5cfd6594.gif - нечетное Þ y - нечетное Þ hello_html_m48de5212.gif

  3. hello_html_662bcbeb.gif, тогда hello_html_m27ebc39c.gif, подставим это в уравнение.

  4. Получим hello_html_m31477e6f.gif.

  5. Так как hello_html_29c74dd1.gif - четные, и разность hello_html_7f61c10c.gifтоже четное, то hello_html_19460946.gif - четное число hello_html_3b52ca82.gif.

  6. Тогда получим уравнение hello_html_m7e55de95.gif

hello_html_m4cc1b35.gif

hello_html_185dc7e.gif- четное

hello_html_71d177e2.gif- четное, как произведение последовательных целых чисел, но тогда hello_html_70221cda.gif - четное hello_html_5ebb178f.gif ни при каких целых m и n hello_html_50cbad75.gif решений в целых числах не имеет.

Замечание. Теорию делимости можно применять и при решении уравнений в целых числах.


  1. Задачи для самостоятельного решения

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

  3. В школе 30 классов и 1 000 учащихся. Доказать, что есть класс, в котором не менее 34 учеников.

  4. Доказать, что для каждого натурального числа n найдется натуральное число, все цифры которого пятерки и нули, которое делится на n.

  5. Доказать, что если hello_html_m2a895898.gif и hello_html_m4a48522.gif, то hello_html_m4eb619d8.gif и hello_html_m4146aeed.gif.

  6. Найти все такие простые числа p, что hello_html_m7339f516.gifтоже простое.

Найти все различные простые числа hello_html_7f569c1c.gif такие, что их сума – простое число, а числа hello_html_19948f49.gif и hello_html_1a3c623a.gif - квадраты натуральных чисел.

Название документа ПРИНЦИП ДИРИХЛЕ.doc

Поделитесь материалом с коллегами:

Принцип дирихле

1. Самая популярная формулировка принципа Дирихле такова: «Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят по крайней мере два зайца». На первый взгляд даже непонятно, почему это совершенно очевидное замечание является весьма эффективным методом решения задач. Дело в том, что в каждой конкретной задаче нелегко бывает понять, что же здесь «зайцы» и «клетки» и почему зайцев больше, чем клеток. Выбор зайцев и клеток часто неочевиден; далеко не всегда по виду задачи можно определить, что следует воспользоваться принципом Дирихле. А главное, этот метод дает неконструктивное доказательство (мы, естественно, не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть), а попытка дать конструктивное доказательство, т. е. доказательство путем явного построения или указания требуемого объекта, может привести к гораздо большим трудностям.

2. Некоторые задачи решаются также методами, в какой-то мере аналогичными принципу Дирихле. Сформулируем соответствующие утверждения (все они легко доказываются методом от противного).

а) Если на отрезке длиной 1 расположено несколько отрезков. сумма длин которых больше 1, то по крайней мере два из них имеют общую точку.

б) Если на окружности радиуса 1 расположено несколько дуг, сумма длин которых больше 2, то по крайней мере две из них имеют общую точку.

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

Методические указания по теме «П Р И Н Ц И П Д И Р И Х Л Е»

 

  При решении многих задач используются сходные между собой приемы рассуждений, получившие название “ принципа Дирихле “. Задачи на принцип Дирихле воспитывают у учащихся умение устанавливать соответствие между элементами двух множеств. На решение задач по принципу Дирихле нужно посвятить несколько занятий, которые могут быть разделены занятиями на другие темы. Принцип Дирихле можно давать прямо на первых уроках, так как он достаточно рельефно характеризует специфику олимпиадных задач. Кроме того, многие задачи используют идеи принципа Дирихле в решении всей задачи или какой-то её части.

 

 

П Р И Н Ц И П Д И Р И Х Л Е.

 

  В самой простой и несерьезной форме принцип Дирихле выглядит так: “нельзя посадить семерых зайцев в три клетки так, чтобы в каждой клетке находилось не больше двух зайцев “. Другая формулировка “ принципа Дирихле“: если n + 1 предмет поместить в n мест, то обязательно хотя бы в одном месте окажутся хотя бы два предмета. Заметим, что в роли предметов могут выступать и математические объекты - числа, места в таблице, отрезки и т.д.

 

Задача 1. В корзине лежат 30 грибов - рыжиков и груздей. Известно, что среди любых 12 грибов имеется хотя бы один рыжик, а среди любых 20 грибов - хотя бы один груздь. Сколько рыжиков и сколько груздей в корзине.

Решение:19 рыжиков и 11 груздей. Если бы в корзине нашлись 12 груздей, то ни один из них не был бы рыжиком, следовательно, количество груздей не превосходит 11. Если бы груздей было меньше 11, то их было бы не больше 10. В этом случае можно было бы найти 20 не груздей, следовательно, груздей - 11. Рыжиков - 19.

Задача 2. В мешке лежат шарики двух разных цветов: черного и белого. Какое наименьшее число шариков нужно вынуть из мешка вслепую так, чтобы среди них заведомо оказались два шарика одного цвета?

Решение: Достанем из мешка 3 шарика. Если бы среди шариков было не более одного шарика каждого из двух цветов, то всего было бы не более двух шариков - это очевидно, и противоречит тому, что мы достали 3 шарика. С другой стороны, понятно, что двух шариков может и не хватить. Ясно, что “ зайцами ” здесь являются шарики, а “ клетками” - цвета: черный и белый.


Задача 3. В магазин привезли 25 ящиков с тремя сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков одного сорта.

Решение: В решении этой задачи нам поможет обобщенный принцип Дирихле: “ Если в n клетках сидят не менее kn + 1 зайцев, то в какой-то из клеток сидит, по крайней мере, k + 1 заяц. 25 ящиков – “зайцев” - рассадим по 3 “клеткам” - cортам. Так как 25 = 3 * 8 + 1, то, применив обобщенный принцип Дирихле для n = 3, k = 8, получим, что в какой-то “ клетке” – сорте не менее 9 ящиков.


Задача 4. В квадрате со стороной 1 м бросили 51 точку. Докажите, что какие-то 3 точки из них можно накрыть квадратом со стороной 20 см.

Решение: Разобьем квадрат на 25 квадратов со стороной 20 см. По обобщенному принципу Дирихле в какой-то из них попадет по крайней мере 3 точки из 51 брошенной.

Заметим, что в основе принципа лежит идея сложения неравенств. Одно замечательное свойство из неё гласит: ” Если сумма n чисел равна S, то среди них есть как число не большее S:n и число не меньшее S:n ”.


Задача 5. В бригаде 7 человек и их суммарный возраст 332 года. Докажите, что из них можно выбрать трех человек, сумма возрастов которых не меньше 142.

Решение: Рассмотрим всевозможные тройки рабочих бригад. Сумма их суммарных возрастов, как легко подсчитать, равна 15*332, а таких троек 35. Значит, есть тройка, суммарный возраст в которой не меньше, чем (15*332):35, что больше 142.


Задача 6. В непрозрачном мешке лежат 5 белых и 2 черных шара. а) Какое наименьшее число шаров надо вытащить из мешка, чтобы среди них обязательно оказался хотя бы один белый шар?

Решение: Худшим”, здесь является случай, когда мы будем вытаскивать все время черные шары. В этом случае, даже вытащив подряд 2 шара, мы не вытащим белого шара. Но если мы вы тащим 3 шара, то тогда уж точно из трех шаров по крайней мере один шар будет белым.

б) Сколько шаров надо вытащить, чтобы среди них обязательно оказался хотя бы один белый и хотя бы один черный шар?

Решение: “ Худшим ” здесь является случай, когда мы сначала будем вытаскивать одни белые шары и только потом попадается один черный шар. Поэтому потребуется вытащить 5 + 1 = 6 шаров.

в) Какое наименьшее число шаров надо вытащить, чтобы среди них наверняка оказались 3 белых и 1 черный шар?

Решение: В “ худшем “ случае мы сначала вытащим все белые шары, и затем лишь пойдут черные. Тогда придется вытащить 5 + 1 =6 шаров.

г) Сколько шаров надо вытащить, чтобы среди них оказались два шара одного цвета?

Решение: “ Худший “ случай - когда сначала идут шары разных цветов. Это возможно, если мы вытащим 2 шара. А если мы вытащим третий, то уже будем иметь два шара одного цвета.


Задача 7. Cколько надо взять двузначных чисел, чтобы по крайней мере одно из них делилось: а) на 2, б) на 7?

Решение: а) В “ худшем “ случае, вытаскивая из мешка числа от 10 до 99, мы сначала будем иметь только нечетные числа - их 45, и поэтому 46-е число обязательно будет четным.

б) Среди 90 чисел от 10 до 99 имеется всего 13 чисел, делящихся на 7, т.е. в “худшем ” случае мы сначала вытащим 90 - 13 = 77 чисел, не делящихся на 7, но 78-е число уже точно будет делиться на 7.


Задача 8. Дано 12 целых чисел. Докажите, что из них можно выбрать два, разность которых делится на 11.

Решение: Решение этой задачи можно начать с вопроса о количестве различных остатков от деления числа на 11. Получив ответ, что их ровно 11, можно сделать вывод о том, что среди 12 чисел найдутся, по крайней мере, два, имеющие одинаковые остатки. Разность этих чисел и будет делится на 11. После этого надо найти “ зайцев” (12 чисел) и “ клетки ” (остатки от деления на 11).


Задача 9. Докажите, что в любой копании из пяти человек двое имеют одинаковое число знакомых.

Решение: Имеются пять вариантов числа знакомых: от 0 до 4.Остается заметить, что если у кого-то четверо знакомых, то ни у кого не может быть ноль знакомых. ("Клетки", соответствующие 0 и 4, взаимно исключают друг друга.) Поэтому можно говорить о четырех “ клетках “- вариантах числа знакомых. Поскольку в компании пять человек – “зайцев ”, по принципу Дирихле обязательно найдутся хотя бы два человека, имеющие одинаковое число знакомых.

Задача 10. 10 школьников на олимпиаде решили 35 задач, причем известно, что среди них есть решившие ровно одну задачу, решившие ровно две задачи и решившие ровно три задачи. Докажите, что среди них есть школьник, решивший не менее пяти задач.

Решение: Из условия задачи можно заключить, что найдутся семь школьников, решивших 35 - (1 + 2 + 3) = 29 задач. Так как 29 = 7 * 4 + 1, то найдется школьник, решивший не менее 5 задач.

Задача 11. В школе 20 классов. В ближайшем доме живут 23 ученика этой школы. Можно ли утверждать, что среди них обязательно найдутся хотя бы два одноклассника?

Решение: Можно, так как классов (20) меньше, чем учеников (23).


  Задача 12. В школе учится 370 человек. Докажете, что среди всех учащихся найдутся два человека, празднующие свой день рождения в один и тот же день.

Решение: В году 365 дней, следовательно, у 5 учеников дни рождения могут совпасть.


Задача 13. Коля подсчитал, что за завтрак, обед и ужин он съел 10 конфет. Докажите, что хотя бы один раз он съел не меньше 4 конфет.

Решение: Доказываемое утверждение следует из равенства: 10 = 3*3 + 1


Задача 14. В классе 37 человек. Докажите, что среди них найдутся 4 человека с одинаковым числом дня рождения.

Решение: В любом месяце дней не более 31, значит, для 37 учеников есть одинаковые числа, месяц роли не играет.


Задача 15. В ящике комода, который стоит в темной комнате, лежат 10 коричневых и 10 красных носков одного размера. Сколько носков нужно достать, чтобы среди них была пара одинакового цвета?

Решение: 3 носка.


Задача 16. Имеются три ключа от трех чемоданов с разными замками. Достаточно ли трех проб, чтобы открыть чемодан?

Решение: Достаточно.


Задача 17. Какое наибольшее число полей на доске 8 Х 8 можно закрасить в черный цвет так, чтобы в любом уголке вида из трех полей было бы по крайней мере одно незакрашенное?

Решение: 32 клетки.

Задача 18. Цифры 1, 2, 3, 4, 5, 6, 7, 8, 9 разбили на 3 группы. Докажите, что произведение чисел в одной из групп не меньше 72.

Решение: Если бы каждое из полученных произведений было меньше 72, то произведение всех чисел от 1 до 9 не превосходило бы 713= 357911. Но 1*2*3*4*5*6*7*8*9= = 362880 > 357911.


Задача 19. Сто человек сидят за круглым столом, причем более половины из них - мужчины. Докажите, что какие-то двое мужчин сидят друг напротив друга.

Решение: В противном случае женщин было бы не меньше, чем мужчин, что противоречит условию задачи.

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

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


Задача 21. Иван-царевич добыл ключи от нескольких комнат в подземелье, но не знал, какой ключ от какой комнаты. Сколько комнат в подземелье, если, как подсчитал Иван-царевич, в худшем случае, ему достаточно 20 проб, чтобы выяснить, какой ключ от какой комнаты.

Решение: Первым ключом Иван-Царевич пробует открыть все двери (или меньше, если ключ к какой-то двери подойдет раньше), вторым – все, кроме одной, и т. д. предпоследним – две, последним – ни одной (дверь осталась одна). Так как 2 + 3 + 4 + 5 + 6 = 20, в подземелье 6 дверей.

 

Задача 22. В погребе стоит 20 одинаковых банок с вареньем. В 8-ми банках клубничное, в 7-ми малиновое, в 5-ти вишневое. Каково наибольшее число банок, которые можно в темноте вынести из погреба с уверенностью, что там осталось еще хотя бы 4 банки одного сорта варенья и 3 банки другого.

Решение: Можно вынести 7 банок 


Название документа План подготовки к районной олимпиаде.doc

Поделитесь материалом с коллегами:

План подготовки к районной олимпиаде по математике учителя – Янченко С. А. .

В 2012-2013 учебном году планирую к районной олимпиаде готовить ученика 9 «А» класса Мирзоян Тиграна. В ходе подготовки необходимо разобрать следующие способы и приемы решения математических задач.

Способы решения олимпиадных задач:
- Метод мат. индукции;
- Метод инвариантов;
- Изобретательность, конструирование решения, промежуточное вспомогательное конструирование;
- Исходить из смысла, условия задачи, ее операций;
- Привлечение других областей математики;
- Свойства объектов ("Заметим, что..."), порассуждать о свойствах, взаимосвязь с другими свойствами;
- задачи на целые числа - делимость;
- принцип Дирихле;
- установление промежуточных фактов, гипотез и их проверка, исходя из цели;
- многошаговое, поэтапное решение, поиск в глубину;
- перебор;
- решать от конца, от того, что требуется;
- доказательство от противного;
- неожиданные гипотезы и попытка их доказательства, их проверка;
- рассмотрение альтернативных вариантов, поиск в ширину.

Во всех перечисленных способах можно выделить отдельные темы:

- Метод мат. индукции;
- Метод инвариантов;
- Задачи на целые числа - делимость;
- Принцип Дирихле;
-Теория Графов;

-Геометрические задачи;

-Текстовые задачи;

Изучить данные темы необходимо в указанные сроки:

сентябрь

- Метод мат. индукции;
- Метод инвариантов;

октябрь

- Задачи на целые числа - делимость;
- Принцип Дирихле;

ноябрь

-Теория Графов;

-Геометрические задачи;


декабрь

-Текстовые задачи;

- И прочие задачи из олимпиад прошлых лет





Учитель математики: ____________________________ Янченко С. А.

Название документа Прогрессии.doc

Поделитесь материалом с коллегами:

Математика. 9, 10 класс

Арифметическая и геометрическая прогрессии

Напомним основные понятия и формулы.

Определение. Арифметической прогрессией называется последовательность чисел hello_html_m5a4a7ddb.gif, hello_html_m4b9f6b6a.gif,каждый член которой, начиная со второго, равен предыдущему члену, сложенному с одним и тем же числом d, т.е.

hello_html_66f2d0c4.gif. (1)

Число d называется разностью арифметической прогрессии, число hello_html_m53e757c9.gif- первым членом, а hello_html_m3f75a86c.gif- n-ым членом ( или общим членом ).

При любом nhello_html_m3229d19f.gif2 имеем:

hello_html_45092d12.gif, hello_html_m14745a5e.gif, (2)


поэтому для nhello_html_m3229d19f.gif2 имеем:

hello_html_69e04def.gif(3)

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

Для арифметической прогрессии hello_html_mff0b0d4.gif с первым членом hello_html_m53e757c9.gif и разностью hello_html_ma8a7349.gif ее n-ый член можно найти по формуле

hello_html_6fed0b10.gif, nhello_html_m1b762db3.gifN. (4)

Также имеет место формула

hello_html_m35e2de08.gif, 1hello_html_1a4a3bea.gif, k,nhello_html_1084e2c2.gif (5)

Т.е., любой член арифметической прогрессии , начиная со второго, равен полусумме равноотстоящих от него членов прогрессии.

Кроме того, справедливо равенство:

hello_html_24fa9c4a.gif, если m+n = k+l. (6)

Сумма первых n членов арифметической прогрессии вычисляется по формуле:

hello_html_m6b5b5266.gifhello_html_m53d4ecad.gif(7)

Определение. Геометрической прогрессией называется последовательность чисел hello_html_m4d97b36c.gif, nhello_html_m1b762db3.gifN, каждый член которой, начиная со второго, равен предыдущему члену, умноженному на одно и то же постоянное для этой последовательности число qhello_html_m1545408.gif0, т. е., hello_html_3418907e.gif. (8)

Число q называется знаменателем геометрической прогрессии, число hello_html_m6de87811.gif- ее первым членом, а hello_html_3f83f1b1.gif- n-ым ( или общим) членом.

Для геометрической прогрессии имеем:

hello_html_me05c2ae.gif, поэтому

hello_html_6c15aeae.gif(9)

Кроме того, для любых натуральных k,l,m,n имеют место формулы:

hello_html_29896b71.gif, если m+n = k+l. (10)

hello_html_m13938c1.gif, если 1hello_html_1a4a3bea.gif (11)

т.е., квадрат любого члена геометрической прогрессии, начиная со второго, равен произведению равноотстоящих от него членов прогрессии.

Сумма n членов геометрической прогрессии вычисляется по формуле:

hello_html_416e9b4b.gif(12)

Определение. Геометрическая прогрессия называется бесконечно убывающей, если ее знаменатель q подчиняется условию hello_html_2c1e1a43.gif.

В этом случае сумма бесконечно убывающей геометрической прогрессии вычисляется по формуле: hello_html_7b89f40e.gif.

Пример 1. В арифметической прогрессии найти hello_html_d27d5bd.gif, если hello_html_m7a343bc8.gif, а hello_html_773ebc54.gif.

Решение: Т.к. hello_html_m74bef3de.gif, hello_html_m4374ceea.gifи hello_html_4d5740ed.gif, то запишем данные задачи в виде системы уравнений:

hello_html_m5cd2104f.gifhello_html_m72e45793.gif

hello_html_m703f72b2.gif

Решая эту систему, найдем hello_html_4c0e3350.gif,hello_html_35bbd8d1.gif. Поэтому

hello_html_mfe9ded6.gif.

Ответ: hello_html_773ebc54.gif.

Пример 2. Могут ли числа 10,25 и 40 в указанном порядке быть членами арифметической прогрессии?

Решение. Т.к. в условии не сказано, что эти числа – последовательные члены прогрессии, то будем считиать, что hello_html_54471e2c.gif, где 1<m<n. Для этой пргрессии имеем систему уравнений:

hello_html_3a0ed85d.gifhello_html_m3a74aecd.gif

hello_html_70f67831.gif,

где hello_html_ma8a7349.gif- разность пргрессии. Исключая из этой системы hello_html_ma8a7349.gif, получим следующее соотношение, связывающее натуратьные числа m и n:

hello_html_7a6b693b.gif.

Полагая, например, m=2, получим, что n=3, d=15 , т.е., числа m и n–натуральные и могут являться номерами членов арифметической прогресии.

Ответ. Числа 10, 25 и 40 могут быть членами арифметической прогрессии.

Пример 3. Найти количество всех трехзначных натуральных чисел, делящихся на 7 без остатка.

Решение. Наименьшим трехзначным числом, делящимся без остатка на 7, является число 105, наибольшим – число 994. Все трехзначные числа, делящиеся без остатка на 7, образуют арифметическую прогрессию с hello_html_446ce198.gif, d = 7, hello_html_6fc65236.gif . Найдем n по формуле общего члена: 994= 105 + 7( n-1) , отсюда n = 128.

Ответ: Всего имеется 128 трехзначных натуральных чисел, делящихся без остатка на 7.

Пример 4. Сумма первых трех членов геометрической прогрессии равна 91. Если к этим членам прибавить, соответственно, 25, 27 и 1, то получатся три числа, образующих арифметическую прогрессию. Найти седьмой член данной геометрической прогрессии.

Решение: По условию имеем три последовательных члена геометрической прогрессии: hello_html_2c6befbc.gifhello_html_m28f23099.gif, hello_html_276a0c1d.gif. Составим первые три члена арифметической прогрессии: hello_html_m7d404e9d.gif,hello_html_4841bfe1.gif, hello_html_me3b170e.gif. Составим систему уравнений:

hello_html_1e8e8555.gif

hello_html_6c83d6f1.gifhello_html_2d45bb20.gifhello_html_m26ace2cf.gif

hello_html_m22f58c1.gifили, hello_html_m277dca3.gif,


hello_html_2e0d9f5a.gifhello_html_m54b6f88.gif

hello_html_1568d24.gif. Разделим одно уравнение системы на другое, затем перемножим крайние с средние члены пропорции, приведем подобные члены и получим следующее уравнение :

hello_html_m4151d80c.gif

Решим это уравнение и получим, что hello_html_71ab2c62.gif. Подставим эти значения в систему уравнений и найдем hello_html_m4b54749.gifили hello_html_57fafe42.gif.

Найдем hello_html_m52c25766.gifили hello_html_6733cabd.gif.

Ответ. hello_html_2d828146.gifили hello_html_m6656d913.gif.

Контрольные задания


Представленные ниже задачи являются контрольным заданием для учащихся 10 классов. Решения необходимо оформить в отдельной тетради и выслать по адресу, указанному во вступительной статье.

Для зачета нужно набрать не менее 30 баллов (каждая правильно решенная задача оценивается в 5 баллов).

М10.1.1. Найти первые шесть членов арифметической прогрессии, если hello_html_2b3c6a7d.gifи hello_html_m40c19a69.gif.

М10.1.2.Сумма второго, третьего и четвертого членов арифметической прогрессии равна 1,5 , а их произведение равно –4,5. Найти первый член и разность прогрессии.

М10.1.3. Найти hello_html_2d844312.gif, если hello_html_2c521370.gif.

М10.1.4. Могут ли числа 2,21 и 59 быть членами арифметической прогрессии?

М10.1.5. Вычислить сумму всех трехзначных чисел, кратных 3.

М10.1.6.Дан треугольник, длины сторон которого образуют арифметическую прогрессию. Найти длину средней стороны, если периметр треугольника равен 12.

М10.1.7. Найти пять первых членов геометрической прогрессии, если ее третий член равен 4, а четвертый равен 8.

М10.1.8.Между числами 3 и 19683 вставить семь чисел так, чтобы все девять чисел образовали геометрическую прогрессию.

М10.1.9.Могут ли длины сторон прямоугольного треугольника являться последовательными членами геометрической прогрессии?

М10.1.10. Доказать формулы (5), (6), (10), (11).

М10.1.11. Три числа образовывают геометрическую прогрессию. Если второе число увеличить на 2, то прогрессия станет арифметической. Если после этого увеличить последнее число на 9, то прогрессия станет снова геометрической. Найти эти числа.

М10.1.12. Найти hello_html_199fee69.gif, если числа hello_html_621535d1.gif,hello_html_72c4e95.gif и hello_html_m56912c15.gifявляются последовательными членами геометрической прогрессии.


Название документа Решение текстовых задач.doc

Поделитесь материалом с коллегами:

Математика, 9 класс

Решение текстовых задач

Задачи на составление уравнений, или текстовые алгебраические задачи, можно условно классифицировать по типам:

  • задачи на числовые зависимости;

  • задачи, связанные с понятием «процента»;

  • задачи на прогрессии;

  • задачи на движение;

  • задачи на совместную работу;

  • задачи на смеси и сплавы.

Стандартная схема решения текстовой задачи состоит из нескольких этапов:

  1. Обозначение буквами x, y, z, ... неизвестных величин, о которых идет речь в задаче.

  2. Составление с помощью введенных переменных и известных из условия задачи величин уравнения или системы уравнений (в некоторых случаях – систем неравенств).

  3. Решение полученного уравнения или системы уравнений.

  4. Отбор решений, подходящих по смыслу задачи.

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

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

Задачи на движение

Уравнения, которые составляются на основании условий задач на движение, обычно содержат такие величины, как расстояние, скорости движущихся объектов, время, а также скорость течения воды (при движении по реке). При решении этих задач принимают следующие допущения:

  1. Если нет специальных оговорок, то движение считается равномерным.

  2. Повороты движущихся тел, переходы на новый режим движения считаются происходящими мгновенно.

  3. Если тело с собственной скоростью х движется по реке, скорость течения которой равна у, то скорость движения тела по течению считается равной (х+у), а против течения – (х-у).

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

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

Пhello_html_735bc1fa.gifусть расстояние между точками А и В равно S. Два тела начинают движение одновременно, но имеют разные скорости v1 и v2. Пусть С – точка встречи, а t – время движения тел до встречи. В случае движения навстречу друг другу имеем АС=v1t, BC=v2t. Сложим эти два равенства:

АС+СВ=v1t+v2t=(v1+v2)t Þ AB=S=(v1+v2)t Þ hello_html_6ecdc3df.gif.

Если одно тело догоняет другое, то теперь получаем АС=v1t, BC=v2t. Вычтем эти равенства:



Аhello_html_625c7ffb.gifСВС=(v1–v2)t.

Так как АСВС=AB=S, то время, через которое первое тело догонит второе, определяется равенством

hello_html_295dc6ac.gif.

Задача 1. Пароход прошел 4 км против течения реки, а затем прошел еще 33 км по течению, затратив на весь путь один час. Найдите собственную скорость парохода, если скорость течения реки равна 6,5 км/ч.

Решение:

Пусть х км/ч – собственная скорость парохода.

Тогда (х+6,5) км/ч – скорость парохода по течению.

(х–6,5) км/ч – скорость парохода против течения.

Так как против течения пароход прошел 4 км со скоростью (х–6,5) км/ч, то

hello_html_57f95fe3.gif ч. – время движения парохода против течения.

Так как по течению пароход прошел 33 км со скоростью (х+6,5) км/ч, то

hello_html_310dabc1.gif ч. – время движения парохода по течению.

По условию hello_html_2407f082.gif

решим полученное уравнение

hello_html_m2d12db74.gif

hello_html_5bcc5005.gif

Откуда получаем квадратное уравнение

х237х+146,25=0 Þ х1=4,5 км/ч и х2=32,5 км/ч.

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

Через х мы обозначили собственную скорость парохода, при этом скорость течения реки 6,5 км/ч, поэтому х1=4,5 км/ч не подходит по смыслу задачи (при такой скорости пароход не выплыл бы против течения).

Поэтому, собственная скорость парохода равна 32,5 км/ч.

Ответ: v=32,5 км/ч.



Задача 2. Расстояние между городами А и В равно 60 км. Два поезда выходят одновременно: один из А в В, другой из В в А. Пройдя 20 км, поезд, идущий из А в В, останавливается на полчаса, затем, пройдя 4 минуты, встречает поезд, идущий из В. Оба поезда прибывают к месту назначения одновременно. Найдите скорости поездов.

Решение:

Оhello_html_m52cf56fb.gif

4 мин.

тобразим все условия задачи на рисунке.

Заметим, что если время в условии задачи выражено как в часах, так и в минутах, то минуты надо перевести в часы. В нашем случае 4 мин=4/10 часа=1/15 часа.

Так как в задаче надо определить две величины, введем две переменные и составим два уравнения.

Пусть х км/ч – скорость поезда, вышедшего из пункта А;

у км/ч – скорость поезда, вышедшего из пункта В.

Так как в задаче известно расстояние, выразим время через скорость и расстояние.

hello_html_d23e648.gifвремя, за которое поезд из А прошел 20 км.

hello_html_60c089ce.gifвремя, затраченное поездом из А до встречи в пункте D.

hello_html_51889f00.gifрасстояние, которое прошел поезд из А за 4 минуты после остановки.

Тогда поезд из А до встречи в пункте D прошел hello_html_6687e96d.gif км.

hello_html_105a20e6.gifкм – расстояние, пройденное поездом из В до встречи.

hello_html_m6b4251ec.gifвремя, пройденное поездом из В до встречи в пункте D.

Так как по условию в пункте D поезда встретились, они затратили на путь до встречи одинаковое время, поэтому получаем первое уравнение

hello_html_m71db16d1.gif.

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

Так как hello_html_3db31cd6.gif, то hello_html_153ac1c8.gif – время движения поезда из В после встречи.

Так как hello_html_17a46089.gif, то hello_html_3c3b777e.gif – время движения поезда из А после встречи.

По условию hello_html_m283ea55b.gif.

Таким образом, мы составили систему двух уравнений с двумя переменными.

hello_html_m2e75c2b7.gif

Решим систему, для чего из первого уравнения выразим у и подставим это выражение вместо у во второе уравнение.

hello_html_m44b12831.gif;

hello_html_1f7dacb8.gif;

hello_html_m4a7f6a6e.gif.

Решим полученное уравнение

hello_html_m74484d92.gif;

hello_html_52f07f0c.gif;

hello_html_m7a7e5009.gif;

х1=60; х2=–600.

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

hello_html_m5946b596.gif.

Ответ: vA=60 км/ч, vB=40 км/ч.

Задачи на совместную работу

Содержание задач этого типа сводится обычно к следующему: некоторую работу, объем которой не указывается и не является искомым, выполняют несколько человек или механизмов, работающих равномерно, то есть с постоянной для каждого из них производительностью. В таких задачах объем всей работы, которая должна быть выполнена, принимается за 1; время t, требующееся для выполнения всей работы, и р ­– производительность труда, то есть объем работы, сделанной за единицу времени, связаны соотношением

hello_html_m2abecb93.gif.

Рассмотрим стандартную схему решения задач этого типа.

Пусть х – время выполнения некоторой работы первым рабочим,

у – время выполнения этой же работы вторым рабочим.

Тогда hello_html_m559226f6.gif – производительность труда первого рабочего,

hello_html_m1bf5470a.gif – производительность труда второго рабочего.

hello_html_m7dff0a34.gif – совместная производительность труда.

hello_html_20d11b81.gif – время, за которое они выполнят задание, работая вместе.

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

Решение:

Пусть х – время работы первого по выполнению всей работы.

у – время работы второго рабочего.

По условию х=у–1, и первое уравнение составлено.

Пусть объем всей работы равен 1.

Тогда hello_html_m559226f6.gif – производительность труда первого рабочего,

hello_html_m1bf5470a.gif – производительность труда второго рабочего.

Так как они работали 45 мин.=3/4 часа совместно, то

hello_html_m4c8e4d91.gif – объем работы, выполненной рабочими за 45 минут.

Так как второй рабочий работал один 2 часа 15 минут==9/4 часа, то

hello_html_6c13303b.gif – объем работы, выполненной вторым рабочим за 2 часа 15 минут.

По условию hello_html_29c03a86.gif.

Таким образом, мы получили систему двух уравнений

hello_html_m3af40aa7.gif

Решим ее, для этого выражение для х из первого уравнения подставим во второе

hello_html_m77b9cca1.gifÞ hello_html_m2ce87fcc.gifÞ2–19у+12=0

hello_html_65b97f4.gifч. и у2=4 ч.

Из двух значений для у выберем то, которое подходит по смыслу задачи у1=45 мин., но 45 мин. рабочие работали вместе, а потом второй рабочий работал еще отдельно, поэтому hello_html_65b97f4.gif не подходит по смыслу задачи. Для полученного у2=4 ч. найдем из первого уравнения первоначальной системы значение х

х=41 Þ х=3 ч.

Ответ: первый рабочий выполнит работу за 3 часа, второй – за 4 часа.

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

Задача 2. Две бригады рабочих начали работу в 8 часов. Сделав вместе 72 детали, они стали работать раздельно. В 15 часов выяснилось, что за время раздельной работы первая бригада сделала на 8 деталей больше, чем вторая. На другой день первая бригада делала за 1 час на одну деталь больше, а вторая бригада за 1 час на одну деталь меньше. Работу бригады начали вместе в 8 часов и, сделав 72 детали, снова стали работать раздельно. Теперь за время раздельной работы первая бригада сделала на 8 деталей больше, чем вторая, уже к 13 часам. Сколько деталей в час делала каждая бригада?

Решение:

Пусть х деталей в час изготовляет первая бригада (производительность первой бригады).

у – производительность второй бригады.

х+у – совместная производительность бригад.

Так как вместе они сделали 72 детали, то

hello_html_m56bd0f1c.gif – время совместной работы бригад.

Так как бригады работали с 8 до 15 часов, всего 7 часов, то

hello_html_m5a69275.gif – время работы бригад раздельно, тогда

hello_html_26470874.gif – число деталей, которое изготовила первая бригада, работая отдельно

hello_html_m1c3e39f5.gif – число деталей, которое изготовила вторая бригада, работая отдельно

По условию hello_html_7d947010.gif или hello_html_7e34d570.gif

Составим второе уравнение. По условию:

х+1 – производительность труда первой бригады на другой день.

у–1 – производительность труда второй бригады на другой день.

х+1+у–1=х+у – совместная производительность (такая же, как и в первый день).

Так как бригады работали с 8 до 13 часов – всего 5 часов, то

hello_html_m296d6164.gif – число деталей, которые изготовила первая бригада, работая отдельно, во второй день.

hello_html_m5ecb4be2.gif – число деталей, которые изготовила вторая бригада, работая отдельно, во второй день.

По условию hello_html_m2536827d.gif или hello_html_68eb8a25.gif.

Таким образом, мы составили систему двух уравнений:

hello_html_m18291f8a.gif

Решим эту систему методом замены переменных:

Пусть hello_html_m52de4af9.gif...................(V)

Тогда имеем:

hello_html_95cc64d.gifÞ hello_html_38dde826.gif

Выразим из первого уравнения hello_html_md545e9e.gif и подставим во второе уравнение

hello_html_m42ddb3c.gifÞ v2+2v–8=0 Þ v1=2, v2=–4.

Значение v2=–4 не подходит по смыслу задачи (из условия ясно, что производительность первой бригады выше, чем второй, а значит х–у=v>0). Найдем значение u, соответствующее v2=2, подставив значение v2 в выражение для u:

hello_html_m1d55321f.gif.

Так как нам нужно найти значения х и у, подставим полученные значения для u и v в (V)

hello_html_4b9ec8bf.gifÞ hello_html_m7f47fbe3.gifÞ hello_html_1ca97abe.gifÞ hello_html_m5d8b1eb7.gifÞ hello_html_bdc8898.gif

Ответ: 13 деталей в час изготавливала первая бригада; 11 деталей в час изготавливала вторая бригада.

Задачи на смеси и сплавы

В задачах этого типа основным является понятие «концентрация». Что же это такое?

Рассмотрим, например, раствор кислоты в воде. Пусть в сосуде содержится 10 литров раствора, который состоит из 3 литров кислоты и 7 литров воды. Тогда относительное (по отношению ко всему объему) содержание кислоты в растворе равно hello_html_m5ff0971d.gif. Это число и определяет концентрацию кислоты в растворе. Иногда говорят о процентном содержании кислоты в растворе. В приведенном примере процентное содержание будет таково: hello_html_m58dee601.gif. Как видно, переход от концентрации к процентному содержанию и наоборот весьма прост.

Итак, пусть смесь массы М содержит некоторое вещество массой m. Тогда:

  • концентрацией данного вещества в смеси (сплаве) называется величина hello_html_2a8e4b32.gif;

  • процентным содержанием данного вещества называется величина с×100%;

Из последней формулы следует, что при известных величинах концентрации вещества и общей массы смеси (сплава) масса данного вещества определяется по формуле m=c×M.

Задачи на смеси (сплавы) можно разделить на два вида:

  1. Задаются, например, две смеси (сплава) с массами m1 и m2 и с концентрациями в них некоторого вещества, равными соответственно с1 и с2. Смеси (сплавы) сливают (сплавляют). Требуется определить массу этого вещества в новой смеси (сплаве) и его новую концентрацию. Ясно, что в новой смеси (сплаве) масса данного вещества равна c1m1+c2m2, а концентрация hello_html_m7a500ef3.gif.

  2. Задается некоторый объем смеси (сплава) и от этого объема начинают отливать (убирать) определенное количество смеси (сплава), а затем доливать (добавлять) такое же или другое количество смеси (сплава) с такой же концентрацией данного вещества или с другой концентрацией. Эта операция проводится несколько раз.

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

Задача 1. Имеется кусок сплава меди с оловом общей массой 12 кг, содержащий 45% меди. Сколько чистого олова надо добавить к этому куску сплава, чтобы получившийся новый сплав содержал 40% меди?

Решение:

Пусть х кг олова надо добавить к сплаву. Так как процентное содержание меди в сплаве равно 45 %, то масса меди в первоначальном сплаве m=0,45×12=5,4 кг (где 0,45 – концентрация меди в сплаве).

Тогда 12 – масса нового сплава

И так как масса меди в первоначальном сплаве равна 5,4 кг, то

hello_html_5c873fb4.gif – концентрация меди в новом сплаве.

По условию hello_html_m292470e1.gif, решая уравнение, получаем х=1,5 кг.

Ответ: нужно добавить 1,5 кг чистого олова.

Задача 2. Имеются два раствора кислоты разной концентрации. Объем одного раствора 4 л, другого – 6 л. Если их слить вместе, то получится 35 % раствор кислоты. Если же слить равные объемы этих растворов, то получится 36 % раствор кислоты. Сколько литров кислоты содержится в каждом из первоначальных растворов?

Решение:

Пусть х л кислоты содержится в первом растворе,

у л кислоты содержится во втором растворе.

Тогда hello_html_m3f27eb20.gif – концентрация кислоты в первом растворе,

hello_html_m3ab6d30f.gif – концентрации кислоты во втором растворе.

Если слить два раствора, то получим раствор массой 4л+=10л, причем масса кислоты в нем будет х+у, тогда

hello_html_m6b05b4c2.gif – концентрация кислоты, после сливания обоих растворов.

Так как по условию в полученном таким образом растворе содержится 35% кислоты, то ее концентрация там равна 0,35.

Таким образом, получаем: hello_html_m7864170.gif или х+у=3,5.

Если будем сливать равные объемы растворов по m литров, то

hello_html_m4417efb9.gif – масса кислоты в полученном растворе,

2m – масса полученного раствора,

тогда

hello_html_m44f567ce.gif – концентрация кислоты в полученном растворе.

По условию

hello_html_m4955952a.gifили hello_html_607ddebf.gif.

Таким образом, получили систему двух уравнений

hello_html_m5d3a3c59.gifÞ hello_html_m8475c36.gifÞ hello_html_6f3e87cd.gifÞ

Þ hello_html_m53253377.gifÞ hello_html_m225a2f58.gif

Ответ: в первом растворе содержится 1,64 л кислоты, во втором – 1,86 л.

Задачи на проценты

Решение задач этого типа тесно связано с тремя алгоритмами: нахождения части от целого, восстановление целого по его известной части, нахождение процентного прироста. Рассмотрим эти алгоритмы.

  1. Пусть известна некоторая величина А, надо найти а % этой величины.

Если считать, что А есть 100%, а неизвестная часть х это а %, то из пропорции

hello_html_m670bf5ff.gifимеем hello_html_m4ea14e02.gif.

  1. Пусть известно, что некоторое число b составляет а % от неизвестной величины А. Требуется найти А.

Рассуждая аналогично, из пропорции получаем hello_html_m748c2fed.gif.

  1. Пусть некоторая переменная величина А, зависящая от времени t, в начальный момент t0 имеет значение А0, а в момент t1 – значение А1.

Тогда абсолютный прирост величины А за время t1–t0 будет равен А1–А0; относительный прирост этой величины вычисляется по формуле hello_html_595198bc.gif, а процентный прирост по формуле hello_html_1daf10f4.gif.

Задача 1. Для офиса решили купить 4 телефона и 3 факса на сумму 1470 долларов. Удалось снизить цену на телефон на 20%, и в результате за эту же покупку уплатили 1326 долларов. Найти цену факса.

Решение:

Пусть х – стоимость факса,

у – стоимость телефона.

По условию 4у+3х=1470.

Так как цену на телефон снизили на 20%, то телефон стал стоить 80% от первоначальной цены, то есть

0,8у – стоимость телефона после снижения.

По условию 3х+4×0,8у=1326.

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

hello_html_5f34da84.gif

Так как нам нужно найти только х, исключим у из системы, для чего первое уравнение умножим на (–0,8) и сложим со вторым: 0,6х=150 Þ х=250.

Ответ: факс стоит 250 долларов.



Задачи для самостоятельного решения

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

Наш адрес: 680000, г. Хабаровск, ул. Дзержинского, 48, ХКЦТТ ( ХКЗФМШ).


М9.9.1. Расстояние 450 км один из поездов проходит на 1,5 ч. быстрее другого. Найдите скорость каждого из поездов, если известно, что первый проходит 240 км за то же время, что второй проходит 200 км.

М9.9.2. Расстояние между городами А и В равно 50 км. Из города А в город В выехал велосипедист, а через 1 ч. 30 мин. вслед за ним выехал мотоциклист. Обогнав велосипедиста, он прибыл в город В на 1 ч. раньше него. Найдите скорость мотоциклиста, если известно, что она в 2,5 раза больше скорости велосипедиста.

М9.9.3. В реку впадает приток. Катер отходит от пункта А, находящегося на притоке, идет по течению 80 км до впадения притока в реку в пункте В, а затем идет вверх по реке до пункта С. На путь от А до С он затратил 18 ч., на обратный – от А до С – 15 ч. Найдите расстояние от пункта А до С, если известно, что скорость течения реки 3 км/ч, а собственная скорость катера 18 км/ч.

М9.9.4. Бассейн может наполниться водой из двух кранов. Если первый кран открыть на 10 мин., а второй – на 20 мин., то бассейн будет наполнен. Если первый кран открыть на 5 мин., а второй – на 15 мин., то заполнится 3/5 бассейна. За какое время из каждого крана в отдельности может заполниться весь бассейн?

М9.9.5. Двум рабочим была поручена работа. Второй приступил к работе на час позже первого. Через 3 ч. после того, как первый приступил к работе, им осталось выполнить 9/20 всей работы. По окончанию работы оказалось, что каждый выполнил половину всей работы. За сколько часов каждый, работая отдельно, может выполнить свою работу?

М9.9.6. Двое рабочих вытачивают вместе 136 деталей за 8 часов. Если бы первый делал на две детали в час меньше, а второй на 1 деталь больше, то на изготовление одной детали второй рабочий затратил бы на 4 минуты меньше, чем первый. Сколько деталей в час изготавливается первый рабочий?

М9.9.7. В сосуде было 12 л соляной кислоты. Часть кислоты отлили и сосуд долили водой. Затем снова отлили столько же и опять залили водой. Сколько жидкости отливали каждый раз, если в сосуде оказался 25% раствор кислоты?

М9.9.8. Имеется сталь двух сортов с содержанием никеля 5% и 40%. Сколько стали того и другого сорта надо взять, чтобы после переплавки получить 140 тонн стал и с содержанием никеля 30%?

М9.9.9. Из 22 кг свежих грибов получается 2,5 кг сухих грибов. Содержащих 12% воды. Какой процент воды в свежих грибах?

М9.9.10. Два завода по плану должны были выпустить за месяц 360 станков. Первый завод выполнил план на 112%, а второй – на 110%, вместе заводы выполнили за месяц 400 станков. Сколько станков сверх плана выпустил каждый завод в отдельности?




Название документа Тренировочные задачи.doc

Поделитесь материалом с коллегами:

Тренировочные задачи по математике

Часть 1. Арифметика

Задача 1.1. Наполненный доверху сосуд с водой весит 5 кг, а наполненный наполовину – 3 кг 250 г. Сколько воды вмещает сосуд?


Задача 1.2. Девять одинаковых открыток стоят меньше 10 рублей, а десять таких же открыток стоят больше 11 рублей. Сколько стоит одна открытка? (известно, что одна открытка стоит целое число копеек).


Задача 1.3. В банк кладется 100 рублей. В каком случае спустя 5 лет вкладчик получит больше денег: если банк начисляет 7% имеющейся суммы в год или если он начисляет 7/12% раз в месяц?


Задача 1.4. Города А и В расположены на реке в 10 км друг от друга. На что пароходу потребуется больше времени: проплыть от А до В и обратно, или проплыть 20 км по озеру?


Задача 1.5. Фрекен Бок съедает торт за полчаса, Малыш – за час, а Карлсон за 5 минут. За какое время они съедят торт вместе?

Указание: очень быстро они его съедят. Пусть это время равно х минут. Фр. Бок за это время съест hello_html_3cefc06e.gifчасть торта, Малыш - hello_html_618af937.gifчасть, а Карлсон - hello_html_m558abd90.gifчасть. В сумме получится 1. Откуда х=4 минуты.


Часть 2. Делимость и остатки

Задача 2.1. Кузнечик прыгает по прямой на 6 и на 8 см (в любую сторону). Сможет ли он попасть в точку, расстояние от которой до исходной равно: а) 7 см; б) 4 см?

Указание: при каждом прыжке расстояние от того места, в котором кузнечик находился первоначально до нового изменяется на четное число. Поэтому случай а) невыполним. А вот во втором случае нужно подумать.


Задача 2.2. Вася рвет газету на 8 частей, одну из получившихся частей – ещё на 8, и так далее. Сможет ли он разорвать газету на 2002 части?

Указание: первоначально имеется 8 кусочков и при каждом действии число кусочков увеличивается на 7. Поэтому общее число кусочков равно hello_html_3b357f56.gif. А можно ли число 2002 представить в таком виде?


Задача 2.3. Число при делении на 2 дает в остатке 1, а при делении на 3 дает в остатке 2. Найдите остаток от деления этого числа на 6.

Указание: представьте число в виде hello_html_m12c80fd6.gif и hello_html_mc7664f8.gif, и рассмотрите половину суммы этих представлений – это целое число. Тогда легко доказать, что k- нечетное число. Поэтому остаток от деления на 6 равен 5.


Задача 2.4. Докажите, что hello_html_4bb16ffb.gifделится на 6 при любом целом k.

Указание: покажите, что данное число есть произведение трех последовательных чисел.


Задача 2.5. На какую цифру оканчивается число hello_html_2ea2ef9e.gif?

Указание: степень тройки оканчивается на 3, 9, 7 и 1. Разберитесь, что получается в нашем случае.

Часть 3. Комбинаторика

Задача 3.1. а) В заборе 20 досок, каждую надо покрасить в синий, зеленый или желтый цвет, причем соседние доски должны быть покрашены в разные цвета. Сколькими способами это можно сделать?

б) А если требуется ещё, чтобы одна из досок была синей?

Указание: а) первую доску раскрашиваем одним из трех цветов, для каждой следующей остается только два цвета - всего hello_html_58dbe23d.gifспособов, а над случаем б) надо подумать.


Задача 3.2. В классе 25 человек. Сколькими способами можно выбрать из них а) дежурного и старосту; б) двух дежурных; в) трех дежурных?

Указание: а) староста может быть и дежурным, поэтому и старосту и дежурного можно выбрать 25 способами, а общее количество вариантов определяется умножением; б) и в) – после каждого назначения число вариантов уменьшается на единицу, поэтому получается 25х24:2 и 25х24х23:6 способов. Разберитесь, почему в первое число делится на 2, а второе на шесть?


Задача 3.3. У Пети есть 5 книг по математике, а у Васи – 7. Сколькими способами они могут обменять две книги одного на две книги другого?

Указание: Посчитайте, сколькими способами может выбрать две книги Петя и сколькими Вася, и перемножьте эти числа. (Петя выбирает книги (5х4)/2 способами!).


Задача 3.4. В кухне 5 лампочек, каждая может гореть или не гореть. Сколькими способами можно осветить кухню?


Задача 3.5. Меню в школьном буфете постоянно и состоит из 10 различных блюд. Чтобы разнообразить своё питание, Петя решил каждый день выбирать себе завтрак по-новому. а) Сколько дней ему удастся это делать? б) Сколько блюд он съест за это время? (Завтрак состоит из двух блюд.)


Часть 4. Принцип Дирихле

Принцип Дирихле состоит в следующем: если k объектов обладает n различными свойствами, и число k>n, то найдется по крайней мере два объекта, обладающих одинаковым свойством.


Задача 4.1. В классе учится 25 учеников.

а) Докажите, что найдется 2 ученика, родившихся в одном и том же месяце.

б) Обязательно ли найдется 3 таких ученика?


Задача 4.2. 15 ребят собрали 100 орехов. Докажите, что какие-то 2 из них собрали одинаковое число орехов.

Указание: докажите, что число 100 нельзя представить в виде суммы 15 различных неотрицательных целых чисел и примените принцип Дирихле.


Задача 4.3. Докажите, что из любых 10 натуральных чисел, ни одно из которых не делится на 10, можно выбрать: а) 2 числа, разность, которых делится на 10; б)* несколько чисел, сумма которых делится на 10.

Указание: а) – достаточно показать, что найдется два числа, оканчивающихся одной цифрой; б) – звездочка есть звездочка.


Задача 4.4. Из чисел 1, 2, …, 49, 50 выбрали 26 чисел. Обязательно ли среди них найдутся 2 числа, отличающиеся друг от друга на 1?

Указание: количество последовательных чисел, отличающихся друг от друга не менее чем на два не больше 50:2=25.


Задача 4.5.* Можно ли накрыть равносторонний треугольник двумя меньшими равносторонними треугольниками?

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


Часть 5. Логика

Задача 5.1. Можно ли имея лишь два сосуда емкостью 3 л и 5 л, набрать из крана в больший из сосудов 4 л воды?

Указание: можно, наберите 5 литров, отлейте 3 литра во второй сосуд, вылейте эту воду, тогда в 5 – литровом останется 2 литра воды. Перелейте эти 2 литра в 3-х литровый сосуд. Наберите полный 5 –литровый и долейте из него воду во второй сосуд (ровно 1 литр), тогда в первом сосуде останется 4 литра. (Придумайте другое решение, с меньшим расходом воды.)


Задача 5.2. В числе 3141592653589793 зачеркните 7 цифр так, чтобы осталось как можно большее число.


Задача 5.3. Есть три утверждения:

У Димы больше 1000 книг!

Да нет, у него меньше 1000 книг.

Ну уж одна-то книга у него есть.

Известно, что среди этих утверждений равно одно верное. Сколько книг может быть у Димы?

Указание: раз одно верное, то ровно два других – неверные, предполагайте по очереди верность каждого утверждения и выберите подходящий вариант.


Задача 5.4. У Серёжи было 7 картофелин, у Паши было 5, а у Коли вообще не было. Они сварили картошку и разделили ее поровну на троих. Благодарный Коля дал Серёже с Пашей 12 конфет. Как они должны поделить их по справедливости?

Указание: справедливо – значит пропорционально тому, сколько получил от каждого. Коля получил 4 картофелины: три от Сережи и одну от Паши.


Задача 5.5. Соревнование по стрельбе из лука проводилось в 2 дня. Каждый участник в первый день выбил столько очков, сколько все остальные вместе во второй день. Докажите, что все участники выбили поровну очков.


Часть 6. Геометрия

Задача 6.1. Нарисуйте на плоскости а) 4; б) 5; в) 6 точек так, чтобы любые три из них образовывали равнобедренный треугольник.

Указание: а) возьмите три вершины правильного треугольника и центр этого треугольника; б) вершины квадрата и точка пересечения его диагоналей; в) – придумайте сами.


Задача 6.2. а) На сколько частей могут делить плоскость три различные прямые? Для каждого случая нарисуйте пример; б) тот же вопрос для 4 прямых.

Указание: удобно рассмотреть случаи, когда нет параллельных прямых и ни какие три не пересекаются в одной точке, случай пересечения трех прямых, случай, когда одна пара параллельных прямых и т.д.


Задача 6.3. В треугольнике АВС угол В прямой, АВ=ВС=1. На стороне АС взяли точку и нашли сумму расстояний от неё до сторон АВ и ВС. Можно ли наверняка сказать какое получилось число?

Указание: можно, ответ: 1.


Задача 6.4. Можно ли разрезать какой-нибудь треугольник на два остроугольных треугольника?

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


Задача 6.5. Дан лист клетчатой бумаги. Как с помощью карандаша и линейки нарисовать квадрат, площадь которого в 5 раз больше площади одной клетки.

Указание: нужно построить отрезок, длина которого равна hello_html_m59c8c0fc.gif. Для этого нудно построить прямоугольный треугольник со сторонами 1 и 2 и взять его гипотенузу.


Задача 6.6. В треугольнике отметили середины двух сторон. С помощью только карандаша и односторонней линейки без делений найдите середину третьей стороны.

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


Задача 6.7. В трапеции АВСD основание АD больше основания ВС. Что больше: сумма углов А и D или сумма углов В и С?

Указание: продолжите боковые стороны трапеции так, чтобы они пересеклись в точке Е. Углы в треугольнике ЕВС равны углам А и D.


Задача 6.8. В треугольнике две высоты не меньше сторон, на которые они опущены. Найдите углы этого треугольника.

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


Задача 6.9. На стороне АВ квадрата АВСD построили (снаружи) равносторонний треугольник АКВ. Найдите радиус окружности, описанной около треугольника СКD, если АВ=1.

Указание: для вычисления радиуса описанной окружности удобно использовать формулу hello_html_m58c80a4.gif.


Часть 7. Разные задачи

Задача 7.1. Король со свитой движется из пункта А в пункт В со скоростью 5 км/ч. Каждый час он высылает гонцов в В, которые движутся со скоростью 20 км/ч. С какими интервалами прибывают гонцы в В?


Задача 7.2. Леспромхоз решил вырубить сосновый лес, но экологи запротестовали. Тогда директор леспромхоза всех успокоил, сказав: «В лесу 99% сосен. Мы будем рубить только сосны. После рубки сосны будут составлять 98% всех деревьев». Какую часть леса вырубит леспромхоз?


Задача 7.3.

А у нас в классе 25 человек, и каждый дружит ровно с семью одноклассниками!

Не может быть этого, - ответил приятелю Витя Иванов, победитель олимпиады.

Почему он так ответил?

Указание: Витя знает свойства графов (о том, что это такое вам самим нужно прочитать в книжке). Сумма степеней всех вершин графа – четное число, а в графе, связанном с этой задачей суммарная степень равна 7х25=175 – нечетное число.


Задача 7.4. Сумма квадратов двух целых чисел делится на 3. Докажите, что каждое из этих чисел делится на 3.


Задача 7.5. В стране 15 городов, каждый соединен дорогами не менее, чем с 7-ю другими. Докажите, что из любого города можно проехать в любой другой: либо напрямую, либо через один промежуточный город.

Указание: Рассмотрим город А. Он соединен дорогами с не менее чем семью городами В1, В2, …, В7, … Всего получилось не меньше 8 городов. Предположим, что есть город С, не связанный ни с А ни с В1, В2, …, В7, … Значит он связан только с теми городами, которые остались вне этого списка. Но таких городов меньше 7, что противоречит условию.


Задача 7.6. В классе 28 человек. Каждая девочка дружит с 4 мальчиками, а каждый мальчик – с 3 девочками. Сколько в классе мальчиков и девочек?

Указание: классическое решение основано на понятии двудольного графа. Но можно решить задачу и из общих соображений.


Задача 7.7. Докажите, что среди учеников любого класса найдутся двое, имеющие одинаковое число знакомых в этом классе (если, конечно, в этом классе не менее двух учеников).

Указание: в теории графов есть классическая теорема: в любом графе существуют две вершины с одинаковой степенью. Другой способ доказательства – по принципу Дирихле.


Задача 7.8. а) Сколько чисел от 1 до 1000 не содержат в своей записи цифру 3? А сколько содержат? б) Сколько чисел от 1 до 1000 содержат в своей записи цифры 1 и 2?

Указание: здесь на помощь должна прийти комбинаторика.


Задача 7.9. Ожерелье должно состоять из 5 бусин. Сколько таких ожерелий разного вида можно составить, если имеется неограниченное количество синих и зеленых бусин?

Указание: давайте посчитаем: одно только синее + одно только зеленое + одно с одной синей и четырьмя зелеными + одно с одной зеленой и четырьмя синими +… а сколько ожерелий можно получить из 2-х бусин одного и 3-х бусин другого – посчитайте сами.


Задача 7.10. Можно ли в таблице 5 5 расставить несколько чисел так, чтобы сумма чисел в любом столбце равнялась 8, а в любой строке – 9?

Указание: предположим, что можно. Сложите суммы, стоящие в столбиках и суммы, стоящие в строках. И там и там должна получиться сумма всех чисел, стоящих в таблице. А что получается на самом деле?


Задача 7.11. Квадрат 8 8 сложен из доминошек 1 2. Докажите, что какие то две из них образуют квадрат 2 2.

Указание: эта задача относится к математическому фольклору.


Оставшиеся задачи попробуйте решить без нашей помощи.

Задача 7.12. Дано 2002 целых числа. Известно, что сумма любых 23-ёх из них положительна. Докажите, что сумма всех чисел так же положительна.


Задача 7.13. Можно ли из квадрата со стороной 10 см вырезать несколько кругов, сумма диаметров которых больше 5 м?


Задача 7.14. Две каменные лестницы одинаковой высоты 1 м и с одинаковым основанием длины 2 м, покрыты дорожками. У первой лестнице 7 ступенек, а у второй – 9. Хватит ли дорожки, покрывающей первую лестницу, для покрытия второй?


Задача 7.15.* Кубик 3 3 3 легко распилить на 27 единичных кубиков шестью распилами. Можно ли уменьшить число распилов, если перекладывать распиленные части?



Название документа геометрия окружности.doc

Поделитесь материалом с коллегами:

Математика, 9-10 класс

Геометрия окружности

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

  1. Итак – окружность, это множество точек, расположенных на одинаковом расстоянии R от заданной точки О. О - центр окружности, R-радиус.

На координатной плоскости окружность логично задать уравнением

(х-х0)2+(y0)2= R2, (1)

где 00) –координаты центра окружности (точки О), а R-ее радиус.

Точка М(х,у) принадлежит окружности, если ее координаты х и у удовлетворяют уравнению (1). hello_html_md5a13d.png

Есть еще параметрическое уравнение окружности:

x=Rhello_html_m3c62c67f.gifcost+ х0

y=Rhello_html_m3c62c67f.gifsint+ у0 (2)

где 0≤t≤2hello_html_1bfc1af9.gif.

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

Упражнение 1. Докажите, что точки, координаты которых вычислены из уравнений (2) лежат на окружности, заданной уравнением (1).

2

Рисунок 1

. Большой интерес представляет взаимное расположение окружности и других объектов. Начнем с взаимного расположения прямой и окружности.

Кhello_html_7857f980.png
ак вы хорошо знаете, возможны три случая:

1). Окружность и прямая пересекаются.

2). Окружность и прямая имеют единственную общую точку (касания).

3). Окружность и прямая пересекаются в двух точках. (рис. 2)

Эhello_html_1b0833ac.png

Рисунок 2

ти три случая характеризуются соотношением между расстоянием hello_html_644d471.gif от прямой до центра окружности и радиусом. В первом случае hello_html_644d471.gif>R, во втором hello_html_644d471.gif= R и в третьем hello_html_644d471.gif<R.

Напомним также, что радиус окружности, проведенный в точку касания, перпендикулярен касательной.

3. Отрезок, концы которого лежат на окружности, называется хордой.

С

Рисунок 3


амая большая хорда – это диаметр. Она проходит через центр окружности. (рис.3)


Упражнение 2. Докажите, что серединный перпендикуляр к хорде является диаметром (т.е., что центр окружности лежит на этом перпендикуляре).

4hello_html_66ebc77e.png
. Рассмотрим теперь взаимное расположение окружности и угла. Естественно считать, что оба луча угла пересекают окружность. Возможно три случая расположения вершины угла:

1). Вне окружности.

2). На окружности (вписанный угол).

3). Внутри окружности.

Наибольший интерес представляет вписанные углы. Для них хорошо известна связь между величиной вписанного угла (hello_html_m2d06686e.gif) и центрального (hello_html_m33c0df0d.gif), опирающихся на общую дугу hello_html_1c9f61bf.gif: hello_html_1ee9d761.gif. (рис. 4).

Эhello_html_3797b663.png

Рисунок 4

то свойство дает изящное и очень полезное доказательство теоремы синусов: выражая боковую сторону hello_html_m39a026b5.gif (см. рис.5) через угол при вершине основания, получим: hello_html_m77c9ce80.gif (3), или hello_html_m532f31b1.gif. Т.е. отношение стороны треугольника к синусу противоположного угла всегда равно диаметру описанной окружности.

Ф

Рисунок 5

ормула (3) – главная рабочая формула для нахождения радиуса описанной окружности.

Пhello_html_fe94de3.pngредположим теперь, что угол А=90º, тогда угол hello_html_mcb7e170.gifº - развернутый, т.е. гипотенуза ВС является диаметром описанной окружности (рис.6). Отсюда также очевидно следует, что медиана прямого угла равна радиусу описанной окружности: OA=R.

Сформулируем и докажем важное свойство.

Т

Рисунок 6

еорема. Если точки А1, А2,…, Аn лежат по одну сторону от прямой ВС и отрезок ВС виден из них под одним углом (т.е. hello_html_7707454f.gifВА1С=hello_html_7707454f.gifВА2С=…=hello_html_7707454f.gifВАnС), то точки А1, А2,…, Аn, В и С лежат на одной окружности.

Доказательство:

  1. Из формул (3) следует, что радиусы описанных окружностей hello_html_2e85d6ba.gif ВА1С,…,hello_html_2e85d6ba.gifВАnС равны.

  2. Центры всех этих окружностей лежат на серединном перпендикуляре к ВС и по одну и ту же сторону от ВС.

Но этими двумя свойствами обладает только одна точка. Поэтому все центры описанных окружностей совпадают.

Упражнение 3. Докажите условие * из предыдущей теоремы.

Указание: вспомните, где лежит центр вписанной окружности остроугольного, прямоугольного и тупоугольного треугольников.


5. Вернемся к касательным. Как известно, из точки, лежащей вне окружности, можно провести ровно две касательных. (рис.7) Из т. Пифагора следует, что

MT12=MO2-R2=MT22,

т.е. отрезки касательных равны.

hello_html_332ee186.png

Рисунок 7

Вспомним, как строится касательная из точки к окружности:

1 Шаг: Находим середину отрезка ОМ, точку х.

2 Шаг: Строим окружность, с центром в точке Х и радиусом МХ.

3 Шаг: Находим точки Т1 и Т2- пересечения построенной и данной окружностей.

4 Шаг: Строим касательные МТ1 и МТ2.

hello_html_25e8ee0c.png

Рисунок 8

Замечание: Так как hello_html_7707454f.gif МТ1О опирается на диаметр МО второй окружности, то он прямой, т.е. МТ1hello_html_m3369453f.gifОТ1, но ОТ1 – радиус первой окружности, поэтому МТ1 – касательная.

6hello_html_m2ca02daa.png. Вписанная окружность.

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

Уточним сказанное:

1). В треугольнике окружность вписывается всегда, ее центр лежит на пересечении биссектрис треугольника.

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

Вычислить радиус вписанной окружности можно по формуле: hello_html_73ed58b4.gif, где S –площадь, P-периметр многоугольника.

З

Рисунок 9

амечание: Помимо вписанных, рассматривают также вневписанные окружности. Их центр лежит вне многоугольника, а окружность касается либо сторон, либо прямых, на которых эти стороны лежат. На рис. 9 изображены вписанная и вневписанная окружности треугольника.

Упражнение 4. Докажите, что центр вневписанной окружности лежит на пересечении биссектрис одного внутреннего и двух внешних углов треугольника.

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

Заметим, что hello_html_49589868.gif. Складывая любые два из этих уравнений и вычитая третье, мы получим 2x=b+c-a, 2y=a+c-b и 2z=a+b-c. Т.е. удвоенная величина отрезка равна сумме прилегающих сторон минус величина противолежащей стороны.

У

Рисунок 10

пражнение 5. Получите аналогичные формулы для вневписанной окружности.

7. Свойства секущих. Степень точки относительно окружности.

Иhello_html_m299b4b9b.pngз свойства вписанных четырехугольников (суммы противоположных углов равны 180º) следует, что треугольники АМС и DMB подобны (рис.11):

hello_html_7c756a21.gif.

Эта формула – известное утверждение о произведениях отрезков секущих, проведенных к окружности из одной точки. Рассмотрим специальную секущую (рис. 12), проходящую через центр окружности. Получим: hello_html_200dddd7.gif, но hello_html_2fb0b9ff.gif, а hello_html_m67ddc785.gif, поэтому

hello_html_6537f0fa.gif

(где МТ – касательная).

Для внутренних точек окружности можно получить аналогичные результаты (рис.13). Здесь будут подобными hello_html_2e85d6ba.gifMAD и hello_html_2e85d6ba.gifMBD, поэтому hello_html_6e3bd4bd.gif.

В

Рисунок 11

случае, когда секущая-диаметр (х1х2), получим hello_html_77f4a424.gif=hello_html_58cef4c.gif.

Как в первом, так и во втором случае, произведение секущих выразилось через радиус окружности R и расстояние МО от точки до ее центра. Величину MO2-R2 принято называть степенью точки относительно окружности (обозначение: dhello_html_m39608289.pngeg(M, ω)).

Со степенью связано много замечательных фактов геометрии.

1). Заметим, что все точки, имеющие одинаковую степень относительно данной окружности, лежат на окружности с тем же центром.

У

Рисунок 12

пражнение 6. Докажите сформулиро-ванное выше утверждение.

2). Рассмотрим две неконцентрических окружности. Справедлива теорема.


Тhello_html_m46b0d113.pngеорема. Множество точек, имеющих одинаковую степень относительно двух окружностей, лежит на прямой, перпендикулярной к линии центров этих окружностей. (Это т.н. радикальная ось).

Доказательство:

МО1222, МО22=(а-х)22

МО12-R1222-2ах+у2-R22hello_html_1b730b13.gifx=hello_html_m6318a41.gif(a2-R12+R22) (**)


К

Рисунок 13

ак мы видим, координата х точки М зависит только от a, R1, R2. Поэтому все точки с одной степенью лежат на прямой, заданной уравнением (**), которая перпендикулярна оси ОХ.

hello_html_4a1ebaec.png

Рисунок 14

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

Заметим, что точки, лежащие на окружности, имеют нулевую степень. Поэтому точки пересечения (касания) двух окружностей лежат на радикальной оси.

Упражнение 7. 1). Постройте радикальную ось двух пересекающихся окружностей.

2). То же для двух касающихся окружностей.

Указание: в первом случае это прямая, проходящая через точки пересечения окружностей (почему?), во втором – общая касательная, проведенная в точке касания.

Упражнение 8. Докажите, что радикальная ось делит общую касательную двух окружностей пополам.

Из упражнения 8 вытекает один способ построения радикальной оси для непересекающихся окружностей: строим общую касательную и из ее середины опускаем перпендикуляр на линию центров. Однако есть менее трудоемкий способ, реализованный на рис. 15:

1). Строим произвольную окружность, пересекающую две данных.

2). Строим радикальные оси для пар, образованных одной из данных окружностей и построенной.

3). Находим точку пересечения этих радикальных осей – она имеет одинаковую степень относительно всех трех окружностей, т.е. лежит на радикальной оси к двум исходным окружностям.

4). Опускаем из найденной точки перпендикуляр на линию центров, он и является радикальной осью.

hello_html_5dda652c.png

Рисунок 15.

КОНТРОЛЬНЫЕ ЗАДАНИЯ

Предлагаемые ниже задачи являются контрольным заданием для учащихся 9-10 классов. Для зачета вам рекомендуется решить не менее 6 задач. Правила оформления, адрес и другая полезная информация – в конце журнала. Желаем Вам успехов.


М.9.4.1.–М.9.4.8. – упражнения 1 – 8 из текста статьи.

Практические задания

М.9.4.9. Постройте общие касательные к двум пересекающимся окружностям. Постройте для них радикальную ось. Убедитесь, что радикальная ось поделила отрезки касательных пополам.

М.9.4.10. Для двух непересекающихся окружностей была построена радикальная ось, затем одну из этих окружностей стерли (на чертеже осталась только одна ее точка, не лежащая на линии центров). Можно ли восстановить стертую окружность? Опишите, как это сделать. Выполните построение.

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







Дорогие ребята, учителя и родители! Напоминаем, что наш журнал распространяется только по подписке. Подписку можно оформить во всех отделениях связи Хабаровского края. Подписной индекс в краевом каталоге: 545769.


Название документа методика подготовки к олимпиаде.doc

Поделитесь материалом с коллегами:

Метод инвариантов. Задачи на раскраску.

В некоторых задачах задан набор преобразований исходного объекта и спрашивается: можно ли используя эти преобразования, получить из одного состояния объекта другое? Перебором вариантов часто легко убедиться в правильности ответа “нельзя”, однако, обосновать это часто нелегко. Методом, позволяющим во многих случаях решать доказательную часть таких задач, является метод инвариантов. Инвариантом называется нечто не меняющееся при заданных преобразованиях (например, число, набор чисел, четность какого-л. числа и т.д.). Если значение инварианта у двух состояний объекта различно, то одно из них нельзя получить из другого. Придумать инвариант должен самостоятельно решающий.

Для построения инвариантов иногда бывают полезны вспомогательные раскраски, т.е. разбиения рассматриваемых объектов на несколько групп (каждая группа состоит из объектов одного цвета).

Задача 1. С таблицей, где имеется 15 чисел (1), а остальные равны 1, можно производить следующую операцию изменить знак двух (не больше, не меньше) чисел в таблице. Можно ли применяя эту операцию конечное число раз, получить таблицу, состоящую из чисел (+1)?

Решение. Ответ очевиден: нельзя. Инвариантом таблицы относительно рассматриваемой операции является произведение всех чисел в таблице. В начальный момент это произведение равно (1), а нам нужно получить таблицу, инвариант которой равен (+1).

Задача 2. Дана шахматная доска. Разрешается перекрашивать в другой цвет сразу все клетки какой-либо горизонтали или вертикали. Может ли при этом получиться доска, у которой ровно одна черная клетка?

Решение. При перекрашивании горизонтали или вертикали, содержащей k черных и 8k белых клеток, получится 8k черных клеток, и k белых клеток. Поэтому число черных клеток изменится на (8k)k=82k, т.е. на четное число. Т.к. четность числа черных клеток сохраняется, из исходных 32 черных клеток мы не можем получить одну черную клетку.

Задача 3. В каждой клетке доски 5х5 клеток сидит жук. В некоторый момент все жуки переползают на соседние по горизонтали или по вертикали клетки. Обязательно ли при этом останется пустая клетка?

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

Задача 4. В Эрмитаже есть две лестницы. Высота первой 13м, а ее длина по горизонтали 20м. У второй соответственно 11м и 22м. Обе лестницы покрыты ковровыми дорожками. Какая из дорожек длиннее, если на первой лестнице ступенек вдвое меньше, чем на второй?

Решение

Задача 5. На шести елках сидят шесть чижей, на каждой елке по чижу. Елки растут в ряд с интервалами 10м. Если какой-то чиж перелетает с одной елки на другую, то какой-то другой чиж обязательно перелетает на столько же метров, но в обратном направлении. Могут ли все чижи собраться на одной елке? А если чижей и ёлок семь?

Задача 6 Дно прямоугольной коробки вымощено плитками 1х4 и 2х2. Плитки высыпали из коробки, и одна плитка 2х2 потерялась. Её заменили на плитку 1х4. Докажите, что теперь дно коробки вымостить не удастся.

Задача 7. В таблице 3х3 закрашена одна клетка. Можно ли, перекрашивая строки и столбцы (как в задаче 2), сделать всю таблицу одноцветной?

Задача 8. Из квадрата 29х29 вырезали 99 квадратиков 2х2. Верно ли, что всегда можно вырезать еще один такой квадратик (разрезы проводятся по линиям сетки)?

Задача 9. Лист бумаги разрезали на 4 части. Некоторые из полученных частей режут еще на 4 части, любой из имеющихся кусков – еще на 4 и т.д. Можно ли таким образом получить 62 куска?

Задача 10. В стране Серобуромалин есть 13 серых, 15 бурых и 17 малиновых хамелеонов. Два хамелеона разного цвета, встречаясь, одновременно приобретают окраску третьего вида. Могут ли все хамелеоны через некоторое время стать одного цвета?

Задача 11. В пробирке находятся марсианские амебы трех типов: 20- типа А, 21- типа В, 22- типа С. Две амебы разных типов могут слиться в одну амебу третьего типа. Через некоторое время в пробирке оказалась одна амеба. Какого она типа?



Олимпиадные задачи на инварианты можно условно разбить на два вида: те, в которых требуется доказать некий инвариант, т. е. он явно определен, и те, в которых инвариант используется при решении и сразу не очевиден. Существует также класс задач, при решении которых используются полуинварианты – значения точной верхней и нижней граней для некоторой величины. Наиболее часто они используются в задачах на доказательство экстремума какой - либо величины. Рассмотрим способ решения задач по методу “Инвариант”.

В некоторых задачах по математике дается набор преобразований исходного объекта и спрашивается: можно ли, используя эти преобразования, получить из одного состояния объекта другое? Перебором вариантов часто легко убедиться в правильности ответа “нельзя”, однако обосновать этот ответ бывает трудно. Методом, позволяющим во многих случаях решать доказательную часть таких задач, является метод инвариант. Инвариантом называется нечто, не меняющееся в преобразованиях, например, число, набор чисел, четность какого – либо числа и другое. Если значение инварианта в двух состояниях объекта различно, то одно из них нельзя получить из другого. Придумать инвариант должен ученик, самостоятельно решающий задачу; обычно это вызывает у него затруднения. В качестве инварианта чаще всего рассматриваются четность (нечетность) чисел и остаток от деления. Причем применение четности – одна из наиболее встречающихся идей при решении олимпиадных задач.

Вспомним определения четного и нечетного числа. Особое внимание надо уделить абстрактному понятию четности, объяснить, что такое “разная четность”. Например, число х =2 имеет ту же четность, что и число х (или оба четные, или оба нечетные), а при прибавлении единицы четность меняется. Применение идеи четности и нечетности основано на двух важных утверждениях (леммах):

Лемма 1. Четность суммы нескольких целых чисел совпадает с четностью количества нечетных слагаемых.

Пример. Число 1 +2 + 3 + … + 10 – нечетное, так как в сумме 5 нечетных слагаемых. Пример 2. Число 5 + 7 + 9 + 11 +13 + 15 – четное, так как в сумме 6 нечетных слагаемых.

Лемма 2. Знак произведения нескольких (отличных от 0) чисел определяется четностью количества отрицательных сомножителей.

Рассматриваем с учащимися несколько примеров.

Пример 1. Число (-1) *(-2) *(-3) *(-4) положительно, так как в произведении четное число отрицательных сомножителей.
Пример 2. Число (-1) *2 * (-3) * (-4) отрицательно, так как в произведении нечетное число отрицательных сомножителей.

После этого разбираем подробно следующие задачи.

Задача 1. На листе бумаги написано число 11. Шестнадцать учеников передают листок друг другу, и каждый прибавляет к числу или отнимает от него единицу – как хочет. Может ли в результате получиться число 0?

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

Задача 2. На вешалке висят 20 платков. 17 девочек по очереди подходят к вешалке и либо снимают, либо вешают платок. Может ли после ухода девочек остаться ровно 10 платков?

Решение. После подхода первой девочки количество оставшихся платков либо 19, либо 21 (нечетное количество); после подхода второй девочки – либо 18, либо 20, либо 22 (четное количество); после подхода третьей девочки – либо 17, либо 21, либо 23, либо 19 (нечетное количество). После подхода 17 девочки остается нечетное количество платков. Получается противоречие. Значит, 10 платков остаться не может.

В первой и во второй задачах инвариантом является четность суммы чисел.

Задача 3. В таблице, где имеются 15 чисел (-1), можно производить следующую операцию: одновременно изменить знак двух (не более, не меньше) чисел в таблице. Можно ли, применяя эту операцию конечное число раз, получить таблицу, состоящую из (+ 1)?

Решение. Ответ: нельзя. Так как число чисел в таблице нечетно, а после каждой операции число чисел (+ 1) в таблице четно. На языке инвариантов это означает: инвариантом таблицы относительно введенной операции является произведение всех чисел в таблице. В начальный момент это произведение равно ( - 1), а нам нужно получить таблицу, инвариант которой равен ( + 1).

Задача 4. Имеется набор чисел а, в, с. Данный набор чисел меняется на тройку чисел: а + в – с, в + с – а, а + с – в. Дан набор чисел 2000, 2002, 2003. Можно ли из него получить набор из чисел 2001, 2002, 2003?

Решение. Ответ: нельзя. Так как (а + в + с) и (а + в - с) +(в +с – а) +(а + с – в) равны, а сумма 2000+2002 +2003 и сумма 2001 + 2002 +2003 различны.

Задача 5. На столе 6 стаканов, Из них 5 стоят правильно, а один перевернут вверх дном. Разрешается переворачивать одновременно 4 любых стакана. Можно ли все стаканы поставить правильно?

Решение. Нет, так как в любом случае перевернутых вверх дном стаканов будет числом нечетным.

Задача 6. Из цифр 2, 3, 4,… 9 составили два натуральных числа. Каждая цифра использовалась один раз. Могло ли одно из этих чисел оказаться вдвое больше другого?

Решение. Ответ: нет. Пусть а и b = 2а – полученные числа, S(a) и S(b) – суммы их цифр. По признаку делимости числа N и S(N) имеют одинаковые остатки при делении на 3. Поскольку число a + b = 3a делится на 3, то сумма S = S(a) + S(b) должна делиться на 3, что неверно, так как S = 2 + 3 + 4 + … + 9 = 44.

Задача 10. На доске написаны числа 1, 2, 3, …, 1998. За один ход разрешается стереть любые два числа и вместо них записать их разность. В результате многократного выполнения таких действий на доске окажется записанным одно число. Может ли оно быть нулем?

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

Задача 11. Числа 0,1,2,3, …, 9 записаны по кругу. За один ход разрешается прибавить к двум соседним числам одно и то же целое число. Можно ли за несколько ходов получить десять нулей?

Решение. Нельзя. При прибавлении одинаковых целых чисел к любым двум из имеющихся не меняет четность общей суммы всех чисел. Первоначально эта сумма равно 1 + 2 + 3 + … 9 = 45, следовательно, после каждого хода общая сумма полученных чисел должна быть нечетна, а нуль – четное число.

Задача 12. В десяти сосудах содержится 1, 2, 3,…, 10 литров воды. Разрешается перелить из сосуда А в сосуд В столько воды, сколько имеется в В. Можно ли добиться, чтобы после нескольких переливаний в 5 сосудах оказалось 3 литра, а в остальных 6, 7, 8, 9, 10?

Решение. Нельзя. Предложенная операция обладает полуинвариантом: при любом переливании число нечетных сосудов (содержащих нечетное число литров воды) не увеличивается. Количество таких сосудов уменьшается при переливании из нечетного сосуда в нечетный, а в остальных случаях не изменяется. Следовательно, переход 1, 2, … 10 —> 3, 3, 3, 3, 3, 6,…,10 невозможен, поскольку увеличивает число нечетных сосудов.





Метод математической индукции

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

Метод математической индукции состоит в следующем:

Предложение (утверждение) P(n), зависящее от натурального числа n, справедливо для любого натурального n если:

  1. P(1) является истинным предложением (утверждением);

  2. P(n) остается истинным предложением (утверждением), если n увеличить на единицу, то есть P(n + 1) - истинное предложение (утверждение).

Таким образом метод математической индукции предполагает два этапа:

  1. Этап проверки: проверяется, истинно ли предложение (утверждение) P(1).

  2. Этап доказательства: предполагается, что предложение P(n) истинно, и доказывается истинность предложения P(n + 1) (n увеличено на единицу).

В дальнейшем рассмотрим примеры применения метода математической индукции.

Пример 1. Доказать следующие равенства

hello_html_m5eded1fd.png

где n N.

Решение. a) При n = 1 равенство примет вид hello_html_21e57d3e.png1=1, следовательно, P(1) истинно. Предположим, что данное равенство справедливо, то есть, имеет место

hello_html_m53627b64.png.

Следует проверить (доказать), что P(n + 1), то есть

hello_html_m51afc1cf.png

истинно. Поскольку (используется предположение индукции)

hello_html_685fc0de.png

получим

hello_html_m2b16d3e5.png

то есть, P(n + 1) - истинное утверждение.

Таким образом, согласно методу математической индукции, исходное равенство справедливо для любого натурального n.

Замечание 2. Этот пример можно было решить и иначе. Действительно, сумма 1 + 2 + 3 + ... + n есть сумма первых n членов арифметической прогрессии с первым членом a1 = 1 и разностью d = 1. В силу известной формулы hello_html_509a55df.png, получим

hello_html_m60629270.png

b) При n = 1 равенство примет вид: 2·1 - 1 = 12 или 1=1, то есть, P(1) истинно. Допустим, что имеет место равенство

1 + 3 + 5 + ... + (2n - 1) = n2

и докажем, что имеет место P(n + 1):

1 + 3 + 5 + ... + (2n - 1) + (2(n + 1) - 1) = (n + 1)2

или

1 + 3 + 5 + ... + (2n - 1) + (2n + 1) = (n + 1)2.

Используя предположение индукции, получим

1 + 3 + 5 + ... + (2n - 1) + (2n + 1) = n2 + (2n + 1) = (n + 1)2.

Таким образом, P(n + 1) истинно и, следовательно, требуемое равенство доказано.

Замечание 3. Этот пример можно решить (аналогично предыдущему) без использования метода математической индукции.

c) При n = 1 равенство истинно: hello_html_49fa7441.png1=1. Допустим, что истинно равенство

hello_html_m7346d4db.png

и покажем, что

hello_html_m2addcdd.png

то есть истинность P(n) влечет истинность P(n + 1). Действительно,

hello_html_m4031eb5a.png

и, так как 2n2 + 7n + 6 = (2n + 3)(n + 2), получим

hello_html_4bf5c53d.png

и, следовательно, исходное равенство справедливо для любого натурального n.

d) При n = 1 равенство справедливо: hello_html_m2a77748d.png1=1. Допустим, что имеет место

hello_html_m727f239b.png

и докажем, что

hello_html_m2b711f1a.png

Действительно,

hello_html_1f86a241.png

e) Утверждение P(1) справедливо: hello_html_m34132a4.png2=2. Допустим, что равенство

hello_html_2fe26615.png

справедливо, и докажем, что оно влечет равенство

hello_html_123be431.png

Действительно,

hello_html_58f0f117.png

Следовательно, исходное равенство имеет место для любого натурального n.

f) P(1) справедливо: hello_html_262ae375.png1/3 = 1/3. Пусть имеет место равенство P(n):

hello_html_m24a5c221.png.

Покажем, что последнее равенство влечет следующее:

hello_html_67f10784.png

Действительно, учитывая, что P(n) имеет место, получим

hello_html_m5229fb58.png

Таким образом, равенство доказано.

Пример 2. Доказать неравенства

a) неравенство Бернулли: (1 + )n ≥ 1 + n, > -1,     n N.

b) x1 + x2 + ... + xnn,   если   x1x2· ... ·xn = 1   и   xi > 0,   hello_html_m5731ee5d.png.

c) неравенство Коши относительно среднего арифемтического и среднего геометрического
    hello_html_205d4b8f.png  где   xi > 0, hello_html_m5731ee5d.png, n ≥ 2.

d) sin2n + cos2n ≤ 1,     n N.

e) hello_html_2e792e29.png

f) 2n > n3,     n N, n ≥ 10.

Решение. a) При n = 1 получаем истинное неравенство

1 + ≥ 1 + .

Предположим, что имеет место неравенство

(1 + )n ≥ 1 + n

(1)

и покажем, что тогда имеет место и

(1 + )n + 1 ≥ 1 + (n + 1).

Действительно, поскольку > -1 влечет + 1 > 0, то умножая обе части неравенства (1) на ( + 1), получим

(1 + )n(1 + ) ≥ (1 + n)(1 + )

или

(1 + )n + 1 ≥ 1 + (n + 1) + n2

Поскольку n2 ≥ 0, следовательно,

(1 + )n + 1 ≥ 1 + (n + 1) + n2 ≥ 1 + (n + 1).

Таким образом, если P(n) истинно, то и P(n + 1) истинно, следовательно, согласно принципу математической индукции, неравенство Бернулли справедливо.

b) При n = 1 получим x1 = 1 и, следовательно, x1 ≥ 1 то есть P(1) - справедливое утверждение. Предположим, что P(n) истинно, то есть, если adica, x1,x2,...,xn - n положительных чисел, произведение которых равно единице, x1x2·...·xn = 1, и x1 + x2 + ... + xnn.

Покажем, что это предложение влечет истинность следующего: если x1,x2,...,xn,xn+1 - (n + 1) положительных чисел, таких, что x1x2·...·xn·xn+1 = 1, тогда x1 + x2 + ... + xn + xn + 1n + 1.

Рассмотрим следующие два случая:

1) x1 = x2 = ... = xn = xn+1 = 1. Тогда сумма этих чисел равна (n + 1), и требуемое неравество выполняется;

2) хотя бы одно число отлично от единицы, пусть, например, больше единицы. Тогда, поскольку x1x2· ... ·xn·xn + 1 = 1, существует еще хотя бы одно число, отличное от единицы (точнее, меньше единицы). Пусть xn + 1 > 1 и xn < 1. Рассмотрим n положительных чисел

x1,x2,...,xn-1,(xn·xn+1).

Произведение этих чисел равно единице, и, согласно гипотезе,

x1 + x2 + ... + xn-1 + xnxn + 1n.

Последнее неравенство переписывается следующим образом:

x1 + x2 + ... + xn-1 + xnxn+1 + xn + xn+1n + xn + xn+1

или

x1 + x2 + ... + xn-1 + xn + xn+1n + xn + xn+1 - xnxn+1.

Поскольку

(1 - xn)(xn+1 - 1) > 0,

то

n + xn + xn+1 - xnxn+1 = n + 1 + xn+1(1 - xn) - 1 + xn =
= n + 1 + xn+1(1 - xn) - (1 - xn) = n + 1 + (1 - xn)(xn+1 - 1) ≥ n + 1.

Следовательно,

x1 + x2 + ... + xn + xn+1n+1,

то есть, если P(n) справедливо, то и P(n + 1) справедливо. Неравенство доказано.

Замечание 4. Знак равенства имеет место тогда и только тогда, когда x1 = x2 = ... = xn = 1.

c) Пусть x1,x2,...,xn - произвольные положительные числа. Рассмотрим следующие n положительных чисел:

hello_html_m1b6c2035.png

Поскольку их произведение равно единице:

hello_html_42ce34b8.png

согласно ранее доказанному неравенству b), следует, что

hello_html_6dfafb51.png

откуда

hello_html_m1fa1ab92.png

Замечание 5. Равенство выполняется если и только если x1 = x2 = ... = xn.

d) P(1) - справедливое утверждение: sin2 + cos2 = 1. Предположим, что P(n) - истинное утверждение:

sin2n + cos2n ≤ 1

и покажем, что имеет место P(n + 1). Действительно,

sin2(n + 1) + cos2(n + 1) = sin2n·sin2 + cos2n·cos2 < sin2n + cos2n ≤ 1

(если sin2 ≤ 1, то cos2 < 1, и обратно: если cos2 ≤ 1, то sin2 < 1). Таким образом, для любого n N    sin2n + cos2n ≤ 1 и знак равенства достигается лишь при n = 1.

e) При n = 1 утверждение справедливо: hello_html_28b15513.png    1 < 3/2.

Допустим, что hello_html_45ee7962.pngи докажем, что

hello_html_5478c639.png

Поскольку

hello_html_m7a59f635.png

учитывая P(n), получим

hello_html_6b3ac33c.png

f) Учитывая замечание 1, проверим P(10): 210 > 103, 1024 > 1000, следовательно, для n = 10 утверждение справедливо. Предположим, что 2n > n3    (n > 10) и докажем P(n + 1), то есть 2n+1 > (n + 1)3.

Поскольку при n > 10 имеем hello_html_m5217e1f3.pngили hello_html_m399521f9.png, следует, что

2n3 > n3 + 3n2 + 3n + 1   или   n3 > 3n2 + 3n + 1.

Учитывая неравенство (2n > n3), получим

2n+1 = 2n·2 = 2n + 2n > n3 + n3 > n3 + 3n2 + 3n + 1 = (n + 1)3.

Таким образом, согласно методу математической индукции, для любого натурального n N,     n ≥ 10 имеем 2n > n3.

Пример 3. Доказать, что для любого n N

a) n(2n2 - 3n + 1)   делится на 6,

b) 62n-2 + 3n+1 + 3n-1   делится на 11.

Решение. a) P(1) - истинное утверждение (0 делится на 6). Пусть P(n) справедливо, то есть n(2n2 - 3n + 1) = n(n - 1)(2n - 1) делится на 6. Покажем, что тогда имеет место P(n + 1), то есть, (n + 1)n(2n + 1) делится на 6. Действительно, поскольку

n(n + 1)(2n + 1) = n(n - 1 + 2)(2n - 1 + 2) = (n(n - 1) + 2n)(2n - 1 + 2) =

= n(n - 1)(2n - 1) + 2n(n - 1) + 2n(2n + 1) = n(n - 1)(2n - 1) + 2n·3n =

= n(n - 1)(2n - 1) + 6n2

и, как n(n - 1)(2n - 1), так и 6n2 делятся на 6, тогда и их сумма n(n + 1)(2n + 1) делится 6.

Таким образом, P(n + 1) - справедливое утверждение, и, следовательно, n(2n2 - 3n + 1) делится на 6 для любого n N.

b) Проверим P(1): 60 + 32 + 30 = 11, следовательно, P(1) - справедливое утверждение. Следует доказать, что если 62n-2 + 3n+1 + 3n-1 делится на 11 (P(n)), тогда и 62n + 3n+2 + 3n также делится на 11 (P(n + 1)). Действительно, поскольку

62n + 3n+2 + 3n = 62n-2+2 + 3n+1+1 + 3n-1+1 =

= 62·62n-2 + 3·3n+1 + 3·3n-1 = 3·(62n-2 + 3n+1 + 3n-1) + 33·62n-2

и, как 62n-2 + 3n+1 + 3n-1, так и 33·62n-2 делятся на 11, тогда и их сумма 62n + 3n+2 + 3n делится на 11. Утверждение доказано.


Упражнения для самостоятельной работы

I. Доказать равенства

hello_html_m42484838.png

hello_html_38152ad6.png

hello_html_m35dc8987.png

hello_html_m7cd04b17.png

hello_html_43492b5a.png

hello_html_m146d013.png

hello_html_m31d17526.png

hello_html_m3f0e4a98.png

hello_html_ma442970.png

hello_html_m4002b4cc.png

hello_html_c53697c.png

hello_html_m67fb7403.png

hello_html_4741445b.png

II. Доказать неравенства

hello_html_fc1d5da.png

III. Доказать, что при любом натуральном n число an делится на b

a) an = 5n+3 + 113n+1,    b = 17,

b) an = 11n+2 + 122n+1,    b = 133,

c) an = 2n3 + 3n2 + 7n,    b = 6,

d) an = 10n + 18n - 28,    b = 27,

e) an = n5 - n,    b = 30.

Задачи с решением:

1.

Доказать, что hello_html_m5102dcbe.png.

____________________________________

Воспользуемся методом математической индукции.

1. База индукции.

При k = 1, hello_html_m3cc79d82.png= 2cosπ/4. Утверждение верно.

2. Переход индукции.

Допустим при неком k = n (n ∈ N) выражение

hello_html_m5102dcbe.png

истинно. Докажем, что оно верно и при k = n + 1, т.е.

hello_html_53073ae2.png

Но так как (исходя из истинности перехода индукции)

hello_html_1d14c789.png

то нам нужно доказать следующее утверждение:

hello_html_m4b5d172d.png= 2cosπ/2n+2.

Делаем преобразования:

2 + 2cosπ/2n+1 = 4cos2π/2n+2.

Для доказательства этого равенства воспользуемся формулой понижения степени косинуса 2cos2x = cos2x + 1. Тогда

4cos2π/2n+2 = 2(cosπ/2n+1 + 1) = 2cosπ/2n+1 + 2. Что и требовалось доказать.

Переход доказан, а потому исходное утверждение верно при любом nN.

2.  Найти все положительные корни уравнения nxn+1 - (n+1)xn + 1 = 0.

_________________________________________________________

Запишем уравнение в следующем виде:

nxn+1 - (n+1)xn + 1 = nxn(x - 1) - (xn - 1) = (x - 1)(nxn - xn-1 - xn-2 - ... - 1) = 0.

Очевидно, что x = 1 - корень уравнения. Докажем, что других положительных корней нет.

Действительно, если x > 1, то xn > xi, где i < n, а потому

   nxn - xn-1 - xn-2 - ... - 1 > nxn - nxn-1 > 0.

Если же 0 < x < 1, то xn < xi, где i < n, а потому

   nxn - xn-1 - xn-2 - ... - 1 < nxn - nxn-1 < 0.

Что и требовалось доказать.

Ответ: x = 1.

 3. Целые числа x, y, z удовлетворяют уравнению x3 + y3 = z3. Доказать, что хотя бы одно из этих чисел делится на 3.

____________________________________________________________________________

Докажем от обратного. Допустим все три числа x, y, z не делятся на 3. Тогда их можно представить в виде x = 3a ± 1, y = 3b ± 1, z = 3c ± 1. Наше уравнение будет иметь вид:

(3a ± 1)3 + (3b ± 1)3 = (3c ± 1)3;

27a3 ± 27a2 + 9a ± 1 + 27b3 ± 27b2 + 9b ± 1 = 27c3 ± 27c2 + 9c ± 1;

9(3a3 ± 3a2 + a + 3b3 ± 3b2 + b - 3c3hello_html_43f656a4.png3a2 - c) = hello_html_43f656a4.png1 ± 1 hello_html_43f656a4.png1.

Левая часть равенства делится на 9. Правая часть не делится при любов из вариантов знака ±. Мы пришли к противоречию. А значит одно из чисел делится на 3.

Что и требовалось доказать.

 4. Вычислить сумму 1/1·2 + 1/2·3 + ... + 1/n·(n + 1),  где nN.

____________________________________________

Воспользуемся следующим равенством:

1/k - 1/(k + 1) = 1/k·(k + 1).

Тогда нашу сумму можно переписать в следующем виде:

1/1·2 + 1/2·3 + ... + 1/n·(n + 1) = 1/1 - 1/2 + 1/2 - 1/3 + ... + 1/n - 1/(n + 1) = 1 - 1/(n + 1).

5. Доказать, что уравнение x3 - px + 1 = 0 не имеет рациональных корней при pZ, p > 2.

___________________________________________________________________________

Докажем сначала, что даное уравнение не имеет целых корней.

Докажем от обратного.

Пусть существует некое x1Z, так что x13 - px1 + 1 = 0, при pZ, p > 2.

Тогда x1(x12 - p) = -1.

Единственные решения в целых числах следующие:

x1 = 1, (x12 - p) = -1; Но тогда 1 - p = -1, откуда p = 2, что противоречит условию.

x1 = -1, (x12 - p) = 1; Тогда 1 - p = 1, p = 0, что опять же противоречит условию.

Значит целых решений нет. Покажем, что и дробных рациональных решений не существует при данном условии.

Снова докажем от обратного. Пусть существует некое x1Q \ Z, такое что x13 - px1 + 1 = 0, при pZ, p > 2.

В таком случае, по определению x1 можно представить в виде несократимой дроби m/n, mN, nZ. Отметим также, что если дробь m/n - несократима, то и дробь m3/n2 - несократима. Тогда уравнение будет иметь следующий вид:

(m/n)3 - p(m/n) + 1 = 0.

m3/n2 = pm - n.

Но справа у нас целое число, а значит и слева число целое. А это противоречит нашему предположению, что дробь m3/n2 - несократима.

Значит уравнение не имеет рациональных решений.

Что и требовалось доказать.


 


Название документа олимпиады кратко.doc

Поделитесь материалом с коллегами:

1. Доказательство от обратного (противного).

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

Доказательство истинности утверждения A проводится следующим образом. Сначала принимают, что суждение A - ложно. Затем доказывают, что в таком случае, некоторое утверждение B было бы верно (хотя оно заведомо неверно). Полученное противоречие показывает, что исходное предположение было неверно (предположение, что А - ложно). А потому утверждение А - истинно по закону двойного отрицания (¬(¬А) равносильно А).


Пример:

Доказать, что hello_html_m51313518.png- иррациональное число.

Доказательство: Докажем утверждение от обратного. Допустим число hello_html_m51313518.png- рациональное. Тогда по определению рационального числа, его можно представить в виде несократимой дроби m/n, где mZ, nN.

hello_html_m51313518.png= m/n. Поднесем в квадрат:

3 = m2/n2.

m2 = 3n2.

m2 делится на 3, а значит и m делится на 3. Тогда m2 делится на 9. Раз так, то и n2 делится на 3, а потому и n делится на 3. Получается - что дробь m/n сократима. Мы пришли к противоречию исходного суждения (что число рационально). Потому число hello_html_m51313518.png- иррациональное.


2. Метод математической индукции.

Один из основных методов доказательства. Смысл его состоит в следующем. Допустим у нас есть последовательность утверждений A1, A2, ... , An, An+1, ..., где nN. Все утверждения будут истинными, если:

1) Будет доказана база индукции, т.е. истинность утверждения A1;

2) Будет доказан переход, т.е. для любого n будет доказано, что если утверждение An - верно, то верно и утверждение An+1.


Пример:

Доказать, что если kN, то число k2 - k - четное.

Решение: Решим задачу с помощью метода математической индукции.

Проверим базу индукции - при k = 1, k2 - k = 0 - число четное.

Докажем переход. Допустим при некотором k = n, число n2 - n - четное. Докажем, что k = n+1 число (n + 1)2 - (n + 1) - тоже четное. Но (n + 1)2 - (n + 1) = n2 + 2n + 1 - n - 1 = n2 + n = n2 - n + 2n. Число n2 - n - четное, согласно предположению и 2n - четное. Сумма четных чисел - четная. Переход доказан.

Потому при любом kN число k2 - k - четное.


Существуют и другие вариации метода математической индукции. Например, есть последовательность утверждений B1, B2, ... , Bn, Bn+1, ..., где nN. Все утверждения будут истинными, если:

1) Будет доказана истинность утверждения B1;

2) Для любого n будет доказано, что если утверждения B1, ... , Bn - верны, то верно и утверждение Bn+1.

Это т.н. принцип полной математической индукции.


3. Принцип Дирихле.

Очевидный, простой в понимании, но в то же время, довольно мощный метод решения задач состоит в следующем: если A элементов разбиты на a групп, причем A > a, то хотя в одной группе будет находится более одного элемента (A, aN). Данный принцип, являющийся одной из форм метода от противного, был сформулирован известным немецким математиком Дирихле и зачастую формулируется так: Если в n клетках сидит m зайцев и m > n, то хотя бы в одной клетке сидят более одного зайца.

Главная цель в решении такого рода задач - определение "зайцев" и "клеток" в даной конкретной задаче. Чаще всего - это самый трудный этап в решении, так как выбор не всегда очевиден.

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


Пример:

Дано 7 различных натуральных чисел. Доказать, что из них можно выбрать два числа, чтобы их разность делилась на 6.

Доказательство: При делении на 6 существует шесть различных остатков: 0, 1, 2, 3, 4, 5. Применим принцип Дирихле. В даному случае "клетками" будут остатки, а "зайцами" - числа. Зайцев 7, а чисел 6. Потому как минимум два числа имеют одинаковые остатки.

Пусть эти числа x и y (x, yN)

Тогда x = 6p + r, а y = 6q + r. А значит x - y = 6(p - q).

Что и требовалось доказать.


4. Метод раскраски..

Суть данного метода состоит в следующем. Раскрасив некоторые ключевые элементы, которые фигурируют в задаче в несколько цветов, исследовать, что будет происходить, если выполнять условия задачи. Цвет позволяет значительно упростить понимание процесса, фигурируемого в условии, и зачастую приводит к решению. Этот метод позволяет эффективно решать ряд задач, в частности, игровые и шахматные задачи.


Пример:

Дан квадрат клетчатой бумаги размером 8 x 8, из которого вырезаны две крайние диагональные клетки (верхняя-правая и нижняя-левая). Можно ли полученную фигуру покрыть прямоугольниками размером 1 x 2?

Решение: Раскрасим наш обрезанный квадрат с помощью двух цветов в шахматную расцветку. Заметим, что отрезанные диагональные клетки будут одного цвета. Отметим также, что в нашем раскрашенном квадрате любые соседние две клетки (имеющие общую сторону) будут разного цвета. Это значит, что любой прямоугольник размером 1 x 2, которым мы будем пытаться покрыть обрезанный квадрат будет покрывать клетки обоих цветов. И если мы сможем покрыть обрезанный квадрат прямоугольниками 1 x 2, то будет покрыто одинаковое количество клеток с разными цветами; то есть фигура должна содержать одинаковое количество клеток обоих цветов. Но так как мы отрезали диагональные клетки одного цвета, то их количество в обрезанном квадрате на две меньше. Это означает, что мы не сможем польностью покрыть указанный обрезанный квадрат прямоугольниками 1 x 2.


hello_html_7d7ec105.png



Краткое описание документа:

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

Автор
Дата добавления 09.10.2015
Раздел Математика
Подраздел Другие методич. материалы
Просмотров1880
Номер материала ДВ-045547
Получить свидетельство о публикации


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