Математическаяэстафета для 7-8 классов для 7-8 классов «Графы в решении логических задач» Математическаяэстафета для 7-8 классов для 7-8 классов «Графы в решении логических задач» 23 октября школа 870

учащиеся 7- 8 классов школ Южного округа г. Москвы 420; 508; 581; 870; и 8 классы соревнуются каждый в своей категории Члены жюри: учителя и старшеклассники школ – участников олимпиады ЗАПОЛНИТЬ ЛИСТЫ РЕГИСТРАЦИИ

15 минут объяснение метода объяснение метода 1 задача 10+5 минут 2 задача 10+5 минут 3 задача 10+5 минут С учетом обсуждения решения 15 минут подведение итогов, награждение победителей и анонс предстоящих игр

15 минут объяснение метода объяснение метода В математике и информатике Граф это совокупность объектов со связями между ними. Родоначальником теории графов принято считать математика Леонарда Эйлера. Вот, что он писал итальянскому математику и инженеру Маринони: "Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно…..» ( ).

Известно, что в настоящий момент: 1) Ваня сыграл шесть партий; 2) Толя сыграл пять партий; 3) Леша и Дима сыграли по три партии; 4) Семен и Илья сыграли по две партии; 5) Женя сыграл одну партию. Условие задачи 1 Требуется определить: с кем сыграл Леша. Шахматный турнир проводится по круговой системе, при которой каждый участник встречается с каждым ровно один раз, участвуют семь школьников. Надо создать решение-аппликацию из материалов, которые вам будут выданы

Изобразим участников турнира точками Для решения задачи будем использовать геометрическое представление графа Эти точки называются вершинами графа Известно, что в настоящий момент: 1) Ваня сыграл шесть партий; 2) Толя сыграл пять партий; 3) Леша и Дима сыграли по три партии; 4) Семен и Илья сыграли по две партии; 5) Женя сыграл одну партию. С кем сыграл Леша? Число в скобках называют степенью вершины, оно показывает сколько ребер выходит из данной вершины Для каждой точки укажем ее имя (по первой букве имени игрока) и количество партий, сыгранные этим игроком В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1)

Будем строить ребра графа с учетом степеней вершин Начать построение ребер следует с вершины В, так как это единственная вершина, которая соединяется со всеми другими вершинами графа Известно, что в настоящий момент: 1) Ваня сыграл шесть партий; 2) Толя сыграл пять партий; 3) Леша и Дима сыграли по три партии; 4) Семен и Илья сыграли по две партии; 5) Женя сыграл одну партию. С кем сыграл Леша? В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Первые выводы: Для вершин В и Ж построены все возможные ребра

Теперь однозначно определяются ребра вершины Т. С учетом ребра ВТ надо построить четыре ребра Известно, что в настоящий момент: 1) Ваня сыграл шесть партий; 2) Толя сыграл пять партий; 3) Леша и Дима сыграли по три партии; 4) Семен и Илья сыграли по две партии; 5) Женя сыграл одну партию. С кем сыграл Леша? В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Новые выводы: Все возможные ребра теперь построены для вершин Ж, В, Т, и для вершин С и И

Теперь становится очевидным, каким должно быть недостающее ребро. Оно должно соединить вершины Л и Д Известно, что в настоящий момент: 1) Ваня сыграл шесть партий; 2) Толя сыграл пять партий; 3) Леша и Дима сыграли по три партии; 4) Семен и Илья сыграли по две партии; 5) Женя сыграл одну партию. С кем сыграл Леша? В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Последний вывод Леша играл с Толей, Ваней и Димой Посмотрим и оценим вместе решение-аппликацию…

Условие задачи 2 В шахматном турнире по круговой системе, в котором участвуют пять школьников, сыграно шесть партий. Больше всего встреч к настоящему моменту провели Ваня и Миша – по три. Какое число партий сыграл участник, проведший наименьшее число встреч?

В данной задаче однозначно построить граф нельзя В аня (3) М иша (3) 1 (?) Построим граф к данной задаче 2 (?) 3 (?) В шахматном турнире по круговой системе, в котором участвуют пять школьников, сыграно шесть партий. Больше всего встреч к настоящему моменту провели Ваня и Миша – по три. Какое число партий сыграл участник, проведший наименьшее число встреч?

