IMO 2008 · Problem 5
Let \(n\) and \(k\) be positive integers with \(k \geq n\) and \(k-n\) an even number. Let \(2n\) lamps labelled \(1,2,\ldots,2n\) be given, each of which can be either on or off. Initially all the lamps are off. We consider sequences of steps: at each step one of the lamps is switched (from on to off or from off to on).
Let \(N\) be the number of such sequences consisting of \(k\) steps and resulting in the state where lamps \(1\) through \(n\) are all on, and lamps \(n+1\) through \(2n\) are all off.
Let \(M\) be the number of such sequences consisting of \(k\) steps, resulting in the state where lamps \(1\) through \(n\) are all on, and lamps \(n+1\) through \(2n\) are all off, but where none of the lamps \(n+1\) through \(2n\) is ever switched on.
Determine the ratio \(N/M\).
Official text of the problem. Official problem paper (PDF)
Answer
\[ \boxed{\frac{N}{M}=2^{\,k-n}}. \]
Solution
Represent a sequence of steps by a word of length \(k\), whose entries are the labels of the lamps switched. Since all lamps are initially off, a lamp finishes on if and only if its label occurs an odd number of times.
Consequently, \(N\) counts the words in which each label \(1,\ldots,n\) occurs an odd number of times and each label \(n+1,\ldots,2n\) occurs an even number of times. The additional restriction defining \(M\) means that no label greater than \(n\) may occur: its first occurrence would switch that lamp on. Thus \(M\) counts the words using only \(1,\ldots,n\), each occurring an odd number of times.
Map every word counted by \(N\) to a word counted by \(M\) by replacing each label \(n+i\) by \(i\), for \(1\leq i\leq n\). This indeed gives a word counted by \(M\), because the new number of occurrences of \(i\) is the sum of an odd number and an even number.
We show that every word counted by \(M\) has exactly \(2^{k-n}\) preimages. Fix such a word, and let \(r_i\) be its number of occurrences of \(i\). Then each \(r_i\) is positive and odd, and \[ r_1+\cdots+r_n=k. \]
To construct a preimage, we must decide which occurrences of \(i\) to replace by \(n+i\). The number replaced must be even; because \(r_i\) is odd, this also ensures that an odd number of occurrences of \(i\) remain.
There are exactly \(2^{r_i-1}\) ways to make this choice: decide freely whether to replace each of the first \(r_i-1\) occurrences, after which the choice for the last occurrence is uniquely determined by the requirement that the total number replaced be even. The choices for different labels are independent. Hence the number of preimages is \[ \prod_{i=1}^{n}2^{r_i-1} =2^{(r_1+\cdots+r_n)-n} =2^{k-n}. \] Therefore \[ N=2^{k-n}M. \]
Finally, \(M>0\): switch each of lamps \(1,\ldots,n\) once, then switch lamp \(1\) another \(k-n\) times. Since \(k-n\) is nonnegative and even, this is a sequence counted by \(M\). Division by \(M\) proves the stated answer.
The solution was checked against the official IMO shortlist solutions.
IMO 2008 · Aufgabe 5
Seien \(n\) und \(k\) positive ganze Zahlen mit \(k\geq n\) und \(k-n\) gerade. Gegeben seien \(2n\) Lampen, die von \(1\) bis \(2n\) nummeriert sind. Jede Lampe ist entweder an oder aus, wobei anfangs alle Lampen aus sind. Man betrachte Folgen von Schritten: in jedem Schritt werde genau eine der Lampen umgeschaltet (von aus nach an oder von an nach aus).
Sei \(N\) die Anzahl solcher Folgen, die aus \(k\) Schritten bestehen und in dem Zustand enden, in dem die Lampen \(1\) bis \(n\) alle an und die Lampen \(n+1\) bis \(2n\) alle aus sind.
Sei \(M\) die Anzahl solcher Folgen, die aus \(k\) Schritten bestehen und in dem Zustand enden, in dem die Lampen \(1\) bis \(n\) alle an und die Lampen \(n+1\) bis \(2n\) alle aus sind, bei denen aber keine der Lampen \(n+1\) bis \(2n\) jemals umgeschaltet worden ist.
Man bestimme das Verhältnis \(N/M\).
Offizieller deutscher Aufgabentext. Offizielles Aufgabenblatt (PDF)
Antwort
\[ \boxed{\frac{N}{M}=2^{\,k-n}}. \]
Lösung
Wir stellen eine Folge von Schritten durch ein Wort der Länge \(k\) dar, dessen Einträge die Nummern der umgeschalteten Lampen sind. Da anfangs alle Lampen aus sind, ist eine Lampe am Ende genau dann an, wenn ihre Nummer ungerade oft vorkommt.
Somit zählt \(N\) die Wörter, in denen jede Nummer \(1,\ldots,n\) ungerade oft und jede Nummer \(n+1,\ldots,2n\) gerade oft vorkommt. Die zusätzliche Einschränkung in der Definition von \(M\) bedeutet, dass keine Nummer größer als \(n\) vorkommen darf: Bei ihrem ersten Auftreten würde diese Lampe angeschaltet. Also zählt \(M\) die Wörter, die nur \(1,\ldots,n\) verwenden, wobei jede dieser Nummern ungerade oft vorkommt.
Wir bilden jedes von \(N\) gezählte Wort auf ein von \(M\) gezähltes Wort ab, indem wir für \(1\leq i\leq n\) jede Nummer \(n+i\) durch \(i\) ersetzen. Dies ergibt tatsächlich ein von \(M\) gezähltes Wort, denn die neue Anzahl der Vorkommen von \(i\) ist die Summe einer ungeraden und einer geraden Zahl.
Wir zeigen, dass jedes von \(M\) gezählte Wort genau \(2^{k-n}\) Urbilder hat. Wir fixieren ein solches Wort und bezeichnen mit \(r_i\) die Anzahl der Vorkommen von \(i\) darin. Dann ist jedes \(r_i\) positiv und ungerade, und es gilt \[ r_1+\cdots+r_n=k. \]
Um ein Urbild zu konstruieren, müssen wir entscheiden, welche Vorkommen von \(i\) durch \(n+i\) ersetzt werden sollen. Die Anzahl der ersetzten Vorkommen muss gerade sein; da \(r_i\) ungerade ist, stellt dies zugleich sicher, dass eine ungerade Anzahl von Vorkommen von \(i\) übrig bleibt.
Für diese Wahl gibt es genau \(2^{r_i-1}\) Möglichkeiten: Für jedes der ersten \(r_i-1\) Vorkommen kann frei entschieden werden, ob es ersetzt wird; danach ist die Wahl für das letzte Vorkommen durch die Forderung, dass die Gesamtzahl der ersetzten Vorkommen gerade sein muss, eindeutig bestimmt. Die Entscheidungen für verschiedene Nummern sind unabhängig voneinander. Daher ist die Anzahl der Urbilder \[ \prod_{i=1}^{n}2^{r_i-1} =2^{(r_1+\cdots+r_n)-n} =2^{k-n}. \] Somit gilt \[ N=2^{k-n}M. \]
Schließlich ist \(M>0\): Man schalte jede der Lampen \(1,\ldots,n\) einmal um und anschließend die Lampe \(1\) weitere \(k-n\) Male. Da \(k-n\) nichtnegativ und gerade ist, wird diese Folge von \(M\) gezählt. Division durch \(M\) beweist die angegebene Antwort.
Die Lösung wurde mit den offiziellen Lösungen der IMO-Shortlist abgeglichen.
IMO 2008 · Soru 5
\(n\) ve \(k\) pozitif tam sayı olmak üzere, \(k\geq n\) ve \(k-n\) çift sayıdır. \(1, 2, \ldots, 2n\) sayılarıyla numaralandırılmış \(2n\) tane lambanın herbiri açık veya kapalı durumda olabiliyor. Başlangıçta lambaların hepsi kapalı durumdadır. Her hamlesinde bir lamba seçilerek, seçilen lambanın durumunu değiştiren (açıktan kapalıya veya kapalıdan açığa) hamleler dizileri tanımlayalım.
Sonucunda \(1\) den \(n\) ye kadar olan lambaları açık ve \(n+1\) den \(2n\) ye kadar olan lambaları kapalı duruma getiren ve \(k\) hamle içeren tüm hamleler dizilerinin sayısı \(N\) olsun.
Sonucunda yine \(1\) den \(n\) ye kadar olan lambaları açık ve \(n+1\) den \(2n\) ye kadar olan lambaları kapalı duruma getiren ve \(k\) hamle içeren, fakat \(n+1\) den \(2n\) ye kadar olan lambalara hiç hamle yapmayan tüm hamleler dizilerinin sayısı \(M\) olsun.
\(N/M\) oranının değerini bulunuz.
Sorunun resmi Türkçe metni. Resmi soru kâğıdı (PDF)
Cevap
\[ \boxed{\frac{N}{M}=2^{\,k-n}}. \]
Çözüm
Bir hamle dizisini, terimleri durumu değiştirilen lambaların numaraları olan, \(k\) uzunluğunda bir sözcükle gösterelim. Başlangıçta tüm lambalar kapalı olduğundan, bir lambanın sonunda açık olması için gerek ve yeter koşul, numarasının tek sayıda geçmesidir.
Dolayısıyla \(N\), \(1,\ldots,n\) numaralarının her birinin tek sayıda, \(n+1,\ldots,2n\) numaralarının her birinin ise çift sayıda geçtiği sözcüklerin sayısıdır. \(M\) yi tanımlayan ek kısıtlama, \(n\) den büyük hiçbir numaranın geçemeyeceği anlamına gelir: böyle bir numaranın ilk kez geçmesi, o lambayı açık duruma getirirdi. Böylece \(M\), yalnızca \(1,\ldots,n\) numaralarını kullanan ve bunların her birinin tek sayıda geçtiği sözcüklerin sayısıdır.
\(N\) ile sayılan her sözcüğü, \(1\leq i\leq n\) için her \(n+i\) numarasını \(i\) ile değiştirerek \(M\) ile sayılan bir sözcüğe eşleyelim. Bu işlem gerçekten de \(M\) ile sayılan bir sözcük verir; çünkü \(i\) nin yeni geçiş sayısı, bir tek sayı ile bir çift sayının toplamıdır.
\(M\) ile sayılan her sözcüğün tam olarak \(2^{k-n}\) ön görüntüsü olduğunu gösterelim. Böyle bir sözcüğü sabitleyelim ve \(i\) nin bu sözcükteki geçiş sayısı \(r_i\) olsun. O hâlde her \(r_i\) pozitif ve tektir; ayrıca \[ r_1+\cdots+r_n=k. \]
Bir ön görüntü oluşturmak için, \(i\) nin hangi geçişlerini \(n+i\) ile değiştireceğimize karar vermeliyiz. Değiştirilenlerin sayısı çift olmalıdır; \(r_i\) tek olduğundan, bu aynı zamanda \(i\) nin tek sayıda geçişinin kalmasını sağlar.
Bu seçimi yapmanın tam olarak \(2^{r_i-1}\) yolu vardır: ilk \(r_i-1\) geçişin her birini değiştirip değiştirmeyeceğimize serbestçe karar veririz; ardından son geçişe ilişkin seçim, değiştirilenlerin toplam sayısının çift olması koşuluyla tek türlü belirlenir. Farklı numaralar için yapılan seçimler birbirinden bağımsızdır. Bu nedenle ön görüntülerin sayısı \[ \prod_{i=1}^{n}2^{r_i-1} =2^{(r_1+\cdots+r_n)-n} =2^{k-n} \] olur. Dolayısıyla \[ N=2^{k-n}M. \]
Son olarak, \(M>0\) dır: \(1,\ldots,n\) lambalarının her birinin durumunu bir kez değiştirelim, ardından \(1\) numaralı lambanın durumunu \(k-n\) kez daha değiştirelim. \(k-n\) negatif olmayan bir çift sayı olduğundan, bu, \(M\) ile sayılan bir dizidir. \(M\) ye bölerek belirtilen cevabı elde ederiz.
Çözüm, resmi IMO shortlist çözümleriyle karşılaştırılarak kontrol edildi.
IMO 2008 · Problema 5
Sean \(n\) y \(k\) enteros positivos tales que \(k\geq n\) y \(k-n\) es par. Se tienen \(2n\) lámparas numeradas \(1,\ 2,\ \ldots,\ 2n\), cada una de las cuales puede estar encendida o apagada. Inicialmente todas las lámparas están apagadas. Se consideran sucesiones de pasos: en cada paso se selecciona exactamente una lámpara y se cambia su estado (si está apagada se enciende, si está encendida se apaga).
Sea \(N\) el número de sucesiones de \(k\) pasos al cabo de los cuales las lámparas \(1,2,\ldots,n\) quedan todas encendidas, y las lámparas \(n+1,\ldots,2n\) quedan todas apagadas.
Sea \(M\) el número de sucesiones de \(k\) pasos al cabo de los cuales las lámparas \(1,2,\ldots,n\) quedan todas encendidas, y las lámparas \(n+1,\ldots,2n\) quedan todas apagadas sin haber sido nunca encendidas.
Calcular la razón \(N/M\).
Texto oficial en español del problema. Enunciado oficial (PDF)
Respuesta
\[ \boxed{\frac{N}{M}=2^{\,k-n}}. \]
Solución
Representemos una sucesión de pasos mediante una palabra de longitud \(k\), cuyas entradas son los números de las lámparas cuyo estado se cambia. Como al principio todas las lámparas están apagadas, una lámpara termina encendida si y solo si su número aparece un número impar de veces.
Por consiguiente, \(N\) cuenta las palabras en las que cada número \(1,\ldots,n\) aparece un número impar de veces y cada número \(n+1,\ldots,2n\) aparece un número par de veces. La restricción adicional que define \(M\) significa que no puede aparecer ningún número mayor que \(n\): su primera aparición encendería esa lámpara. Así pues, \(M\) cuenta las palabras que usan únicamente \(1,\ldots,n\), cada uno de los cuales aparece un número impar de veces.
A cada palabra contada por \(N\) le asignamos una palabra contada por \(M\) sustituyendo cada número \(n+i\) por \(i\), para \(1\leq i\leq n\). Esto da, en efecto, una palabra contada por \(M\), porque el nuevo número de apariciones de \(i\) es la suma de un número impar y un número par.
Demostraremos que cada palabra contada por \(M\) tiene exactamente \(2^{k-n}\) preimágenes. Fijemos una de esas palabras, y sea \(r_i\) su número de apariciones de \(i\). Entonces cada \(r_i\) es positivo e impar, y \[ r_1+\cdots+r_n=k. \]
Para construir una preimagen, debemos decidir qué apariciones de \(i\) sustituir por \(n+i\). El número de apariciones sustituidas debe ser par; como \(r_i\) es impar, esto también garantiza que quede un número impar de apariciones de \(i\).
Hay exactamente \(2^{r_i-1}\) maneras de hacer esta elección: decidimos libremente si sustituir cada una de las primeras \(r_i-1\) apariciones, tras lo cual la elección para la última aparición queda determinada de forma única por la exigencia de que el número total de apariciones sustituidas sea par. Las elecciones para números distintos son independientes. Por tanto, el número de preimágenes es \[ \prod_{i=1}^{n}2^{r_i-1} =2^{(r_1+\cdots+r_n)-n} =2^{k-n}. \] Por tanto, \[ N=2^{k-n}M. \]
Finalmente, \(M>0\): cambiamos el estado de cada una de las lámparas \(1,\ldots,n\) una vez y, después, cambiamos el estado de la lámpara \(1\) otras \(k-n\) veces. Como \(k-n\) es no negativo y par, esta es una sucesión contada por \(M\). Dividiendo por \(M\) se demuestra la respuesta indicada.
La solución se comprobó con las soluciones oficiales de la shortlist de la IMO.
IMO 2008 · 问题 5
设 \(n\) 和 \(k\) 是正整数，\(k\geq n\)，且 \(k-n\) 是一个偶数．\(2n\) 盏灯依次编号为 \(1,\ 2,\ \cdots,\ 2n\)，每一盏灯可以“开”和“关”．开始时，所有的灯都是“关”的．对这些灯可进行操作，每一次操作只改变其中的一盏灯的开关状态（即“开”变成“关”，“关”变成“开”），我们考虑长度为 \(k\) 的操作序列，序列中的第 \(i\) 项就是第 \(i\) 次操作时被改变开关状态的那盏灯的编号．
设 \(N\) 是 \(k\) 次操作后使得灯 \(1,\ \cdots,\ n\) 是“开”的，灯 \(n+1,\ \cdots,\ 2n\) 是“关”的状态的所有不同的操作序列的个数．
设 \(M\) 是 \(k\) 次操作后使得灯 \(1,\ \cdots,\ n\) 是“开”的，灯 \(n+1,\ \cdots,\ 2n\) 是“关”的，但是灯 \(n+1,\ \cdots,\ 2n\) 始终没有被开过的所有不同的操作序列的个数．
求比值 \(\dfrac{N}{M}\)．
题目为官方中文译本。 官方试卷 (PDF)
答案
\[ \boxed{\frac{N}{M}=2^{\,k-n}}. \]
解答
用一个长度为 \(k\) 的字来表示一个操作序列，其中各项是被改变开关状态的灯的编号。由于所有灯最初都是关的，一盏灯最终为开当且仅当它的编号出现奇数次。
因此，\(N\) 计数的是每个编号 \(1,\ldots,n\) 均出现奇数次、每个编号 \(n+1,\ldots,2n\) 均出现偶数次的字。定义 \(M\) 时所加的限制意味着，任何大于 \(n\) 的编号都不能出现：它的第一次出现就会把对应的灯打开。因此，\(M\) 计数的是仅使用 \(1,\ldots,n\)，且每个编号均出现奇数次的字。
对于 \(N\) 所计数的每个字，将其中的每个编号 \(n+i\) 替换为 \(i\)，其中 \(1\leq i\leq n\)，从而将它映射到 \(M\) 所计数的一个字。这确实得到 \(M\) 所计数的一个字，因为替换后 \(i\) 的出现次数是一个奇数与一个偶数之和。
我们证明，\(M\) 所计数的每个字恰有 \(2^{k-n}\) 个原像。固定这样的一个字，设 \(r_i\) 为其中 \(i\) 的出现次数。那么每个 \(r_i\) 都是正奇数，且 \[ r_1+\cdots+r_n=k. \]
为了构造一个原像，我们必须决定将哪些位置上的 \(i\) 替换为 \(n+i\)。替换的次数必须是偶数；由于 \(r_i\) 是奇数，这也保证了留下的 \(i\) 的个数为奇数。
这样的选择恰有 \(2^{r_i-1}\) 种：对于前 \(r_i-1\) 次出现的 \(i\)，可自由决定是否替换，之后最后一次出现的 \(i\) 是否替换，就由替换总次数为偶数这一要求唯一确定。不同编号的选择相互独立。因此，原像的个数为 \[ \prod_{i=1}^{n}2^{r_i-1} =2^{(r_1+\cdots+r_n)-n} =2^{k-n}. \] 所以 \[ N=2^{k-n}M. \]
最后，\(M>0\)：将灯 \(1,\ldots,n\) 各改变一次开关状态，然后将灯 \(1\) 再改变 \(k-n\) 次开关状态。由于 \(k-n\) 是非负偶数，这个序列被 \(M\) 计数。两边除以 \(M\)，便得所述答案。
解答已与 IMO 官方预选题（shortlist）解答核对。
IMO 2008 · Задача 5
Пусть \(n\) и \(k\) — натуральные числа такие, что \(k\geq n\), а число \(k-n\) четное. Имеются \(2n\) лампочек, занумерованных числами \(1,\ 2,\ \ldots,\ 2n\), каждая из которых может находиться в одном из двух состояний: вкл. (включена) или выкл. (выключена). Вначале все лампочки были выключены. Рассматриваются упорядоченные последовательности шагов: на каждом шаге ровно одна из лампочек меняет свое состояние на противоположное (с вкл. на выкл., либо с выкл. на вкл.).
Обозначим через \(N\) количество последовательностей из \(k\) шагов, приводящих к ситуации, в которой все лампочки с \(1\)-й по \(n\)-ю включены, а все лампочки с \((n+1)\)-й по \((2n)\)-ю выключены.
Обозначим через \(M\) количество последовательностей из \(k\) шагов, приводящих к ситуации, в которой также все лампочки с \(1\)-й по \(n\)-ю включены, все лампочки с \((n+1)\)-й по \((2n)\)-ю выключены, но при этом ни одна из лампочек с \((n+1)\)-й по \((2n)\)-ю ни разу не меняла своего состояния.
Найдите значение отношения \(N/M\).
Официальный русский текст задачи. Официальный текст задач (PDF)
Ответ
\[ \boxed{\frac{N}{M}=2^{\,k-n}}. \]
Решение
Представим последовательность шагов словом длины \(k\), символами которого служат номера переключаемых лампочек. Поскольку изначально все лампочки выключены, лампочка в конце окажется включённой тогда и только тогда, когда её номер встречается нечётное число раз.
Следовательно, \(N\) — число слов, в которых каждый номер \(1,\ldots,n\) встречается нечётное число раз, а каждый номер \(n+1,\ldots,2n\) — чётное число раз. Дополнительное ограничение в определении \(M\) означает, что ни один номер, больший \(n\), не может встречаться: при первом его появлении соответствующая лампочка включилась бы. Таким образом, \(M\) — число слов, в которых используются только номера \(1,\ldots,n\), причём каждый встречается нечётное число раз.
Каждому слову, учитываемому в \(N\), сопоставим слово, учитываемое в \(M\), заменив каждый номер \(n+i\) на \(i\) при \(1\leq i\leq n\). При этом действительно получается слово, учитываемое в \(M\), поскольку новое число вхождений \(i\) равно сумме нечётного и чётного чисел.
Покажем, что каждое слово, учитываемое в \(M\), имеет ровно \(2^{k-n}\) прообразов. Зафиксируем такое слово и обозначим через \(r_i\) число вхождений \(i\) в него. Тогда каждое \(r_i\) положительно и нечётно, причём \[ r_1+\cdots+r_n=k. \]
Чтобы построить прообраз, нужно выбрать, какие вхождения \(i\) заменить на \(n+i\). Число заменённых вхождений должно быть чётным; поскольку \(r_i\) нечётно, это также гарантирует, что останется нечётное число вхождений \(i\).
Сделать этот выбор можно ровно \(2^{r_i-1}\) способами: для каждого из первых \(r_i-1\) вхождений произвольно решаем, заменять ли его, после чего выбор для последнего вхождения однозначно определяется требованием чётности общего числа заменённых вхождений. Выборы для разных номеров независимы. Следовательно, число прообразов равно \[ \prod_{i=1}^{n}2^{r_i-1} =2^{(r_1+\cdots+r_n)-n} =2^{k-n}. \] Поэтому \[ N=2^{k-n}M. \]
Наконец, \(M>0\): переключим каждую из лампочек \(1,\ldots,n\) один раз, а затем переключим лампочку \(1\) ещё \(k-n\) раз. Поскольку \(k-n\) неотрицательно и чётно, эта последовательность учитывается в \(M\). Деление на \(M\) даёт указанный ответ.
Решение проверено по официальным решениям шортлиста IMO.
IMO 2008 · المسألة 5
ليكن \(n\) و \(k\) عددين صحيحين موجبين حيث \(k\geq n\) و \(k-n\) عدد زوجي.
لدينا \(2n\) مصباحا مرقمة \(1\) ، \(2\) ، ... ، \(2n\). كل مصباح من هذه المصابيح يمكن أن يكون في وضع ON (مضاء) أو وضع OFF (مطفئ). في البداية جميع المصابيح في وضع OFF.
الخطوة: هي تغيير وضع المصباح (من OFF إلى ON أو من ON إلى OFF)
السلسلة : هي عدد من الخطوات المتتالية.
ليكن \(N\) عدد السلاسل المكونة من \(k\) خطوة و التي تنتهي إلى الحالة التي تكون فيها المصابيح من \(1\) إلى \(n\) جميعها في الوضع ON و المصابيح من \(n+1\) إلى \(2n\) جميعها في الوضع OFF.
ليكن \(M\) عدد السلاسل المكونة من \(k\) خطوة و التي تنتهي إلى الحالة التي تكون فيها المصابيح من \(1\) إلى \(n\) جميعها في الوضع ON و المصابيح من \(n+1\) إلى \(2n\) جميعها في الوضع OFF بحيث أن المصابيح من \(n+1\) إلى \(2n\) لم تمس (لم يغير وضعها البدائي)
أوجد النسبة \(\frac{N}{M}\).
نص المسألة هو الترجمة العربية الرسمية. ورقة المسائل الرسمية (PDF)
الإجابة
\[ \boxed{\frac{N}{M}=2^{\,k-n}}. \]
الحل
نمثل سلسلة من الخطوات بكلمة طولها \(k\)، عناصرها هي أرقام المصابيح التي يُغيَّر وضعها. وبما أن جميع المصابيح مطفأة في البداية، فإن المصباح يكون مضاءً في النهاية إذا وفقط إذا ورد رقمه عددًا فرديًا من المرات.
ومن ثم، فإن \(N\) يعدّ الكلمات التي يرد فيها كل رقم من \(1,\ldots,n\) عددًا فرديًا من المرات، وكل رقم من \(n+1,\ldots,2n\) عددًا زوجيًا من المرات. ويعني القيد الإضافي الذي يعرّف \(M\) أنه لا يجوز ورود أي رقم أكبر من \(n\): فوروده الأول سيضيء ذلك المصباح. إذن \(M\) يعدّ الكلمات التي لا تستخدم إلا الأرقام \(1,\ldots,n\)، بحيث يرد كل منها عددًا فرديًا من المرات.
نربط كل كلمة محسوبة في \(N\) بكلمة محسوبة في \(M\)، وذلك باستبدال كل رقم \(n+i\) بالرقم \(i\)، لكل \(1\leq i\leq n\). وهذا يعطي بالفعل كلمة محسوبة في \(M\)، لأن العدد الجديد لمرات ورود \(i\) هو مجموع عدد فردي وعدد زوجي.
نبين أن لكل كلمة محسوبة في \(M\) بالضبط \(2^{k-n}\) صورة عكسية. نثبت كلمة كهذه، وليكن \(r_i\) عدد مرات ورود \(i\) فيها. عندئذ يكون كل \(r_i\) موجبًا وفرديًا، ولدينا \[ r_1+\cdots+r_n=k. \]
لإنشاء صورة عكسية، يجب أن نحدد أيًّا من مواضع ورود \(i\) سنستبدل فيه \(n+i\) به. ويجب أن يكون عدد الاستبدالات زوجيًا؛ وبما أن \(r_i\) فردي، فإن ذلك يضمن أيضًا بقاء عدد فردي من مرات ورود \(i\).
يوجد بالضبط \(2^{r_i-1}\) طريقة لإجراء هذا الاختيار: نقرر بحرية إجراء الاستبدال أو عدمه في كل من مواضع الورود الأولى البالغ عددها \(r_i-1\)، ثم يتحدد الاختيار في الموضع الأخير بشكل وحيد من شرط كون العدد الكلي للاستبدالات زوجيًا. والاختيارات الخاصة بالأرقام المختلفة مستقلة. ومن ثم فإن عدد الصور العكسية هو \[ \prod_{i=1}^{n}2^{r_i-1} =2^{(r_1+\cdots+r_n)-n} =2^{k-n}. \] لذلك \[ N=2^{k-n}M. \]
وأخيرًا، \(M>0\): نغير وضع كل مصباح من \(1,\ldots,n\) مرة واحدة، ثم نغير وضع المصباح \(1\) عددًا إضافيًا من المرات قدره \(k-n\). وبما أن \(k-n\) غير سالب وزوجي، فهذه سلسلة محسوبة في \(M\). وبالقسمة على \(M\) تثبت الإجابة المذكورة.
تمت مراجعة الحل بمقارنته بالحلول الرسمية لقائمة IMO المختصرة.