ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Страница: 1 2 >> [Всего задач: 6]
Комбинация А поворотов кубика Рубика называется порождающей, если среди результатов многократного применения комбинации А встретятся всевозможные состояния, в которые можно перевести кубик Рубика при помощи поворотов. Существует ли порождающая комбинация поворотов? ПодсказкаЕсли бы существовала порождающая комбинация поворотов, то для любых двух поворотов результат их последовательного применения не зависел бы от порядка выполнения этих поворотов. РешениеПредположим противное. Обозначим через А порождающую комбинацию, а за 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. Противоречие. ОтветНе существует.
ПодсказкаЧисло состояний кубика Рубика конечно; для каждого поворота есть обратный.РешениеОбозначим начальное состояние кубика Рубика за 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.
2°. Если 3°. Если Докажите, что операция * РешениеИз условий 1° и 2° следует коммутативность: подставив в 1° a вместо b, получим, что для любых a и c
Из условия 1° и коммутативности следует ассоциативность: для любых
a, b и c, согласно 1°,
Задача решена. Условие 3°, как видим, оказалось лишним. Разумеется, можно было использовать его вместо 2°. Если условие 1° выполнено, то каждое из условий 2° и 3° следует из другого.
Мы видели, что из 1° и коммутативности следует ассоциативность.
Конечно, если операция коммутативна и ассоциативна, для нее верно
1°. Однако из ассоциативности и условия 1° коммутативность
не следует (т.е. без условий 2° или 3° в доказательстве
коммутативности обойтись нельзя). Попробуйте придумать пример, доказывающий, что из одного условия 1° не следует ассоциативность.
Можно ли разбить все целые неотрицательные числа на 1968 непустых классов так, чтобы в каждом классе было хотя бы одно число и выполнялось бы следующее условие: если число m получается из числа n вычёркиванием двух рядом стоящих цифр или одинаковых групп цифр, то и m, и n принадлежат одному классу (например, числа 7, 9339337, 93223393447, 932239447 принадлежат одному классу)? РешениеПервый способ. Обозначим знаком ≈ принадлежность одному классу. MabN ≈ MbbabN ≈ MbaababN ≈ MbaN. Таким образом, числа, получающиеся перестановкой соседних цифр, принадлежат одному классу. Так как любую перестановку можно представить в виде последовательности перестановок соседних цифр, то любые два числа, запись которых отличается только перестановкой цифр, принадлежат одному классу. Следовательно, если цифра входит в запись не менее двух раз, то любые два её вхождения можно вычеркнуть, то есть информация о том, какие цифры входят в запись числа нечётное число раз, полностью определяет класс, к которому принадлежит число. Итак, число классов не превосходит 210 = 1024.
Второй способ. Рассмотрим полугруппу последовательностей цифр с операцией конкатенации (приписывания) и нейтральным элементом Λ (пустым словом). После факторизации по описанному в условии отношению эквивалентности получается полугруппа с образующими 0, 1, ..., 9 и соотношениями вида X² = Λ для каждого X. В силу этого соотношения полученная полугруппа будет группой. Так как все группы индекса 2 коммутативны, то полученная группа коммутативна. Таким образом, получаем коммутативную группу индекса два с десятью образующими. Число элементов в ней равно 1024, то есть у описанного в условии отношения эквивалентности не более 1024 классов эквивалентности. ОтветНельзя.
Прямой угол разбит на бесконечное число квадратных клеток со стороной единица. Будем рассматривать ряды клеток, параллельные сторонам угла (вертикальные и горизонтальные ряды). Можно ли в каждую клетку записать натуральное число так, чтобы каждый вертикальный и каждый горизонтальный ряд клеток содержал все натуральные числа по одному разу? Решение Первую строку заполним числами по порядку. Каждую следующую строку заполняем слева направо по следующему правилу: в очередную клетку ставим наименьшее допустимое число (то есть не совпадающее с уже поставленными под ним и слева от него числами). ОтветМожно.
Страница: 1 2 >> [Всего задач: 6] |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|