Задачи // Upstairs

Александр ШЕНЬ о Теории Множеств и Алгоритмах. Воскресенье, 28 апреля

✅ Диагональные конструкции: Кантор, Бэр, теория вычислимости

Знаменитая "диагональная конструкция" придумана Кантором для доказательства того, что нельзя пронумеровать натуральными числами все последовательности нулей и единиц. Она может быть пересказана так: "на n-м шаге мы гарантируем выполнение n-го требования и так строим объект, удовлетворяющий всем требованиям".

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

Задача для разогрева: можно ли отметить точки на прямой так, чтобы среди расстояний между ними по одному разу встречались все натуральные числа?

⭐️ Александр Шень (CNRS, ИППИ РАН) — специалист по дискретной математике и информатике, автор книг, популяризатор.

📍 Начало в 18:00 МСК/15:00 GMT

❗️Если вы школьник/студент и хотите стать контрольным слушателем, напишите мне @d1_d57.

📌 Ссылка на Zoom стандартная.

✉️ КАНАЛ СЕМИНАРА

#открытые_лекции #анонс

Вступительная работа в 8 класс 179 школы

16 марта 2024

Аналогичные работы прошлых лет+устные:
2023:
https://t.me/matolimp/2477
https://t.me/matolimp/2470
https://t.me/matolimp/2427
https://t.me/matolimp/2500

2022:
https://t.me/matolimp/1482
https://t.me/matolimp/1445

2021:
https://t.me/matolimp/706
https://t.me/matolimp/674
https://t.me/matolimp/673
https://t.me/matolimp/637

#в8класс #мо179 #школа179

@matolimp

Задача с тремя кругами.

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

#Математическая_разминка

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

https://www.youtube.com/watch?v=aDsdKtvuWjA записали видео с демонстрацией дефектов интерфейса

Опрос про кружки 5 класса.

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

Но пока вот у меня такой промежуточный итог.

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

1 Алгебра (Алгебраическая запись чисел, равенств и неравенств)
2 Алгебра (Делимость и остатки)
3 Алгебра (Последняя цифра)
4 Алгебра (Составить уравнение)
5 Арифметика (Время и календарь)
6 Арифметика (Задачи про возраст)
7 Арифметика (Задачи про движение, стоимости, совместную работу)
8 Арифметика (Математические ребусы)
9 Геометрия (Конструктивы, разрезания и пр.)
10 Геометрия (Окружности)
11 Геометрия (Периметры площади объемы и поверхности)
12 Геометрия (Разные задачи на клетчатой бумаге)
13 Геометрия (Расстояния)
14 Геометрия (Точки на прямой)
15 Идеи и методы (Анализ с конца)
16 Идеи и методы (Выкинуть ненужное)
17 Идеи и методы (Диаграммы Эйлера-Венна)
18 Идеи и методы (Инварианты)
19 Идеи и методы (Метод подбора)
20 Идеи и методы (Обратный ход)
21 Идеи и методы (Организация перебора)
22 Идеи и методы (Оценка + пример)
23 Идеи и методы (Плюс-минус 1)
24 Идеи и методы (Подсчет двумя способами)
25 Идеи и методы (Поиск примеров и контрпримеров)
26 Идеи и методы (Раскраска - шахматная и другие)
27 Идеи и методы (Рассуждения от противного)
28 Идеи и методы (Чётность и чередование)
29 Логика (Выводы из набора утверждений)
30 Логика (Задачи на логический перебор)
31 Логика (Построения отрицаний)
32 Логика (Рыцари и лжецы)
33 Прочее (Алгоритмические задачи - взвешивания, переливания, переправы)
34 Прочее (Графы)
35 Прочее (Игры. Выигрышные позиции)
36 Прочее (Мой брат-моя сестра)
37 Прочее (Негеометрические конструкции)
38 Прочее (Основы комбинаторики без специальных формул)

Часть 2. Темы "только для тех, кто раньше не учился в кружках"

1 Алгоритмы (переправы, переливания, взвешивания)
2 Анализ с конца
3 Арифметика (Головы и ноги)
4 Арифметика (прием Гаусса для сложения)
5 Арифметика (Числовые неравенства)
6 Геометрия на прямой
7 Головоломки
8 Количество мостов-дверей при проходе по маршруту
9 Круги Эйлера
10 Логика (логические квадраты)
11 Логика (Рыцари и лжецы)
12 Мой-брат-сестра
13 Перебор случаев
14 Плюс-минус один
15 Промежутки
16 Простая комбинаторика (на уровне "выпиши все такое" без подсчетов)
17 Простая комбинаторика (Перестановки)
18 Простые конструктивы
20 Простые разрезалки
21 Ребусы
22 Сколько детей в семье
23 Чётность

Нетрудно заметить, что темы части 1 у меня уже "причесаны", а темы части 2 - нет.
Это не случайно: я собирался их просто соединить с частью 1, сделав там специальные пометки -
потому что практически очевидно, что часть 2 является подмножеством части 1.

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

В теории чисел есть такая очень известная очень простая задача:

Для любого простого p>3 доказать, что p^2+2 делится на 3. У этой задачи есть не менее известное (и очень простое и очевидное решение): любое такое простое число имеет вид 3х+1 или 3х+2 для некого натурального х. Теперь для каждого из этих случаев возводим в квадрат сумму, прибавляем двойку и получаем число явно делящееся на 3.

Одна моя зайка сегодня мне нашла решение, которое, к моему стыду, мне в голову не пришло. В зайкином решении не нужно разбивать решение на два случая: p^2+2 сравнимо с p^2-1 по модулю 3, а p^2-1=(р-1)(р+1), причем очевидно, что одно из р+1 и р-1 обязательно делится на 3. Все. Просто и элегантно

Здравствуйте! Друзья из Швейцарии прислали задачу по геометрии их сына. Это примерно 8 класс. Можно ли решить эту задачу красиво? Опираясь, на теорему Пифагора я решила, но как-то сомневаюсь , что там так решают. Иногда, им дают задачу поломать голову , а потом говорят, что она не решается( возможно, не решается учитывая их знания на сей момент).

Гервер, Константинов, Кушниренко. Задачи по алгебре и анализу, предлагавшиеся учащимся 9 и 10 классов [школы №7] (1965) — к истории матклассов в Москве

(upd) есть и html-версия: https://www.mathedu.ru/text/obuchenie_v_matematicheskih_shkolah_1965/p41/

Очередная порция: Сочетания и бином - условия задач