Таблицы Брадиса

Если п 1, то первый

Если п 1, то первый

Элементы математики в задачах - Г. А. Мерзон

Если п = 1, то первый уже выиграл.

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

Описанный процесс есть не что иное, как алгоритм Евклида.

-о-

Ш Чтобы решить задачу, часто полезно выделить то существенное, что нужно для ее решения. Для это можно некоторые объекты объ­явить «равными». Например, в геометрии обычно считают равными фигуры, которые можно «совместить наложением», так как они (хотя и отличаются как множества точек) имеют одинаковые свойства; проявлением этой идеи в наших листках является переход от чисел к остаткам (например, при решении целочисленных уравнений). В бо­танике растения делят на классы, семейства или виды в зависимости от конкретных задач исследования.

Математической формализацией этой идеи являются отношения эквивалентности.

Определение 1. Пусть М — множество. Произвольное множество К с {(а, Ъ) | а, Ъ е М} упорядоченных пар элементов М называется (бинарным) отношением на М. Если (а, Ъ) е К, то пишут а ~КЬ, или просто а ~ Ъ.

Ш Бинарные отношения на конечном множестве можно задавать в виде таблицы. А именно, по отношению Я построим таблицу п х п, где над строками и перед столбцами написаны наши элементы в одной и той же последовательности. А в клетке с координатами (а, Ъ) стоит 1 тогда и только тогда, когда пара (а, Ъ) принадлежит Я.