і дотримується не у всіх завданнях розглянутого типу; наприклад, у шахах пішаки назад не ходять. У цій статті ми обмежимося завданнями, для яких умова симетричності виконано.
Домовимося вважати, що з будь-якої позиції a можна В«перейтиВ» у неї ж. Це властивість називається рефлексивностью.
Назвемо позиції a і p еквівалентними, якщо по заданих правилам з a можна перейти в p (зважаючи припущень симетричності це рівнозначно тому, що з p можна пе-Рейті в a ). Еквівалентність позицій a і p ми будемо позначати так: a ~ p ; нееквівалентність - так: a ~/ p .
Оскільки еквівалентність позицій рефлексивна, симетрична і транзитивна, вихідна безліч М розбивається на непусті непересічні підмножини (рис. 1): М = M1UM2UM3U ... У кожному з підмножин M i , всі позиції еквівалентні: якщо a з М i , і p з M < i> i , то a ~ p . Якщо ж позиції a і p належать різним підмножини: a з M i p з M j ( i відмінно від < i> j ), то a і p не еквівалентні). Підмножини М i ми будемо називати орбітами. Повторимо ще раз: якщо ми знаходимося в позиції a , що належить який-небудь орбіті M i , то ми можемо, переміщаючись по цій орбіті, перебратися з позиції a в будь-яку іншу позицію, приналежну орбіті. З іншого боку, зійти з цієї орбіти, тобто перебратися з позиції a на позицію p , що належить будь-який інший орбіті, ми не можемо. Орбіт може бути як кінцеве, так і нескінченне число. Втім, якщо безліч М звичайно, те, зрозуміло, і число орбіт звичайно. Інваріант. Числова функція f , визначена на множині В«позиційВ» M , називається інваріантної функцією, або інваріантом, якщо на еквівалентних позиціях вона приймає однакові значення: якщо a ~ р , то f (а) = f (р) . (1)
Завдання 1 (продовження). Нехай п = 2 т. Розфарбуємо сектори через один в сірий і білий колір. Тоді при кожному переміщенні число фішок у білих секторах або не змінюється (рис. 2), або збільшується на 2 (рис. 3), або зменшується на 2 (рис. 4). Для довільної розстановки a фішок по секторах позначимо через б (а) число фішок у білих секторах. Розглянемо тепер таку функцію g .
0, якщо б (a) парне,
g ( a