Ваня и Миша не играли друг с другом В аня (3) М иша (3) 1 (?) 1 случай 2 (?) 3 (?) В этом случае каждый из остальных участников провел по две встречи В шахматном турнире по круговой системе, в котором участвуют пять школьников, сыграно шесть партий. Больше всего встреч к настоящему моменту провели Ваня и Миша – по три. Какое число партий сыграл участник, проведший наименьшее число встреч?

Ваня и Миша сыграли друг с другом, В аня (3) М иша (3) 1 (?) 2 (?) 3 (?) Этот случай невозможен, поскольку проведя шестое ребро, но есть участник, не встречавшийся ни с Ваней,ни с Мишей мы получим противоречие с условием задачи, так как появится еще один участник, сыгравший 3 партии В шахматном турнире по круговой системе, в котором участвуют пять школьников, сыграно шесть партий. Больше всего встреч к настоящему моменту провели Ваня и Миша – по три. Какое число партий сыграл участник, проведший наименьшее число встреч? 2 случай

Ваня и Миша сыграли друг с другом, В аня (3) М иша (3) 1 (?) 2 (?) 3 (?) Есть только одна возможность провести шестое ребро, не нарушая условия задачи при этом каждый участник, встретился либо с Ваней, либо с Мишей, либо с обоими вместе В этом случае каждый из остальных участников провел по две встречи В шахматном турнире по круговой системе, в котором участвуют пять школьников, сыграно шесть партий. Больше всего встреч к настоящему моменту провели Ваня и Миша – по три. Какое число партий сыграл участник, проведший наименьшее число встреч? 3 случай

В аня (3) М иша (3) 1 (2) 2 (2)3 (2) Наименьшее число встреч у участников 1,2,3 по две встречи Требовалось определить: Какое число партий сыграл участник, проведший наименьшее число встреч? 1 случай 2 случай 3 случай В аня (3) М иша (3) 12 3 Шестое ребро ? Случай невозможен В аня (3) М иша (3) 1 (2) 2 (2) 3 (2) Наименьшее число встреч у участников 1,2,3 по две встречи

2 этап. Решение задач. 1. Сейчас зал превратится в множество беговых дорожек: СТАРТ ( стул) ---- ФИНИШ (стол) 2. У каждой команды есть свой член жюри, который следит за соблюдением правил эстафеты 3. Каждая команда получит последовательно 3 карточки с условиями задач, для которых надо сделать решение-аппликацию. 4. На планшете можно сделать черновое решение, но его нельзя переносить на финишный стол. 5. Участники команды должны распределить между собой этапы эстафеты: (1) наклеить на ватман круги – вершины графа ( 2 участника) (2) подписать названия и степени вершин графа ( 1 участник) (3) наклеить полоски серпантина – ребра графа ( 2 участника) (4) сделать вывод и записать ответ ( 1 участник) На каждом столе есть ВАТМАН, МАРКЕР и КЛЕЙ, КРУГИ и СЕРПАНТИН, карточка с условием задачи (дополнительная) Время выполнения аппликации 10 минут, затем жюри собирает и оценивает решение, а для участников проходит показ решения задачи 1. Аналогично будет проходить решение задачи 2

В шахматном турнире по круговой системе участвуют 5 школьников. Миша и Саша провели по 4 встречи, Костя и Женя – по 3, Ваня – 2. С кем сыграл Ваня? В аня (2) М иша (4) С аша (4) К остя (3) Ж еня (3) ОТВЕТ. Ваня сыграл с Мишей и Сашей 6 баллов

2 этап. Решение задач. 1. Сейчас зал превратится в множество беговых дорожек: СТАРТ ( стул) ---- ФИНИШ (стол) 2. У каждой команды есть свой член жюри, который следит за соблюдением правил эстафеты 3. Каждая команда получит последовательно 3 карточки с условиями задач, для которых надо сделать решение-аппликацию. 4. На планшете можно сделать черновое решение, но его нельзя переносить на финишный стол. 5. Участники команды должны распределить между собой этапы эстафеты: (1) наклеить на ватман круги – вершины графа ( 2 участника) (2) подписать названия и степени вершин графа ( 1 участник) (3) наклеить полоски серпантина – ребра графа ( 2 участника) (4) сделать вывод и записать ответ ( 1 участник) На каждом столе есть ВАТМАН, МАРКЕР и КЛЕЙ, КРУГИ и СЕРПАНТИН, карточка с условием задачи (дополнительная) Время выполнения аппликации 10 минут, затем жюри собирает и оценивает решение, а для участников проходит показ решения задачи 1. Аналогично будет проходить решение задачи 2

