Олимпиады по обществознанию

РЕШЕНИЕ ОЛИМПИАДНЫХ ЗАДАЧ МЕТОДАМИ ДИСКРЕТНОЙ

М.И. Мухаметова, студент

Г.Х. Воистинова, канд. пед. наук, доцент

Стерлитамакский филиал Уфимского университета науки и технологий (Россия, г. Стерлитамак)

Аннотация

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

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

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

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

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

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

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

Графический метод

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

Граф — это геометрическая фигура, состоящая из точек (вершины графа) и линий, их соединяющих (рёбра графа). Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выходит четное количество ребер — четными.

Решая задачу про кенигсбергские мосты, Эйлер установил свойства графа:

Решение методом графов

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

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

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

4. Число нечетных вершин графа всегда четное.

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

Выделяют несколько типов задач, решаемых методом графов:

1. Задачи на вычерчивание фигур одним росчерком.
2. Задачи о мостах.
3. Задачи о правильном раскрашивании карт.
4. Задачи о колодцах.
5. Задачи на построение уникурсальных графов.
6. Задачи комбинаторного характера.

Решение задач методом графов

Эйлеровы графы

Задача 1: Начертить одним росчерком следующие фигуры:

Логические задачи

Задача 2: В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой.

Решение: В данной задаче одна группа — игроки. Поэтому устанавливаем отношения между игроками.

Посчитав количество ребер, ответим на вопрос, сколько игр сыграно к настоящему моменту. Ответ: 7 игр.

Построим граф для непроведенных игр, на этом рисунке граф имеет 8 ребер, следовательно, осталось провести 8 игр.

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

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

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

Ответ: Пистолет — в синей, сумочка — в красной, кукла — в зеленой, машинка — в желтой коробках.

Комбинаторика

Основной вопрос комбинаторики -сколько?, основная задача — подсчёт числа элементов конечного множества.

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

Выписывание комбинаций

2. Выписываем комбинации в алфавитном порядке (при обозначении буквами) или по возрастанию чисел (при обозначении цифрами). При таком переборе ни один вариант не ускользнёт от нас и, с другой стороны, будет исключена возможность повторения вариантов.

Задача 4

Задача 4. Маша собирается съесть яблоко, сливу и мандарин, но пока не решила, в какой последовательности. Сколькими способами Маша может выбрать эту последовательность?

Решение: Обозначаем буквами: Я — яблоко, С — слива, М — мандарин. Тогда, например, СМЯ — это вариант, когда Маша сначала съест сливу, потом — мандарин, потом — яблоко. Выпишем варианты в алфавитном порядке:

• МСЯ,
• МЯС,
• СМЯ,
• СЯМ,
• ЯМС,
• ЯСМ.

Получилось 6 вариантов.

Решение

Решение: Пронумеруем гостей цифрами 1, 2, 3, 4 и так же пронумеруем их шляпы. Считаем, что шляпа с данным номером принадлежит гостю с этим же номером (то есть, например, шляпа 2 принадлежит гостю 2). Тогда каждый вариант получения шляп обозначается четырёхзначным числом, составленным из цифр 1, 2, 3 и 4, в котором номер позиции цифры есть номер гостя, а сама цифра есть номер полученной им шляпы (номера позиций будем считать слева направо).

Например, комбинация 4132 означает, что первый гость получил четвёртую шляпу, второй — первую, третий — третью, а четвёртый — вторую. Такой вариант не годится по условию, поскольку третий получил свою шляпу. Теперь понятно, что нужно сделать — выписать по возрастанию все четырехзначные числа, содержащие по одной цифре 1, 2, 3 и 4, такие, что никакая цифра не стоит на позиции со своим номером.

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

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

Рис. 6

Комбинации шляп и гостей

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

Использование дискретной математики

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

Дискретной математики используются при

Решение олимпиадных задач методами дискретной математики

М.И. Мухаметова, студент

Г.Х. Войстинова, кандидат педагогических наук, доцент

Стерлитамакский филиал Уфимского университета науки и технологий (Россия, Стерлитамак)

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

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

Олимпиады по обществознанию

Подготовка к олимпиадам по обществознанию

• Процент поступления в топ 5 вузов России
• Дипломы Всероссийской олимпиады школьников и перечневых олимпиад

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

• Ответить на вопросы и проверить домашнее задание
• Проходить необходимую теорию в своем темпе
• Занятия в Zoom по практике
• Разбор заданий олимпиад и их решения
• Задания реальных олимпиад для отработки навыков
• Проверка полученных знаний
• Быстрый ответ и проверка домашнего задания

Практика — практика — практика!

Убедись во всем сам: получи скрипт и конспект, просмотри лекцию, получи ДЗ и пример проверки, а также ответы на интересующие тебя вопросы

Обществознание: https://vk.com/app5898182_-205898273#s=2028624История: https://vk.com/app5898182_-217507675#s=2077247Английский: https://vk.com/app5898182_-218691412#s=2156478

Студентка политфака НИУ ВШЭ

Подготовила 1 абсолютного победителя

Призер ВСОШ по обществознанию

Главный тренер МК по олимп. обществознанию

Более 140 призеров перечневых олимпиад

Выпустила более 30 учеников

Студентка факультета права НИУ ВШЭ

Призер множества перечневых олимпиад

Народный титул «Мама куратор»

Главный куратор МК, тренер МК по праву и обществознанию

Студентка соцфака НИУ ВШЭ

Тренер МК по обществознанию

Студент факультета МО НИУ ВШЭ

Один из первых преподавателей МК

Нажимая кнопку вы даете согласие на обработку персональных данных

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

Результаты осенней олимпиады 2023 категория 1 курс

Результаты осенней олимпиады 2023 категория 2+ курс

Также поздравляем Федорова Тимофея, Нифонтова Даниила, Штанникова Алексея, Бышкова Олега, которые выступали вне конкурса, но также добились высоких результатов.

Условия олимпиады для 1 курса

Условия олимпиады для 2+ курса

Открытая студенческая олимпиада ФКН по математике проводится для студентов высших учебных заведений 1-4 курсов.

Для студентов НИУ ВШЭ результаты олимпиады являются одним из критериев отбора в сборную университета на международные и межвузовские олимпиады по математике (олимпиада им. Войтеха Ярника, IMC и др.)