Курс "Олимпиадная математика"

Источник

Методическое обеспечение: Одной из важных задач введения  курса является не только прагматическая составляющая по развитию интереса к математике, но и  развитие у учащихся интереса собственно к математике, чувства эстетического удовлетворения от красиво решенной задачи, ведь именно правильно решенная задача в  математике является эквивалентом усвоения материала. Поэтому курс и строится на решении различных по степени важности и трудности задач. Направленность курса – развивающая. Прежде всего, он ориентирован на удовлетворение и поощрение любознательности  школьников, их аналитических и синтетических способностей. В процессе реализации  курса можно использовать разнообразные подходы к организации занятий,  представлению как теоретического так и  практического материала, включенного в модули, использование  игровых технологий. В рамках данного курса предполагается различный текущий и итоговый контроль: самостоятельные работы, зачетные работы по вариантам по модулям, выполнение решения задач  в программе «Ателье»,  общение в режиме «On line»,  участие в итоговой интеллектуальной игре.  Способ изложения материала предполагает применение редактора формул, с которым ребята знакомятся в случае необходимости на первом аудиторном занятии. С учетом того, что данный курс выбирается учащимися самостоятельно, целесообразно, при оценке результата,  использовать  нетрадиционную систему оценивания в виде символов, заносимых в специальную таблицу результатов. Практически по каждой теме, затронутой в программе   курса, ученику предоставляется  учителем  дополнительные материалы как теоретического, так и практического характера. Кроме того, материал  модулей, может  служить основой для докладов  и исследовательских работ.  В каждом модуле представлены решенные  задачи,  задачи для самостоятельного решения  с приведенными ответами и зачетные задания по вариантам.  Данный курс имеет прикладное и общеобразовательное значение, способствует развитию логического мышления учащихся, намечает и использует целый ряд межпредметных связей. Предполагаемые  результаты от реализации программы : В процессе  изучения курса учащиеся овладеют: 1         Умением математического моделирования при решении логических задач различной сложности; 2        Сведениями, которые не только помогут учащимся углубить свои знания по использованию признаков делимости, но проверить и закрепить практические навыки по решению задач; 3        Навыками решения нестандартных задач, включая задачи с параметрами. 4        Предоставление возможности создания  гибких  обучающих  ресурсов,  направленных на реализацию индивидуальных  образовательных потребностей обучающихся. Основными требованиями к учащимся, желающим учиться на дистанционных курсах являются следующие: наличие у учащихся математических способностей и желание развития их, наличие компьютера в домашних условиях ; умение работать на ПК, знание текстовых и графических редакторов, умение работать в Интернет. Отсюда можно выявить ожидаемый риск : - отсутствие компьютера дома у учащегося;  -не владение работы на ПК;  - не умение работать в Интернет Примерное учебно-тематическое планирование дистанционного  курса в  7 – 10  классах Вводное занятие: 1 час на овладение учащимися работы с оболочкой № Наименование модулей и блоков Всего часов Часы теории Часы практики зачет Число подготовленных учителем решенны задач Число задач самостоятельной работы с ответами Число задач в зачетной работе 1. Модуль 1:   Логические задачи 6 1 4 1 10 10 8    Модуль 2:  Принцип Дирихле 5 1 3 1 12 6 4    Модуль 3: Комбинаторика 7 2 4 1 12 19 14    Модуль 4 : Признаки делимости. 5 1 3 1 8 5 3 Модуль 5:  Задачи  с параметрами 3 1 1 1 7 3 5 2 Итоговая игра 3 Модуль 1. Логические задачи. Задачи с решениями: Задача №1   Однажды на лестнице была найдена странная тетрадь. В ней было записано сто утверждений:                             "В этой тетради ровно одно неверное утверждение";                             "В этой тетради ровно два неверных утверждения";                               "В этой тетради ровно три неверных утверждения";                                    ...                                  "В этой тетради ровно сто неверных утверждений".                                  Есть ли среди этих утверждений верные, и если да, то какие? Решение: То, что в тетради записано 100 утверждений, каждые два из которых противоречат друг другу, означает, что если среди них и есть верные утверждения, то их не может быть более одного. Посмотрим, может ли здесь быть хотя бы одно верное утверждение. Если верно ровно одно утверждение, то ровно девяносто девять неверных. А такое утверждение в тетради есть: "В этой тетради ровно девяносто девять неверных утверждений". Итак, в тетради записано ровно одно верное утверждение. Ответ: Одно верное утверждение: "В этой тетради ровно девяносто девять неверных утверждений". Задача №2  В гости пришло 10 гостей и каждый оставил в коридоре пару калош. Все пары калош имеют разные размеры. Гости начали расходиться по одному, одевая любую пару калош, в которые они могли влезть (т.е. каждый гость мог надеть пару калош, не меньшую, чем его собственные). В какой-то момент обнаружилось, что ни один из оставшихся гостей не может найти себе пару калош, чтобы уйти. Какое максимальное число гостей могло остаться? Решение:Пронумеруем гостей и их пары калош числами от 1 до 10 в порядке возрастания размера калош. Предположим, что осталось 6 гостей (и соответственно 6 пар калош). Тогда наименьший номер оставшегося гостя не больше 5, а наибольший номер оставшихся пар калош не меньше 6, поэтому гость с наименьшим номером сможет надеть калоши с наибольшим номером. Противоречие. С другой стороны, если последовательно уходили гости с номерами 1, 2, 3, 4, 5, и надевали соответственно калоши с номерами 10, 9, 8, 7, 6, то ни один из оставшихся пяти гостей не сможет надеть ни одну пару оставшихся калош. Ответ: 5 Задача №3  На столе лежат в ряд четыре фигуры: треугольник, круг, прямоугольник и ромб. Они окрашены в разные цвета: красный, синий, жёлтый, зелёный. Известно, что красная фигура лежит между синей и зелёной; справа от жёлтой фигуры лежит ромб; круг лежит правее и треугольника и ромба; треугольник лежит не с краю; синяя и жёлтая фигуры лежат не рядом. Определите, в каком порядке лежат фигуры и какого они цвета. Решение: Для удобства изложения повторим все условия задачи: 1) красная фигура  — между синей и зелёной; 2) справа от жёлтой фигуры  — ромб; 3) круг  — правее и треугольника и ромба; 4) треугольник  — не с краю;  5) синяя и жёлтая фигуры  — не рядом. Поскольку красная фигура лежит между синей и зелёной (условие 1), а жёлтая  — не рядом с синей (условие 5), то возможны только два варианта расположения фигур по цвету: "синяя, красная, зелёная, жёлтая" или "жёлтая, зелёная, красная, синяя". Первый из приведённых вариантов неверен, поскольку по условию 2 жёлтая фигура не может лежать на правом крае. Остаётся только одна возможность расположения фигур по цветам: "жёлтая, зелёная, красная, синяя". Из условия 2 сразу же определяется, что ромб зелёный. Отсюда и из условия 4 следует, что треугольник красный. В свою очередь отсюда и из условия 3 следует, что круг синий. Значит, прямоугольник может быть только жёлтым. Окончательный ответ: жёлтый прямоугольник, зелёный ромб, красный треугольник, синий круг. Ответ:  Жёлтый прямоугольник, зелёный ромб, красный треугольник, синий круг. Задача №4  На столе лежат в ряд пять монет: средняя  — вверх орлом, а остальные  — вверх решкой. Разрешается одновременно перевернуть три рядом лежащие монеты. Можно ли при помощи нескольких таких переворачиваний все пять монет положить вверх орлом? Решение: Это действительно можно сделать, причём довольно быстро. Перевернём первые три монеты. Тогда первые две монеты будут лежать вверх орлом, а последние три  — вверх решкой. Теперь переворачиваем последние три монеты, и все пять монет лежат вверх орлом.Ответ:   Да:  первым ходом перевернём первые 3 монеты,  вторым  — последние 3. Задача №5  Из набора гирек с массами 1, 2, ..., 101 г потерялась гирька массой 19 г. Можно ли оставшиеся 100 гирек разложить на две кучки по 50 гирек в каждой так, чтобы массы обеих кучек были одинаковы? Решение: Положим в первую кучку две гирьки массой 101 г и 1 г, а во вторую  — 100 г и 2 г; затем в первую две гирьки  — 99 г и 3 г, а во вторую  — 98 г и 4 г. Так будем действовать, пока не положим во вторую кучку гирьки в 84 г и 18 г. К этому моменту в каждой кучке будет лежать по 18 гирек. Теперь положим в первую кучку две гирьки массой 83 г и 20 г, а во вторую  — 82 г и 21 г. Так будем продолжать до тех пор, пока во вторую кучку не придётся положить последнюю пару гирек массой 52 г и 51 г. Ответ: Да. Задача № 6  Первый вторник месяца Митя провёл в Смоленске, а первый вторник после первого понедельника  — в Вологде. В следующем месяце Митя первый вторник провёл во Пскове, а первый вторник после первого понедельника  — во Владимире. Сможете ли вы определить, какого числа и какого месяца Митя был в каждом из городов? Решение:  Поскольку Митя не мог провести один и тот же день и в Смоленске и в Вологде, значит, месяц начинался во вторник (ведь иначе первый вторник и первый вторник после первого понедельника совпали бы). Аналогично заключаем, что и второй месяц должен начинаться во вторник. Это возможно только в случае, когда один месяц  — февраль, а другой  — март, причём год не високосный. Отсюда уже легко получить, что в Смоленске Митя был 1 февраля, в Вологде  — 8 февраля, во Пскове  — 1 марта, во Владимире  — 8 марта. Ответ:  В Смоленске  — 1 февраля, в Вологде  — 8 февраля, в Пскове  — 1 марта, во Владимире  — 8 марта. Задача № 7 В равенстве 101 - 102 = 1 передвиньте одну цифру так, чтобы оно стало верным. Решение:  Если цифру 2 в числе 102 передвинуть вверх, на место показателя степени, то исходное равенство примет вид 101 - 102 = 1 и будет верным. Ответ:  Цифру 2 в числе 102 надо поставить на место показателя степени. Задача № 8 На острове живут два племени  — аборигены и пришельцы. Известно, что аборигены всегда говорят правду, пришельцы  — всегда лгут. Путешественник нанял туземца-островитянина в проводники. По дороге они встретили какого-то человека. Путешественник попросил проводника узнать, к какому племени принадлежит этот человек. Проводник вернулся и сообщил, что человек назвался аборигеном. Кем был проводник  — аборигеном или пришельцем? Решение: Второй туземец, кем бы он ни был, на вопрос: "Абориген ли Вы?" ответит положительно. Значит, проводник не обманул путешественника, следовательно, и он тоже абориген. Ответ: Проводник абориген. Задача № 9 В день рождения дяди Федора почтальон Печкин хочет выяснить, сколько тому лет. Шарик говорит, что дяде Федору больше 11 лет, а кот Матроскин утверждает, что больше 10 лет. Сколько лет дяде Федору, если известно, что ровно один из них ошибся? Ответ обоснуйте.Решение: Заметим, что если не ошибся Шарик, то не ошибся и Матроскин, что противоречит условию. Значит, Шарик сказал неправду, в отличие от кота Матроскина. Таким образом, дяде Федору больше 10 лет, но не меньше 11. Следовательно, дяде Федору исполнилось 11 лет. Ответ : Дяде Федору 11 лет. Задача № 10  В чашке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в чашке; сосуд с лимонадом стоит между кувшином и сосудом с квасом; в банке не лимонад и не вода; стакан стоит около банки и сосуда с молоком. В какой сосуд налита каждая из жидкостей? Решение: В банке может быть только квас, ибо из условия следует, что там не лимонад, не вода и не молоко. В чашке  — лимонад, так как известно, что там не молоко, не вода и не квас. Поскольку в стакане  не молоко, не квас, не лимонад  — значит, вода, а в кувшине  — то, что осталось, т.е. молоко.Ответ:  В чашке  — лимонад, в стакане  — вода, в кувшине  — молоко, в банке  — квас. Задачи для самостоятельного решения(с рекомендациями и ответами).  Задача №1 Старый сапожник Карл сшил сапоги и послал своего сына Ганса на базар  — продать их за 25 талеров.  На базаре к мальчику подошли два инвалида (один без левой ноги, другой  — без правой) и попросили продать им по сапогу. Ганс согласился и продал каждый сапог за 12,5 талера. Когда мальчик пришёл домой и рассказал всё отцу, Карл решил, что инвалидам надо было продать сапоги дешевле  — каждому за 10 талеров. Он дал Гансу 5 талеров и велел вернуть каждому инвалиду по 2,5 талера. Пока мальчик искал на базаре инвалидов, он увидел, что продают сладости, не смог удержаться и истратил 3 талера на конфеты. После этого он нашёл инвалидов и отдал им оставшиеся деньги  — каждому по одному талеру. Возвращаясь домой, Ганс понял, как нехорошо он поступил. Он рассказал всё отцу и попросил прощения. Сапожник сильно рассердился и наказал сына, посадив его в тёмный чулан. Сидя в чулане, Ганс задумался. Получалось, что раз он вернул по одному талеру, то инвалиды заплатили за каждый сапог по 11,5 талера: 12, 5 - 1 = 11, 5. Значит, сапоги стоили 23 талера: 11, 5 + 11, 5 = 23. И 3 талера Ганс истратил на конфеты, следовательно, всего получается 26 талеров: 23 + 3 = 26. Но ведь было-то 25 талеров! Откуда же взялся лишний талер? Подсказка :Подумайте, сколько денег должен был получить Карл, сколько он их получил и почему. Ответ:   3 талера, которые Ганс истратил на конфеты, надо не прибавить к стоимости сапог, а вычесть из неё. Тогда мы получим 20 талеров  — ту сумму, которую в итоге получил Карл. Задача №2  Девочка заменила каждую букву в своём имени её номером в русском алфавите. Получилось число 2011533. Как её зовут? Подсказка : Обратите внимание: первая буква имеет номер либо 2, либо 20. Ответ:  Девочку зовут Таня. Задача № 3: Золотоискатель Джек добыл 9 кг золотого песка. Сможет ли он за три взвешивания отмерить 2 кг песка с помощью чашечных весов: а) с двумя гирями — 200 г и 50 г; б) с одной гирей 200 г? Подсказка: Попробуйте начать с деления песка на две равные части. Ответ: Сможет в обоих случаях. Задача № 4 В комнате находятся 85 воздушных шаров  — красных и синих. Известно, что: 1) по крайней мере один из шаров красный; 2) из каждой произвольно выбранной пары шаров по крайней мере один синий. Сколько в комнате красных шаров? Подсказка: Подумайте, может ли в комнате быть два красных шара. Ответ: 1 шар. Задачи для самостоятельного решения(с ответами).  Задача № 1: Федя всегда говорит правду, а Вадим всегда лжёт. Какой вопрос надо было бы им задать, чтобы они дали на него одинаковые ответы? Ответ:   "Тебя зовут Федя?" Задача №2: Когда три подруги  — Надя, Валя и Маша  — вышли гулять, на них были белое, красное и синее платья. Туфли их были тех же трех цветов, но только у Нади цвета туфель и платья совпадали. При этом у Вали ни платье, ни туфли не были синими, а Маша была в красных туфлях. Определите цвет платьев и туфель каждой из подруг. Ответ: У Нади туфли и платье синего цвета;  у Вали туфли белые, платье красное;  у Маши туфли красные, платье белое. Задача №3: Пять первоклассников стояли в шеренгу и держали 37 флажков. У всех справа от Таты  — 14 флажков, справа от Яши  — 32, справа от Веры  — 20, справа от Максима  — 8. Сколько флажков у Даши? Ответ:  8 флажков. Задача №4: Мастер спорта Седов, кандидат в мастера Чернов и перворазрядник Рыжов встретились в клубе перед тренировкой. -- Обратите внимание,  — заметил черноволосый,  — один из нас седой, другой  — рыжий, третий  — черноволосый. Но ни у одного из нас цвет волос не совпадает с фамилией. Забавно, не правда ли? -- Ты прав,  — подтвердил мастер спорта. Какого цвета волосы у кандидата в мастера? Ответ: Седые. Задача № 5: Сирень. В вазе стоит букет из 7-ми белых и голубых веток сирени. Известно, что 1) по крайней мере, одна ветка белая, 2) из любых двух веток хотя бы одна — голубая. Сколько в букете белых веток и сколько голубых? Ответ: что белая ветка — одна, а голубые — остальные шесть. Задача №6 В книжном шкафу стоят по порядку четыре тома собрания сочинений Астрид Линдгрен, по 200 страниц в каждом томе. Червячок, живущий в этом собрании прогрыз путь от первой страницы первого тома до последней страницы четвертого тома. Сколько страниц прогрыз червячок? Ответ: 400 страниц. Задачи для зачета.  Задача №1 Мудрецу С. сообщили сумму трёх натуральных чисел, а мудрецу П. - их произведение. - Если бы я знал - сказал С., - что твоё число больше, чем моё, я бы сразу назвал три искомых числа. - Мое число меньше, чем твоё - ответил П., а искомые числа ..., ... и ... . Какие числа назвал П.? Задача №2 Три человека A, B, C пересчитали кучу шариков четырёх цветов. При этом каждый из них правильно различал какие-то два цвета, а два других мог путать: один путал красный и оранжевый, другой — оранжевый и жёлтый, а третий — жёлтый и зелёный. Результаты их подсчётов приведены в таблице. Сколько каких шариков было на самом деле? Задача № 3 На острове Контрастов живут и рыцари, и лжецы. Рыцари всегда говорят правду, лжецы всегда лгут. Некоторые жители заявили, что на острове чётное число рыцарей, а остальные заявили, что на острове нечётное число лжецов. Может ли число жителей острова быть нечётным?   Задача № 4 Одного из близнецов зовут Ваня, другого - Витя. Один из братьев всегдв говорит правду, а другой всегда лжет. Можно задать один вопрос одному из братьев, на который тот ответит "да" или "нет". Выясните, кого из близнецов как зовут. Задача № 5 Женю, Лёву и Гришу рассадили так, что Женя мог видеть Лёву и Гришу, Лёва  — только Гришу, а Гриша  — никого. Потом из мешка, в котором лежали две белые и три чёрные шапки (содержимое мешка было известно мальчикам), достали и надели на каждого шапку неизвестного ему цвета, а две шапки остались в мешке. Женя сказал, что он не может определить цвет своей шапки. Лёва слышал ответ Жени и сказал, что и у него не хватает данных для определения цвета своей шапки. Мог ли Гриша на основании этих ответов определить цвет своей шапки? Задача № 6 В семье Семеновых 5 человек: муж, жена, их сын, сестра мужа и отец жены. Все они работают. Один — инженер, другой — юрист, третий — слесарь, четвертый — экономист, пятый — учитель. Вот что еще известно о них. Юрист и учитель не кровные родственники. Слесарь — хороший спортсмен. Он пошел по стопам экономиста и играет в футбол за сборную завода. Инженер старше жены своего брата, но моложе, чем учитель. Экономист старше, чем слесарь. Назовите профессии каждого члена семьи Семеновых. Задача №7 На острове живут рыцари, которые всегда говорят правду, и лжецы, которые всегда лгут. Путник встретил троих островитян и спросил каждого из них: «Сколько рыцарей среди твоих спутников?». Первый ответил: «Ни одного». Второй сказал: «Один». Что сказал третий? Задача № 8 Путешественник, попавший в государство, встретил четырех людей из задачи 3 и задал им вопрос:"Кто вы?".   Он получил такие ответы: 1-ый: "Все мы лжецы". 2-ой: "Среди нас 1 лжец". 3-ий: "Среди нас 2 лжеца". 4-ый: "Я ни разу не соврал и сейчас не вру". Путешественник быстро сообразил, кем является четвертый житель. Как он это сделал?                   Модуль 2. Принцип Дирихле. Задачи с решениями.  Вполне возможно, что вы уже слышали про принцип Дирихле. Тогда он, скорее всего, представлял перед вами в какой шутливой формулировке: если в клетках N сидят не менее N+1 кроликов, то в какой – то из клеток сидит не менее двух кроликов. Обратите внимание на расплывчатость вывода «в какой – то из клеток», «не менее». Это является, пожалуй,     отличительной  чертой принципа Дирихле, которая иногда приводит к возможности неожиданных выводов на основе, казалось бы, совершение недостаточных сведений. Доказательство самого принципа чрезвычайно просто, в нем используется тривиальный подсчет кроликов в клетках. Если бы в каждой клетке сидело не более одного кролика, то всего в наших N клетках сидело бы не более N кроликов, что противоречило бы условиям. Таким образом, мы доказали принцип Дирихле методом от противного. Но, спросите вы, разве о кроликах идет речь в задаче:  Задача № 1 В мешке лежат шарики двух различных цветов: черного и белого. Какое наименьшее число шариков нужно вынуть всплошную так , чтобы среди них заведомо оказались два шарика одного цвета?      Решение: 1) Достанем из мешка 3 шарика. Если бы среди этих шариков было не более одного шарика каждого из двух цветов, то всего было бы не более двух шаров – это очевидно, и противоречит тому, что мы достали три шарика. С другой стороны понятно, что двух шариков может и не хватить. Ясно, что кроликами здесь являются шарики, а клетками – цвета: черный и белый. Задача № 2 В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок. Решение: Перед нами миллион «кроликов» - елок и увы всего лишь 600001 клетка с номерами от 0 до 600000. Каждый кролик елка сажается нами в клетку с номером, равным количеству иголок на этой елке. Так как «кроликов» гораздо больше, чем клеток, то в какой – то клетке сидит по крайней мере два «кролика» - если бы в каждой сидело не более одного, то всего «кроликов» - елок было бы не более 600001 штук. Но ведь если два кролика – елки сидят в одной клетке, то количество иголок у них одинаково.        Обращаем внимание на то, что формулирование этих задач носят тот же налет расплывчатости вывода, что и сам принцип Дирихле. Часто именно такие вопросы и решаются с его помощью. В самой простой и несерьезной форме он выглядит так «Нельзя посадить семерых зайцев в три клетки так, чтобы в каждой клетке находилось не больше двух зайцев». Действительно, если в каждой клетке не более двух зайцев, то всего зайцев не больше, чем 2*3=6, что противоречит условию. Еще решим несколько задач, выбирая каждый раз подходящих «зайцев» и строя соответствующие «клетки». Задача № 3  В   классе 30 человек. Саша Иванов в диктанте сделал 13 ошибок, а остальные  - меньше. Докажите, что по крайней мере 3 ученика сделали ошибок поровну (может быть по 0 ошибок)  Решение: Здесь «зайцы» - ученики, «клетки» - число сделанных ошибок. В клетку 0 «посадили всех то не сделал ни одной ошибки, в клетку 1 – тех, у кого одна ошибка, в клетку 2 – две и так до клетки 13, куда попал один Саша Иванов.   Теперь применим Принцип Дирихле( Это очень важное место ). Докажем утверждение задачи от противного. Предположим, никакие три ученика не сделали по одинаковом числу ошибок, т.е. в каждую «клетку» 0,1,2, ….12 попало меньше 3 школьников. Тогда в каждой из них два человека или меньше, а всего в этих 13 клетках не более 2х13=26 человек. Добавив Сашу Иванова, все равно не наберем 30 ребят. Противоречив следовательно, утверждение задачи верно, но по крайней мере трое учеников сделали поровну ошибок.     Можно ли утверждать, что ровно трое сделали поровну ошибок? Нет, конечно. Возможно, все ребята, кроме Саши, написали диктант без единой ошибки. Можно ли надеяться, что по крайней мере четверо попали в одну клетку? Нет и этого предполагать нельзя. Условию задачи удовлетворяет класс, в котором ученики распределились по числу сделанных ошибок так: по 3 человека. Сделали ошибки 0,1,2, по 2 человека – 3,4,…12 ошибок и один Саша – 13 ошибок. Задача № 4  Пусть в классе 41 человек, а не 30, а все остальные условия такие как в задаче 1. Докажите, что найдутся четверо, сделавшие одинаковое число ошибок. Решение: На 13 «клеток» для сделавших 0,1,…12 ошибок приходится 40 учеников. Если бы в каждой клетке было бы не более трех учеников, их всего было не более 3х13=39. Задача № 5  На Земле живет более 3,6 миллиарда человек. Известно, что среди них не более 1% людей старше 100 лет. Докажите, что найдутся два человека, которые родились в одну и туже секунду. Решение : В году менее 370 дней. За 100 лет пройдет менее чем 37000 дней или менее 3330000000с. Из условия  задачи следует, что не старше 100 лет по крайней мере 99%, т.е. 3564000000 людей. Для завершения задачи достаточно сослаться на принцип Дирихле. Задача № 6  В доме 123 жильца, им вместе 3813 лет. Можно ли выбрать 100 из них, которым вместе не менее 3100 лет? Решение : Рассмотрим жильцов по возрасту и возьмем 100 самых старших. Возраст самого молодого из этой сотни не меньше чем возраст тех кого не включили в сотню. Предположим, что сумма возрастов отобранной сотни меньше 3100 лет. Тогда возраст самого молодого из них меньше 3100:10=31 года. Следовательно, возраст каждого из них вошедшего в сотню старших тоже меньше 31 года, значит сумма возрастов не вошедших в сотню меньше 31х23=713 лет, а сумма всех возрастов менее 3100+713=3813 лет, что противоречит условию. Задача № 7 Имеется 25 короб конфет трех сортов (в каждой коробке конфеты одного сорта). Доказать, что среди них обязательно есть 9 коробок конфет одного сорта. Решение: Допустим, что мы раскладываем 24 коробки в 3 ящика по сортам. Самый неблагоприятный для нас вариант, когда в каждом ящике по 8 коробок. Но у нас есть еще одна коробка. Значит, мы должны положить и в нем окажется 9 коробок или короче 24=3*8+1. Задача № 8 В классе 37 учеников. Найдутся ли среди них четыре, которые родились в одном месяце. Решение: Ответ очевиден: да. 37>12*3. Здесь целесообразно несколько изменить условие задачи; а что будет, если в классе скажем не 37, а 38 или 42 и 48 учеников? Эти модификации условия дают ребятам возможность понять, что с увеличением числа учеников до 48 заключение не меняется, а если взять 49, то можно уже утверждать, что в одном месяце родились 5 учеников. Задача № 9 10 школьников на олимпиаде решили 35 задач, причем известно, что среди них есть школьники, решившие ровно одну задачу, школьники, решившие ровно две задачи, и школьники, решившие ровно три задачи. Докажите, что есть школьник, решивший не менее пяти задач.Решение: Из условий следует, что найдутся 7 школьников, решивших 35-6=29 заданий. Так как 29=4*7+1, то найдется школьник решивший не менее пяти задач. Задача № 10  Сосновый лес растет на участке, имеющим форму квадрата со стороной 1км. Зная, что весь этот лес состоит из 4500 деревьев диаметра 50см, доказать, что в лесу можно выбрать прямоугольную площадку 10м*20м, на которой не растет ни одного дерева. Решение: Разобьем участок на прямоугольные размеры 10м*20м и на полосы между ними, а именно: на одной стороне участка отложим 48 обрезков длиной в 20м каждый, причем между соседними отрезками оставим промежуток в 0,6м и два крайних отрезка по 5,9 м каждый. На второй стороне квадрата отложим 95 отрезков длины 10м каждый, разделенных промежутками длины больший 0,5м каждый. Тогда на участке окажется 95*48=4560 прямоугольников, разделенных полосами шириной, большей 1,5м. Так как деревьев всего 4500 и ни одно из деревьев не может попасть больше чем в один прямоугольник, то найдутся прямоугольники (даже не меньше 60), на которых нет деревьев. Задачи для самостоятельного решения (с ответом и рекомендациями).  1) Какое наибольшее число королей можно поставить на шахматной доске так, чтобы никаких два из них не били друг друга? Ответ : 32 короля 2) Какое наибольшее число пауков может ужиться на паутине, показанной на рисунке?  Паук терпит соседа на расстоянии, не меньшим 1,1м. Разбейте паутину на 4 клетки, в каждой из которых не может находиться более одного паука. 3) Докажите, что равносторонний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками. Каждый из меньших треугольников не может накрывать более одной вершины большого треугольника. 4)  В квадрат со стороной 1м бросили 51 точку. Докажите, что какие-то из них три можно накрыть квадратом со стороной 20см. Разобьем наш квадрат на 25 квадратов со стороной 20см. По обобщенному принципу Дирихле, в какой-то из них попадет по крайней мере три из 51 брошенной. Следствие: Если сумма n чисел равна S, то среди них есть как число, не больше S/n, так и число, не меньше S/n “. 5) 15 мальчиков собрали 100 орехов . Докажите, что какие-то двое из них собрали одинаковое число орехов.(105) 6) Докажите, что в любой компании из 5 человек есть двое, имеющие одинаковое число знакомых в этой компании.  Вариантов числа знакомых всего 5: от 0 до 4. Осталось заметить, что если у кого-то 4 знакомых, то ни у кого не может быть 0 знакомых. Зачетные задачи. 1)   Несколько футбольных команд проводят турнир в один круг. Докажите, что в любой момент турнира найдется две команды, сыгравшие к этому моменту одинаковое число матчей. 2)   а) Какое наибольшее число полей на доске 8*8 можно закрасить в черный цвет так. чтобы в любом уголке вида из трех полей было по крайней мере одно незакрашенное поле?       б) Какое наименьшее число полей на доске 8*8 можно закрасить в черный цвет так, чтобы в каждом уголке вида было по крайней мере одно черное поле? 3)  В алфавите языка племени Ни-Бум-Бум 22 согласных и 11 гласных, причем словом в этом языке не называется произвольное буквосочетание, в котором нет двух согласных и ни одна буква не использована дважды. Алфавит разбили на 6 непустых групп. Докажите, что из всех букв одной из групп можно составить слово.   Докажите, что в одной из групп разности между числом согласных и числом гласных не больше 1.                  Модуль №1. Комбинаторика. Задачи с решениями. Задача №1а) Сколькими способами  Дима сможет покрасить пять елок в серебристый, зеленый и синий цвета, если количество  краски у него неограниченно, а каждую елку он красит только в один цвет? б) У Димы есть пять шариков:  красный, зеленый, желтый, синий и золотой. Сколькими способами он сможет украсить ими пять елок, если на каждую требуется надеть ровно один шарик? в) А если можно надевать несколько шариков на одну елку (и все шарики должны быть использованы)? Решение:  а) Каждую из пяти елок можно покрасить в один из трех цветов, поэтому всего различных способов существует 3*3*3*3*3 = 35 = 243. б) На первую елку можно надеть любой из пяти шариков, на вторую елку — любой из оставшихся четырех, и так далее; всего получаем 5*4*3*2*1 = 120 способов. в) Каждый из шариков можно надеть на любую елку, поэтому в этом случае ответ — 55 = 3125. Ответ:  а) 243; б) 120; в) 3125. Задача № 2  В Стране Чудес есть четыре города: А, Б и В и Г. Из города А в город Б ведет 6 дорог, из города Б в город В - 4 дороги, из города А в город Г - две дороги, и из города Г в город В - тоже две дороги. Сколькими способами можно проехать от А до В? Решение: Выделим два случая: путь проходит через город Б или через город Г. В каждом из этих случаев легко сосчитать количество возможных маршрутов: в первом - 24, во втором - 4. Складывая, получаем общее количество маршрутов: 28.Ответ: 28 Задача №3  В компании у каждых двух людей ровно пять общих знакомых. Докажите, что количество пар знакомых делится на 3.Решение: Обозначим через Р количество пар знакомых людей, а через Т - количество троек попарно знакомых людей (т.е. количество троек людей, в которых каждые двое знакомы между собой). По условию у каждой пары знакомых людей есть ровно 5 общих знакомых, это означает, что каждая из Р пар знакомых людей входит ровно в 5 троек попарно знакомых людей. С другой стороны, в каждую из Т троек попарно знакомых людей входит ровно 3 пары знакомых людей. Сделанные замечания позволяют написать равенство: 5Р=3Т. Поскольку 3 и 5 - взаимно простые числа, Р делится на 3, что и требовалось доказать. Задача №4 Сколькими способами можно переставить числа от 1 до 100 так, чтобы соседние числа отличались не более, чем на 1?Решение: Понятно, что имеются хотя бы две перестановки со свойством, указанным в условии - 1, 2, ... , 99, 100 и 100, 99, ... , 2, 1. Покажем, что других перестановок, удовлетворяющих условию, нет. Число 1 может стоять только в начале и в конце. Действительно, если число 1 стоит не в начале и не в конце, то рядом с ним будут стоять два числа, большее из которых больше, чем 2, что противоречит условию. Допустим, что 1 стоит в начале. Посмотрим, где может стоять двойка. Если она стоит не после единицы, то рядом с двойкой будут стоять два числа, каждое из которых больше двойки. Большее из них будет больше 4, что снова противоречит к условию. Рассуждая таким же образом, получаем, что после единицы и двойки стоит тройка, и так далее однозначно восстанавливаем перестановку чисел - 1, 2, ... , 99, 100. Если же единица стоит в конце, то аналогично однозначно восстанавливается перестановка 100, 99, ... , 2, 1. Ответ: двумя. Задача № 5 У Сережи и у Лены есть несколько шоколадок, каждая весом не более 100 граммов. Как бы они не поделили эти шоколадки, у одного из них суммарный вес шоколадок не будет превосходить 100 граммов. Какой наибольший суммарный вес могут иметь все шоколадки? Решение: Пример шоколадок суммарным весом 300 граммов: 3 шоколадки по 100 граммов. Ясно, что пример удовлетворяет условию. Покажем, что суммарный вес шоколадок Лены и Сережи не больше 300 граммов. Отдадим вначале все шоколадки Сереже и будем отдавать по одной шоколадке Лене. Вначале у Сережи вес шоколадок больше, но наступит момент, когда у Лены шоколадки будут весить не меньше, чем у Сережи. Рассмотрим этот момент. Пусть в этот момент шоколадки Сережи весят A граммов (по условию A не превосходит 100 граммов), а шоколадки Лены - B граммов. Пусть последняя шоколадка, которую мы перекладывали, весила C граммов. До перекладывания суммарный вес шоколадок Лены был не больше 100 граммов. Итак, A не превосходит 100 граммов, B-C не превосходит 100 граммов, и также C не превосходит 100 граммов. Таким образом, суммарный вес всех шоколадок A+B+C не превосходит 3*100=300 граммов. Ответ: 300 граммов. Задача №6 Полоска 1*10 разбита на единичные квадраты. В квадраты записывают числа 1, 2, ..., 10. Сначала в один какой-нибудь квадрат пишут число 1, затем число 2 записывают в один из соседних квадратов, затем число 3 - в один из соседних с уже занятыми и т. д. (произвольными являются выбор первого квадрата и выбор соседа на каждом шагу). Сколькими способами это можно проделать?Решение: Пусть 1 стоит в i-м слева квадрате полосы. Расстановка остальных чисел однозначно определяется набором чисел, стоящих левее 1. Таких наборов ровно C9i – 1 (так как в каждом наборе фиксирован порядок чисел), а общее количество способов равно C90 + C91 + C92 + C93 + C94 + C95 + C96 + C97 + C98 + C99 = 29 = 512. Ответ: 512-ю способами Задачи для самостоятельного решения(с рекомендациями и ответами). Задача № 1  В одной из школ 20 раз проводился кружок по астрономии. На каждом занятии присутствовало ровно пять школьников, причём никакие два школьника не встречались на кружке более одного раза. Докажите, что всего на кружке побывало не менее 20 школьников. Подсказка:  Посмотрите на самого ''активного'' школьника.    Задача № 2 В столовой предложено на выбор 6 блюд. Каждый день Вася берет некоторый набор блюд (возможно, не берет ни одного блюда), причем этот набор блюд должен быть отличен от всех наборов, которые он брал в предыдущие дни. Какое наибольшее количество дней Вася сможет питаться по таким правилам и какое количество блюд он в среднем при этом будет съедать за день? Подсказка: Каждому набору блюд можно сопоставить противопо-ложный набор, состоящий в точности из тех блюд, которых нет в исходном наборе. Ответ: 64 дня, в среднем 3 блюда в день. Задача № 3 На собеседовании десяти человекам был предложен тест, состоящий из нескольких вопросов. Известно, что любые пять человек ответили вместе на все вопросы (т.е. на каждый вопрос хоть один из пяти дал правильный ответ), а любые четыре - нет. При каком минимальном количестве вопросов это могло быть? Подсказка: Для каждого вопроса количество людей, не ответивших на него, не больше четырех. Ответ: 210 Задача № 4 Сколькими способами можно составить комиссию из 3 человек, выбирая ее членов из 4 супружеских пар, но так, чтобы члены одной семьи не входили в комиссию одновременно? Подсказка: Выберите сначала семьи, а потом в каждой паре конкретного представителя. Ответ : 32 Задача № 5 У одного школьника есть 6 книг по математике, а у другого - 8. Сколькими способами они могут обменять три книги одного на три книги другого? Ответ: 1120 Задача № 6 В дискуссии приняли участие 15 депутатов. Каждый из них в своем выступлении раскритиковал ровно k депутатов из оставшихся 14 депутатов. При каком наименьшем k можно утверждать, что обязательно найдутся два депутата, которые раскритиковали друг друга? Подсказка : Изображайте депутатов точками, а тот факт, что депутат A раскритиковал депутата B обозначайте стрелкой, идущей от A к B.Ответ: 8 Задача № 7  Архитектор хочет расположить 7 высотных зданий так, чтобы, гуляя по городу, можно было увидеть их шпили в любом (циклическом) порядке. Удастся ли это ему? Подсказка: Чтобы сменить порядок следования шпилей, пешеход должен пройти через прямую линию, соединяющую некоторые два шпиля. Число возможных циклических порядков следования шпилей равно 6!=6*5*4*3*2*1. Ответ: нет. Задача № 8 Любую ли сумму из целого числа рублей, больше семи, можно уплатить без сдачи денежными купюрами по 3 и 5 р.? Почему?  Подсказка: Попробуйте рассмотреть три случая: а) сумма кратна 3; б) при делении на 3 сумма дает остаток 1; в) при делении на 3 сумма дает остаток 2.Ответ: Да, любую. Задачи для самостоятельно решения(с ответами). Задача №1 В кошельке лежит по 20 монет достоинством в 10, 15 и 20 копеек. Сколькими способами можно из этих 60 монет выбрать двадцать? Ответ: 231 Задача №2 Имеются 4 гири и двухчашечные весы без стрелки. Сколько всего различных по весу грузов можно точно взвесить этими гирями если а) гири можно класть только на одну чашку весов; б) гири можно класть на обе чашки весов? Ответ: 40 Задача №3 В почтовом отделении продаются открытки 10 видов. Сколькими способами можно купить в нем 8 различных открыток?Ответ: 45 Задача № 4  Даны 6 цифр: 0, 1, 2, 3, 4, 5. Найти сумму всех четырёхзначных чётных чисел, которые можно написать этими цифрами (одна и та же цифра в числе может повторяться). Ответ: 1 769 580. Задача № 5 Человек имеет 6 друзей и в течение 5 дней приглашает к себе в гости каких-то троих из них так, чтобы компания ни разу не повторялась. Сколькими способами он может это сделать? Ответ: C63(C63 - 1)(C63 - 2)(C63 - 3)(C63 - 4). Задача № 6 Сколькими способами 12 пятаков можно разложить по 5 различным кошелькам так, чтобы ни один кошелек не оказался пустым? Ответ: 330 Задача № 7 Сколькими способами 3 человека могут разделить между собой 6 одинаковых яблок, один апельсин, одну сливу и один мандарин? Ответ: 756. Задача № 8 Сколько существует 10-значных чисел, сумма цифр которых равна а) 2; б) 3; в) 4? Ответ : а) 10, б) 55, в) 220. Задача № 9 Сколькими способами можно представить 1000000 в виде произведения трех множителей, если произведения, отличающиеся порядком множителей, считаются различными? Ответ : 784 Задача № 10 Сколькими способами 12 пятаков можно разложить по 5 различным кошелькам так, чтобы ни один кошелек не оказался пустым?, Ответ: 330 Задача № 11 Сколькими способами можно разложить 7 монет различного достоинства по трем карманам? Ответ: 37. Задачи для зачета. Задача №1 а) Сколькими способами Дима  сможет покрасить пять елок в серебристый, зеленый и синий цвета, если количество краски у него неограниченно, а каждую елку он красит только в один цвет? б) У Димы есть пять шариков: красный, зеленый, желтый, синий и золотой. Сколькими способами он сможет украсить ими пять елок, если на каждую требуется надеть ровно один шарик? в) А если можно надевать несколько шариков на одну елку (и все шарики должны быть использованы)?    Задача № 2 Из 12 девушек и 10 юношей выбирают команду, состоящую из пяти человек. Сколькими способами можно выбрать эту команду так, чтобы в нее вошло не более трех юношей? Задача № 3 Сколько существует девятизначных чисел, сумма цифр которых четна? Задача № 4 В магазине ``Все для чая'' есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем? Задача № 5  В Стране Чудес есть три города: А, Б и В. Из города А в город Б ведет 6 дорог, а из города Б в город В - 4 дороги. Сколькими способами можно проехать от А до В? Задача № 6  В Стране Чудес есть четыре города: А, Б и В и Г. Из города А в город Б ведет 6 дорог, из города Б в город В - 4 дороги, из города А в город Г - две дороги, и из города Г в город В - тоже две дороги. Сколькими способами можно проехать от А до В? Задача № 7 В магазине ``Все для чая'' по-прежнему продается 5 чашек, 3 блюдца и 4 чайные ложки. Сколькими способами можно купить два предмета с разными названиями? Задача № 8 Назовем натуральное число ``симпатичным'' , если в его записи встречаются только нечетные цифры. Сколько существует 4-значных ``симпатичных'' чисел? Задача № 9 На доске написаны 7 существительных, 5 глаголов и 2 прилагательных. Для предложения нужно выбрать по одному слову каждой из этих частей речи. Сколькими способами это можно сделать? Задача №10 У двух начинающих коллекционеров по 20 марок и по 10 значков. Честным обменом называется обмен одной марки на одну марку или одного значка на один значок. Сколькими способами коллекционеры могут осуществить честный обмен? Задача № 11 Надо послать 6 срочных писем. Сколькими способами это можно сделать, если для передачи писем можно использовать трех курьеров и каждое письмо можно дать любому из курьеров? Задача № 12 Чемпионат России по шахматам проводится в один круг. Сколько играется партий, если участвуют 18 шахматистов? Задача № 13 Пешеход обошёл шесть улиц одного города, пройдя каждую ровно два раза, но не смог обойти их, пройдя каждую лишь раз. Могло ли это быть? Задача № 14 В корзине лежат 30 грибов — рыжиков и груздей. Известно, что среди любых 12 грибов имеется хотя бы один рыжик, а среди любых 20 грибов — хотя бы один груздь. Сколько рыжиков и сколько груздей в корзине? Модуль 4.Признаки делимости. Задачи с решениями:             Задача №1 Доказать, что число  делится на 33. Решение:   ,         на 33. Используется   разложение на множители – эта идея присутствует во многих примерах. Задача № 2 Числа 90 и 100 разделили на одно и то же  число. в первом случае остаток 4, а во  втором 18. На какое число делили? Решение:  На искомый делитель делятся 100-4=96 и 100-18=72, значит этот делитель общий для чисел 96 и 72. Из общих делителей  выбираются которые больше 18. Ответ:    24. Задача № 3     Доказать, что 1989·1990·1991·1992 + 1  есть полный квадрат.            Решение:                         Задача № 4    Существует ли такое двузначное число, которое при делении на сумму квадратов его цифр дает в остатке 6, в частном 2, а при делении на произведение цифр дает в частном 4, а в остатке 6. Решение:   1 способ               ;                    2 способ:  перебором. Если двузначное число при делении на произведение дает в частном 4. а в остатке 6, то оно четно, произведение цифр четно и при делении дает 8  ;  14; 22; 30;…   уже 22 обнаруживаем выполнение задачи. Значит,  такое число существует. Доказательств о единственности не требуется, так как вопрос поставлен существует ли? Ответ: существует Задача № 5 Если к четырёхзначному числу приписать слева цифру 2 или справа цифру 4, то в обоих случаях получится точный квадрат. Найти это число. Решение:             Пусть , а точные квадраты через  и , тогда выполняются равенства 20000+ x =                        10x + 4 =  из второго равенства следует, что  - чётное число и, значит, , так что число х – тоже чётное, но тогда из первого равенства получаем, что - чётное, т.е. k=2m, а значит х делится  на 4, т.е. х=4у 5000+у=;                          10у+1= Если n не на 3, то  и тогда у на 3(из второго), а тогда из первого равенства следует, что  при делении на 3 даёт остаток 2, что невозможно. Поэтому   на 3,  откуда у =9z-1,  = 5000+у=9t+4, m=9u 2 k=2m=18u 4. Так как 20000<<30000, то 142, и из чисел от 142 до 173 остаётся найти числа, дающие при делении на 18 остаток 4 или 14, т.е. 148,166 и 158. Непосредственная проверка показывает, что условию задачи удовлетворяет только значение k=148, и искомое число 1904. Ответ: 1904 Задача № 6  Произведение нескольких последовательных нечетных чисел оканчивается цифрой 9. Сколько в этом произведении множителей? Решение: В таком произведении может быть либо 2, либо 4 множителя. Например, 9  или   . Если множителей больше 4, то один из них, а следовательно и все произведение, оканчивается цифрой 5. Произведение же трех последовательных нечетных чисел не оканчивается цифрой 9. ….1……3…..5;       7…..9….11 Ответ: 2 или 4 Задача № 7   Какими двумя цифрами оканчивается двадцатая степень четного числа? Решение:          Четное число оканчивается   0, 2, 4, 6, 8   ,  поэтому его можно представить в одном из следующих видов      ;   ;   .  - очевидно оканчивается двумя нулями.                    оканчивается     76   ,   тоже оканчивается числом 76. Итак, две последние цифры двадцатой степени четного числа   00  и   76. Ответ: 00 или 76 Задача № 8 Сколько существует чисел, состоящих из 2n  цифр, у которых произведение цифр, стоящих на четных местах, делится на  3  , а произведение цифр, стоящих на нечетных местах,  делится на   2.      Решение. Среди цифр, стоящих на четных местах, должна быть хотя бы одна из цифр 0, 3, 6, 9  , а на нечетных – одна из четных цифр. Всего на четных местах можно расставить цифры  способами, причем   из них не будут удовлетворять условию задачи, т.к. 6 цифр (1, 2, 4, 5, 7, 8 ) не делятся на 3. Всего на нечетных местах можно расставить цифры  способами ( на первом месте нельзя ставить 0 ), причем  из них не будут удовлетворять условию задачи, так как 5 цифр (1; 3; 5; 7; 9) нечетные. существует   чисел, удовлетворяющих данному условию. Задачи с ответами:  1)Сколько имеется четырехзначных чисел, которые делятся на 35, а две средние цифры у                  них 2  и  4.  Назовите их.   Ответ:  два числа  ( 2240  и 7245) 2 )   Могут ли числа   и    одновременно делиться на 49?      Ответ:. одновременно делиться на 49 не могут. 4)        Можно ли из цифр от 1 до 6 составить шестизначное число с  различными цифрами, делящиеся на 11.Ответ: числа с требуемыми свойствами не существует.        5) Сколько существует трехзначных чисел, у которых каждая цифра отлична от 0 и делится на разность двух других цифр?          Ответ :  78 чисел