Олимпиадные задачи по теме «Отношение эквивалентности. Классы эквивалентности» для 6-10 класса
Отношение эквивалентности. Классы эквивалентности
НазадЧисла от 1 до 1000000 покрашены в два цвета – чёрный и белый. За ход разрешается выбрать любое число от 1 до 1000000 и перекрасить его и все числа, не взаимно простые с ним, в противоположный цвет. Вначале все числа были чёрными. Можно ли за несколько ходов добиться того, что все числа станут белыми?
На сфере отмечено пять точек, никакие три из которых не лежат на большой окружности (большая окружность – это окружность, по которой пересекаются сфера и плоскость, проходящая через её центр). Две большие окружности, не проходящие через отмеченные точки, называются <i>эквивалентными</i>, если одну из них с помощью непрерывнвого перемещения по сфере можно перевести в другую так, что в процессе перемещения окружность не проходит через отмеченные точки.
а) Сколько можно нарисовать окружностей, не проходящих через отмеченные точки и не эквивалентных друг другу?
б) Та же задача для <i>n</i> отмеченных точек.
Можно ли разбить все целые неотрицательные числа на 1968 непустых классов так, чтобы в каждом классе было хотя бы одно число и выполнялось бы следующее условие: если число <i>m</i> получается из числа <i>n</i> вычёркиванием двух рядом стоящих цифр или одинаковых групп цифр, то и <i>m</i>, и <i>n</i> принадлежат одному классу (например, числа 7, 9339337, 93223393447, 932239447 принадлежат одному классу)?
В алфавите племени Мумбу-Юмбу есть лишь две буквы A и Б. Два разных слова обозначают одно и то же понятие, если одно из них может быть получено из другого с помощью следующих операций:
1) в любом месте слова комбинацию букв АБА можно заменить на БАБ;
2) из любого места можно выкидывать две одинаковые буквы, идущие подряд.
а) Может ли дикарь племени сосчитать все пальцы на своей руке?
б) А дни недели?
На плоскости нарисовано некоторое количество равносторонних треугольников. Они не пересекаются, но могут иметь общие участки сторон. Мы хотим покрасить каждый треугольник в какой-нибудь цвет так, чтобы те из них, которые соприкасаются, были покрашены в разные цвета (треугольники, имеющие одну общую точку, могут быть покрашены в один цвет). Хватит ли для такой раскраски двух цветов?