Олимпиадные задачи по теме «Теория групп» для 3-11 класса

Прямой угол разбит на бесконечное число квадратных клеток со стороной единица. Будем рассматривать ряды клеток, параллельные сторонам угла (<i>вертикальные</i> и <i>горизонтальные</i> ряды). Можно ли в каждую клетку записать натуральное число так, чтобы каждый вертикальный и каждый горизонтальный ряд клеток содержал все натуральные числа по одному разу?

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

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

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

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

Можно ли разбить все целые неотрицательные числа на 1968 непустых классов так, чтобы в каждом классе было хотя бы одно число и выполнялось бы следующее условие: если число <i>m</i> получается из числа <i>n</i> вычёркиванием двух рядом стоящих цифр или одинаковых групп цифр, то и <i>m</i>, и <i>n</i> принадлежат одному классу (например, числа 7, 9339337, 93223393447, 932239447 принадлежат одному классу)?

В некотором множестве введена<nobr>операция <font face="Symbol"></font>,</nobr>которая по каждым двум элементам<i>a</i><nobr>и <i>b</i></nobr>этого множества вычисляет некоторый элемент<i>a</i><font face="Symbol"></font><i>b</i>этого множества. Известно, что:<nobr>1°. Для любых трех элементов <i>a</i>, <i>b</i> и <i>c</i></nobr> <nobr>          <i>a</i><font face="Symbol"></font>(<i>b</i><font face="Symbol"></font><i>c</i>) = <i>b</i><font face="Symbol">*</font>(<i>c</i><font face="Symbo...

Шифрпреобразование простой замены в алфавите  <i>A</i> = {<i>a</i>₁, <i>a</i>₂, ..., <i>a_n</i>},  состоящем из <i>n</i> различных букв, заключается в замене каждой буквы шифруемого текста буквой того же алфавита, причём разные буквы заменяются разными. Ключом шифра простой замены называется таблица, в которой указано, какой буквой надо заменить каждую букву алфавита <i>A</i>. Если слово СРОЧНО зашифровать простой заменой с помощью ключа: <div align="center"><img src="/storage/problem-media/35699/problem_35699_img_2.gif"></div>то получится слово ВЗДАБД. Зашифровав полученное слово с помощью того же ключа еще раз,...

Некоторый текст зашифровали, поставив в соответствие каждой букве некоторую (возможно, ту же самую букву) букву так, что текст можно однозначно расшифровать. Докажите, что найдется такое число N, что после N-кратного применения шифрования заведомо получится исходный текст. Найдите из всех таких значений N наименьшее, годящееся для всех шифров (при условии, что в алфавите 33 буквы). (Задача с сайта<a href="http://www.cryptography.ru">www.cryptography.ru</a>.)

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

Комбинация <i>А</i> поворотов кубика Рубика называется <i>порождающей</i>, если среди результатов многократного применения комбинации <i>А</i> встретятся всевозможные состояния, в которые можно перевести кубик Рубика при помощи поворотов. Существует ли порождающая комбинация поворотов?

К кубику Рубика применили последовательность поворотов. Доказать, что применяя ее несколько раз, можно привести кубик в начальное состояние.

На поверхности куба мелом отмечено 100 различных точек. Докажите, что можно двумя различными способами поставить кубик на черный стол (причем в точности на одно и то же место) так, чтобы отпечатки от мела на столе при этих способах были разными. (Если точка отмечена на ребре или в вершине, она тоже дает отпечаток.)