Задача із журналу «Квант» (2006 рік, №4)
Умова
Для натуральних чисел m і n позначимо через F(m,n) кількість всіх зв’язних клітинних фігур прямокутнику m×n. Доведіть, що парність числа F(m,n) збігається з парність числа n(n+1)2⋅m(m+1)2. (Зв’язна клітинна фігура – це така непорожня множина клітин, що з будь-якої клітини цієї множини можна пройти в будь-яку іншу клітину цієї множини по клітинах цієї множини, переходячи щоразу в сусідню по стороні клітину.)
Рішення
Припустимо, що F(m,0)=0. Зв’язні фігури в прямокутнику m×1 – це m фігур з однієї клітини та смужки із двох або більше клітин. Кожна смужка визначається парою клітин – першою та останньою, тому F(m,1)=m+m(m−1)2=m(m+1)2.
Нехай у прямокутнику m рядків та n>1 стовпців. Позначимо через l вертикальну вісь симетрії. Кожній зв’язній фігурі відповідає фігура, симетрична щодо l, тому несиметричні щодо l фігури розбиваються на пари, і парність F(m,n) збігається з парністю кількості зв’язних фігур, симетричних щодо l.
Розглянемо деяку фігуру T, симетричну щодо l.
Нехай n непарне, n=2k−1, k≥2. Фігура T містить хоча б одну клітину k-го стовпця, інакше з клітини фігури T неможливо пройти по клітинам T в симетричну відносно l клітину, переходячи кожен раз в сусідню клітину. Зауважимо, що частина T1 фігури T, що розташована в k найлівіших стовпцях, зв’язна. Дійсно, розглянемо дві клітини x та y фігури T1. Нехай x′ – клітина, що симетрична x відносно l, a x′,z1,z2,…,zt,y – послідовність клітин, що утворює шлях з x′ в y по сусідніх клітинах фігури T. Тоді, замінюючи в цьому шляху клітини, що лежать правіше k-го стовпця, на симетричні щодо l, ми отримаємо шлях з x в y по сусідніх клітинах фігури T1 (див. малюнок). Навпаки, якщо фігура T1 розташована у прямокутнику, що складається з k найлівіших
стовпців, зв’язна і містить хоча б одну клітину k-го стовпця, можна однозначно продовжити фігуру T1 до зв’язної фігури T, симетричної відносно l. Кількість зв’язних фігур у прямокутнику m×k дорівнює F(m,k), серед них F(m,k−1) фігур лежать у перших k−1 стовпцях (тобто не містить клітин k-го стовпця). Отже, кількість зв’язних симетричних щодо l фігур у прямокутнику m×(2k−1) дорівнює F(m,k)−F(m,k−1).
Для парного n=2k, k≥1, міркуючи аналогічно, встановимо взаємно однозначну відповідність між зв’язними симетричними щодо l фігурами та зв’язними фігурами, що розташовані в перших k стовпцях і що містять хоча б одну клітинку k-го стовпця. Звідси випливає, що кількість зв’язних симетричних щодо l фігур у прямокутнику m×2k дорівнює F(m,k)−F(m,k−1).
Отже, для n=2k−1 и n=2k парність F(m,n) збігається з парністю числа F(m,k)−F(m,k−1).
Доведемо індукцією по n, що F(m,n) непарно тоді і лише тоді, коли m і n дають залишок 1 або 2 при діленні на 4; звідси відразу випливає твердження задачі. Твердження вірне при n=0 і n=1.
Нехай m дає залишок 0 або 3 при діленні на 4. Припустимо, що це твердження вірне для F(m,0),F(m,1),…,F(m,n−1), тобто ці числа парні. Якщо n=2k−1, k≥2, або n=2k, k≥1, то n>k, тому F(m,n) парне, так як F(m,k)−F(m,k−1) парне. Нехай m дає залишок 1 або 2 при діленні на 4. Припустимо, що твердження вірно для чисел F(m,0),F(m,1),…,F(m,n−1), тобто F(m,s) непарне тоді і лише тоді, коли s дає залишок від ділення 1 або 2 при діленні на 4. Тоді F(m,s)−F(m,s−1) непарне тоді і лише тоді, коли s непарне. Звідси випливає, що F(m,n) непарне тоді і тільки тоді, коли n=2(2l+1)−1=4l+1 або n=2(2l+1)=4l+2.