В шахматном турнире по круговой системе участвуют 6 школьников. Известно, что Кеша сыграл 5 партий, Толя – 4, Семен – 2, Вася -1. Сколько встреч провели еще 2 участника: Андрей и Олег? К еша (5) А ндрей (?) С емен (2) В ася (1) Т оля (4) ОТВЕТ. 2 встречи, если Олег и Андрей НЕ играли друг с другом; 3 встречи, если совместный матч был балла О лег (?)

2 этап. Решение задач. 1. Сейчас зал превратится в множество беговых дорожек: СТАРТ ( стул) ---- ФИНИШ (стол) 2. У каждой команды есть свой член жюри, который следит за соблюдением правил эстафеты 3. Каждая команда получит последовательно 3 карточки с условиями задач, для которых надо сделать решение-аппликацию. 4. На планшете можно сделать черновое решение, но его нельзя переносить на финишный стол. 5. Участники команды должны распределить между собой этапы эстафеты: (1) наклеить на ватман круги – вершины графа ( 2 участника) (2) подписать названия и степени вершин графа ( 1 участник) (3) наклеить полоски серпантина – ребра графа ( 2 участника) (4) сделать вывод и записать ответ ( 1 участник) На каждом столе есть ВАТМАН, МАРКЕР и КЛЕЙ, КРУГИ и СЕРПАНТИН, карточка с условием задачи (дополнительная) Время выполнения аппликации 10 минут, затем жюри собирает и оценивает решение, а для участников проходит показ решения задачи 1. Аналогично будет проходить решение задачи 2

В шахматном турнире по круговой системе участвуют 5 школьников и все сыграли хотя бы по одной встрече, только Ваня и Леша провели одинаковое число встреч. Сколько встреч провели Ваня и Леша? В аня (*) 1 участник (?) Л еша (*) Объясните, почему ваш граф единственно возможный, то есть почему других вариантов быть не может. 2 участник (?) 3 участник (?) Ваня и Леша сыграли по 1 партии 1 случай

В шахматном турнире по круговой системе участвуют 5 школьников и все сыграли хотя бы по одной встрече, только Ваня и Леша провели одинаковое число встреч. Сколько встреч провели Ваня и Леша? В аня (*) 1 участник (?) Л еша (*) Объясните, почему ваш граф единственно возможный, то есть почему других вариантов быть не может. 2 участник (?) 3 участник (?) Ваня и Леша сыграли по 2 партии 2 случай

В шахматном турнире по круговой системе участвуют 5 школьников и все сыграли хотя бы по одной встрече, только Ваня и Леша провели одинаковое число встреч. Сколько встреч провели Ваня и Леша? В аня (*) 1 участник (?) Л еша (*) Объясните, почему ваш граф единственно возможный, то есть почему других вариантов быть не может. 2 участник (?) 3 участник (?) Ваня и Леша сыграли по 3 партии 3 случай

В шахматном турнире по круговой системе участвуют 5 школьников и все сыграли хотя бы по одной встрече, только Ваня и Леша провели одинаковое число встреч. Сколько встреч провели Ваня и Леша? В аня (*) 1 участник (?) Л еша (*) Объясните, почему ваш граф единственно возможный, то есть почему других вариантов быть не может. 2 участник (?) 3 участник (?) Ваня и Леша сыграли по 4 партии Последний 4 случай

В шахматном турнире по круговой системе участвуют 5 школьников и все сыграли хотя бы по одной встрече, только Ваня и Леша провели одинаковое число встреч. Сколько встреч провели Ваня и Леша? В аня (*) 1 участник (?) Л еша (*) Объясните, почему ваш граф единственно возможный, то есть почему других вариантов быть не может. 2 участник (?) 3 участник (?) Ваня и Леша сыграли по 2 партии 2 случай Нарисовать картинки, объясняющие невозможность трех остальных случаев 6+6 баллов

СКРИН конференция для 6-10 классов для 6-10 классов Защита исследовательских проектов СКРИН конференция для 6-10 классов для 6-10 классов Защита исследовательских проектов 27 ноября Школа 420