Методические рекомендации для проведения курса «Комбинаторика» (стр. 10 )

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

ГЛАВА IV. Олимпиадные задачи из области комбинаторики.

Главная цель внеклассных занятий по математике – углубление знаний, получаемые школьниками на уроках, повышение интереса к предмету. Хорошо зарекомендовали себя такие формы внеклассной работы как, кружки, школы юных математиков, летние и  заочные  математические школы и т. д.В них сложились три основных направления: научно – популяризаторское (лекции, беседы, доклады, конференции); игровое (театрализованные представления, вечера, КВН и другие мероприятия); соревновательное (смотр знаний, математические бои, олимпиады).[36]

Олимпиады наиболее распространенная и яркая форма внеклассной работы с одаренными детьми.

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

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

Для успешного проведения олимпиад необходимо выполнение в первую очередь следующих условий:[34]

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

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

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

Школьные олимпиады проводятся с V – XI класс.

Примерные задания по комбинаторике для проведения олимпиад в V – VII классах.

Задача 1: Грани куба с ребром 1 метр выкрасили и разрезали куб на кубики с ребром 1мм. Сколько кубиков имеют: а) 3, б) 2, в) 1, г) ни одной крашеной грани?[36]

Решение: а) 8; б) 998 * 12 = 11976; в) 6 * 998 = 5976024; г) 998 = 994011992.

Задача 2: Грани прямоугольного параллелепипеда покрасили и разрезали его на 24 единичных кубика. У 12 кубиков покрашено по 2 грани. Каковы размеры параллелепипеда?[34]

Ответ: 2 * 3 * 4

Задача 3: В тетрадях нарисована полоска 1 Ч 6. Сколькими способами она может быть окрашена в 6 цветов?[34]

Решение: 6! = 720.

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

Решение: Рассмотрим развертку куба (рис.4.1)

  Рис. 4.1

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

Задача 5: В мастерской имеется 10 различных станков. Известно, что каждый из 10 рабочих этой мастерской умеет работать только на двух станках и на каждом станке, умеют работать только два рабочих. Можно ли расставить рабочих у станков так, чтобы каждый стоял у станка, на котором умеет работать?[24]

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

  Рис. 4.2

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

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

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

Таким образом, утверждение остается верным.

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

Задача 6: (для 9 кл.) В сенате 30 сенаторов. Каждые два из них либо дружат, либо враждуют. Каждый сенатор враждует ровно с 6 другими. Каждые три сенатора образуют комиссию. Найти общее число таких комиссий, в которых либо все три члена попарно дружат, либо все трое попарно враждуют?[31]

Решение: Известно, что 30 сенаторов образуют  комиссий по 3 члена. Если каждый сенатор составит список, включающий его комиссий, в которых у него оба других члена одновременно или друзья, или враги, то получится 30 списков  по  комиссий, а всего 30* 268 = 8040 комиссий (с повторениями). Обозначив число  интересующих нас комиссий через х, заметим, что каждая из них окажется в трех списках, а каждая из остальных – в одном, поэтому

3х + (4060 – х) = 8040, откуда х = 1990.  Следовательно, всего 1990 комиссий.

Задача 7: (для 10 кл.) Сколько различных пятизначных чисел, делящихся на 4, можно составить из цифр 1, 2, 3, 5?[34]

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

Ответ: 192 различных числа, делящихся на 4, можно составить из данных цифр.

Задача 8: (для 11 кл.) В цветочном городе n площадей и m улиц (m > n +1). Каждая улица соединяет две площади и не проходит через другие площади. По существующей в городе традиции улица может называться либо Синей, либо Красной. Ежегодно в городе происходит переименование, выбирается площадь, и переименовываются все выходящие из нее улицы. Докажите, что вначале можно назвать так, что переименованиями нельзя добиться одинаковых названий у всех улиц города.[2]

Решение: Заметим, что существует всего способов присвоения названий улицам. Для краткости будем их называть раскрасками. Оценим количество раскрасок, которые можно получить с помощью переименований из раскраски, для которой все улицы Красные. Раскраска, полученная после серии переименований,  не зависит от порядка, в котором эти переименования были произведены. Кроме того, если дважды переименовать улицы, выходящие из одной и той же площади, то все улицы сохранят свои прежние названия. Наконец, если провести n переименований, по одному для каждой площади, то каждая улица будет переименована 2 раза и, следовательно, сохранит свое название. Значит, мы можем получить не более 2ⁿ - 1 раскрасок.

Аналогично, если бы все улицы  были Синими, то с помощью переименований можно получить не более  2(2ⁿ -1)< 2ⁿ  ≤  раскрасок; следовательно, какую-то раскраску нельзя получить с помощью переименований из раскраски, для которой все улицы названы одинаково.

Задача 9: В каждой вершине правильного 100-угольника поставлены фишки: 76 красных и 24 синих. Доказать, что найдутся 4 красные фишки, образующие квадрат. [36]

Решение: Фишки образуют 25 квадратов. Синие фишки являются вершинами не более 24-х квадратов, поэтому хотя бы один квадрат будет красным.

Задача 10: Каждая клетка таблицы 1995  Ч 1995 покрашена в один из двух цветов. За один ход разрешается все клетки любой строки (или столбца)  перекрасить в тот цвет, который в ней чаще встречается. Можно ли перекрасить всю таблицу в один цвет?[1]

Решение: Сначала  перекрасим таблицу в полоску: каждую строку в тот цвет, который в ней  чаще встречается. Затем также перекрасим столбцы. Следовательно, можно перекрасить всю таблицу в один цвет.

Задача 11: (для 11кл.) «Король – самоубийца». На шахматной доске размером 1000Ч1000 стоит черный король и 499 белых ладей. Докажите, что при произвольном начальном расположении фигур король может стать под удар белой ладьи, как бы не играли белые. (Ходы делаются так же, как в обычных шахматах).[34]

Решение: Пошлем короля сначала в левый нижний угол доски и затем по диагонали вправо-вверх. Можно считать, что после первого хода короля по диагонали и ответа белых, три нижние горизонтали и три левые вертикали свободны от ладей, иначе следующим ходом король может стать под удар ладьи  (рис.4.3,а). Таким образом, все ладьи находятся выше и правее короля. Рассмотрим момент, когда король сделал еще 997 ходов по диагонали (рис.4.3,б) и белые ответили на его последний ход. В этот момент все ладьи должны быть левее и ниже короля. При этом каждая ладья должна была сделать два хода: поменять вертикаль и горизонталь до того, как на них появится король. Но ладей 499, и они за 997 ходов не успеют передвинуться.