ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: 1 2 >> [Всего задач: 6]      



Задача 35293

Тема:   [ Теория групп (прочее) ]
Сложность: 3+
Классы: 10,11

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

Подсказка

Если бы существовала порождающая комбинация поворотов, то для любых двух поворотов результат их последовательного применения не зависел бы от порядка выполнения этих поворотов.

Решение

Предположим противное. Обозначим через А порождающую комбинацию, а за X начальное состояние кубика. Тогда в последовательности X, A(X), A(A(X)), ... встретятся все состояния кубика. Возьмём два простых поворота кубика: P – поворот правой грани, Q – поворот верхней грани. Применив поворот P к состоянию X, получим состояние P(X). Согласно нашему предположению оно совпадает с некоторым состоянием вида Am(X) для некоторого натурального m. Аналогично  Q(X) = An(X)  для некоторого натурального n. Тогда  P(Q(X)) = Q(P(X)) = Am+n(X).  Однако нетрудно проверить, что результат последовательного выполнения поворотов P и Q отличается от результата последовательного выполнения поворотов Q и P. Противоречие.

Ответ

Не существует.

Прислать комментарий

Задача 35240

Тема:   [ Теория групп (прочее) ]
Сложность: 4-
Классы: 9,10,11

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

Подсказка

Число состояний кубика Рубика конечно; для каждого поворота есть обратный.

Решение

Обозначим начальное состояние кубика Рубика за A. Пусть P=P1P2...Pn - некоторая последовательность поворотов. Обозначим через P(X) результат применения последовательности поворотов P к состоянию X, и через Pm(X) результат m-кратного применения последовательности поворотов P к состоянию X. Рассмотрим последовательность состояний A, P(A), P2(A), P3(A), ... Поскольку имеется лишь конечное число состояний кубика Рубика, то в этой последовательности встретится повторение, т.е. Pk(A)=Pn(A)=B для некоторых k, n, k<n. Для каждого поворота Pi кубика есть обратный поворот P-1i (т.е. такой поворот, что P-1i(Pi) = Pi(P-1i) есть тождественное преобразование). Таким образом, для последовательности поворотов P=P1P2...Pn имеется обратное преобразование P-1, определяемое как последовательное выполнение поворотов P-1n, P-1n-1, ... , P-11. Применяя преобразование P-1 к состоянию B=Pk(A)=Pn(A), мы получаем, что P-1(B)=Pk-1(A)=Pn-1(A). Проводя дальнейшие рассуждения подобным образом, мы получим совпадение состояний Pk-2(A)=Pn-2(A), ... , P1(A)=Pn-k+1(A). Таким образом, начальное состояние повторится после (n-k+1)-кратного выполнения последовательности поворотов P.
Прислать комментарий


Задача 73655

Темы:   [ Теория групп (прочее) ]
[ Процессы и операции ]
Сложность: 4
Классы: 9,10,11

В некотором множестве введена операция *, которая по каждым двум элементам a и b этого множества вычисляет некоторый элемент a*b этого множества. Известно, что: 1°. Для любых трех элементов a, b и c
          a*(b*c) = b*(c*a).
2°. Если a*b = a*c, то b = c.
3°. Если a*c = b*c, то a = b.

Докажите, что операция *
а) коммутативна, то есть для любых элементов a и b верно равенство a*b = b*a;
б) ассоциативна, то есть для любых элементов a, b и c верно равенство (a*b)*c = a*(b*c).

Решение

Из условий 1° и 2° следует коммутативность: подставив в a вместо b, получим, что для любых a и c

a*(a*c) = a*(c*a),
а отсюда следует, согласно 2°, что a*c = c*a.

Из условия 1° и коммутативности следует ассоциативность: для любых a, b и c, согласно 1°,

a*(b*c) = b*(c*a) = c*(a* b)
и, пользуясь коммутативностью, получаем
a*(b*c) = c*(a*b) = (a*b)*c.

Задача решена. Условие 3°, как видим, оказалось лишним. Разумеется, можно было использовать его вместо 2°. Если условие 1° выполнено, то каждое из условий 2° и 3° следует из другого.

Мы видели, что из 1° и коммутативности следует ассоциативность. Конечно, если операция коммутативна и ассоциативна, для нее верно 1°. Однако из ассоциативности и условия 1° коммутативность не следует (т.е. без условий 2° или 3° в доказательстве коммутативности обойтись нельзя).
Приведем пример, подтверждающий это: пусть множество состоит из четырех элементов 0, 1, 2, 3 и операция * определена так: 1*2 = 3, и для любой другой пары элементов a*b = 0 (в частности, 2*1 = 0); в этом примере (a*b)*c = a*(b*c) = 0 для любых трех a, b и c.

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


Задача 78666

Темы:   [ Отношение эквивалентности. Классы эквивалентности ]
[ Процессы и операции ]
[ Четность и нечетность ]
[ Теория групп (прочее) ]
Сложность: 4-
Классы: 9,10,11

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

Решение

Первый способ. Обозначим знаком ≈ принадлежность одному классу.  MabNMbbabNMbaababNMbaN.  Таким образом, числа, получающиеся перестановкой соседних цифр, принадлежат одному классу. Так как любую перестановку можно представить в виде последовательности перестановок соседних цифр, то любые два числа, запись которых отличается только перестановкой цифр, принадлежат одному классу. Следовательно, если цифра входит в запись не менее двух раз, то любые два её вхождения можно вычеркнуть, то есть информация о том, какие цифры входят в запись числа нечётное число раз, полностью определяет класс, к которому принадлежит число. Итак, число классов не превосходит  210 = 1024.

Второй способ. Рассмотрим полугруппу последовательностей цифр с операцией конкатенации (приписывания) и нейтральным элементом Λ (пустым словом). После факторизации по описанному в условии отношению эквивалентности получается полугруппа с образующими 0, 1, ..., 9 и соотношениями вида   X² = Λ  для каждого X. В силу этого соотношения полученная полугруппа будет группой. Так как все группы индекса 2 коммутативны, то полученная группа коммутативна. Таким образом, получаем коммутативную группу индекса два с десятью образующими. Число элементов в ней равно 1024, то есть у описанного в условии отношения эквивалентности не более 1024 классов эквивалентности.

Ответ

Нельзя.

Прислать комментарий

Задача 97969

Темы:   [ Числовые таблицы и их свойства ]
[ Примеры и контрпримеры. Конструкции ]
[ Индукция (прочее) ]
[ Теория групп (прочее) ]
Сложность: 4+
Классы: 8,9,10

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

Решение

  Первую строку заполним числами по порядку. Каждую следующую строку заполняем слева направо по следующему правилу: в очередную клетку ставим наименьшее допустимое число (то есть не совпадающее с уже поставленными под ним и слева от него числами).
  Докажем, что число n появится в k-м столбце. Действительного, его появлению может препятствовать только то, что во всех строчках, кроме тех, где в этом столбце стоят меньшие числа, n встречается левее k-го места. Но это невозможно: в первых  k – 1  столбцах n встречается не более  k – 1  раз. Ситуация со строками аналогична.

Ответ

Можно.

Прислать комментарий

Страница: 1 2 >> [Всего задач: 6]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .