IMO 1990 · Problem 5
Given an initial integer \(n_0>1\), two players, \(\mathcal A\) and \(\mathcal B\), choose integers \(n_1,n_2,n_3,\ldots\) alternately according to the following rules:
Knowing \(n_{2k}\), \(\mathcal A\) chooses any integer \(n_{2k+1}\) such that \[ n_{2k}\le n_{2k+1}\le n_{2k}^{2}. \]
Knowing \(n_{2k+1}\), \(\mathcal B\) chooses any integer \(n_{2k+2}\) such that \[ \frac{n_{2k+1}}{n_{2k+2}} \] is a prime raised to a positive integer power.
Player \(\mathcal A\) wins the game by choosing the number 1990; player \(\mathcal B\) wins by choosing the number 1. For which \(n_0\) does:
(a) \(\mathcal A\) have a winning strategy?
(b) \(\mathcal B\) have a winning strategy?
(c) Neither player have a winning strategy?
Official text of the problem. Official problem paper (PDF)
Answer
(a) All integers \(n_0\ge8\).
(b) \(n_0\in\{2,3,4,5\}\).
(c) \(n_0\in\{6,7\}\).
Solution
Write \(n\) for the number before a turn of \(\mathcal A\), and \(m\) for the number she chooses. Thus \(n\le m\le n^2\), and \(\mathcal B\) must replace \(m\) by \(m/p^a\), where \(p\) is prime, \(a\ge1\), and \(p^a\mid m\).
Winning strategy for \(\mathcal A\) when \(8\le n_0\le1990\). Use the following table:
| Current \(n\) | \(\mathcal A\) chooses | All possible replies by \(\mathcal B\) |
|---|---|---|
| \(45\le n\le1990\) | \(1990\) | \(\mathcal A\) wins immediately |
| \(21\le n\le44\) | \(420\) | \(60,84,105,140,210\) |
| \(15\le n\le20\) | \(210\) | \(30,42,70,105\) |
| \(11\le n\le14\) | \(105\) | \(15,21,35\) |
| \(8\le n\le10\) | \(60\) | \(12,15,20,30\) |
Every choice is legal: it is at least the upper endpoint of its interval and at most the square of the lower endpoint. The reply lists follow directly from the prime factorizations \[ 420=2^2\cdot3\cdot5\cdot7,\qquad 210=2\cdot3\cdot5\cdot7,\qquad 105=3\cdot5\cdot7,\qquad 60=2^2\cdot3\cdot5. \] Every reply in a row belongs to an earlier row. Therefore \(\mathcal A\) reaches the first row and wins after at most five of her turns.
Winning strategy for \(\mathcal A\) when \(n_0>1990\). Whenever \(n>1990\), choose \[ m=60\left\lceil\frac n{60}\right\rceil. \] This is legal because \[ n\le m<n+60<2n\le n^2. \]
Let \(\mathcal B\)'s reply be \(n'=m/p^a\). Since \(60\mid m\):
- if \(p=2\), then \(15\mid n'\);
- if \(p=3\), then \(20\mid n'\);
- if \(p=5\), then \(12\mid n'\);
- otherwise, \(60\mid n'\).
Consequently, \[ 12\le n'\le\frac m2<n. \] Thus \(\mathcal B\) cannot win, and the current number strictly decreases whenever it exceeds 1990. After finitely many rounds it lies between 12 and 1990, where the table gives \(\mathcal A\) a winning strategy.
Winning strategy for \(\mathcal B\) when \(2\le n_0\le5\). Suppose the current number satisfies \(2\le n\le5\). Then \[ 2\le m\le n^2\le25. \] Since \(2\cdot3\cdot5=30>25\), the number \(m\) has at most two distinct prime divisors.
If \(m\) is a prime power, \(\mathcal B\) chooses 1 and wins. Otherwise write \[ m=p^a q^b \] with distinct primes \(p,q\) and positive integers \(a,b\). Player \(\mathcal B\) divides by the larger of \(p^a,q^b\), leaving \[ n'=\min(p^a,q^b)<\sqrt m\le n. \] The strict inequality holds because powers of distinct primes cannot be equal.
This strategy strictly decreases the positive integer \(n\) after each round until \(\mathcal B\) chooses 1. Throughout, \(\mathcal A\)'s choices are at most 25, so she cannot win first.
Neither player has a winning strategy when \(n_0=6\) or \(7\). We give each player a strategy preventing the other from winning.
Player \(\mathcal A\) can always choose 30. This is legal initially, and \(\mathcal B\)'s only replies are \[ 30/2=15,\qquad30/3=10,\qquad30/5=6. \] For each \(n\in\{6,10,15\}\), the choice 30 is again legal. Repeating it prevents \(\mathcal B\) from ever choosing 1.
Conversely, \(\mathcal B\) can keep the current number at most 7. Indeed, if \(2\le n\le7\), then \(m\le49\). If \(m\) has at most two distinct prime divisors, the preceding strategy either wins immediately or gives \(n'<n\le7\).
The only integers at most 49 having at least three distinct prime divisors are 30 and 42. To see this, the three smallest such divisors must be \(2,3,5\) or \(2,3,7\): every other triple has product at least \[ \min(2\cdot3\cdot11,\;2\cdot5\cdot7,\;3\cdot5\cdot7)=66. \] Moreover, any proper multiple of 30 or 42 exceeds 49. For \(m=30\) or \(42\), player \(\mathcal B\) divides by 5 or 7, respectively, leaving 6.
Hence \(\mathcal B\) can always return a number at most 7, unless he has already won. Player \(\mathcal A\)'s subsequent choices are therefore at most 49, so she can never choose 1990. This proves that neither player can force a win from 6 or 7.
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1990 · Aufgabe 5
Ausgehend von einer gegebenen ganzen Zahl \(n_0>1\) wählen zwei Spieler, \(\mathcal A\) und \(\mathcal B\), abwechselnd ganze Zahlen \(n_1,n_2,n_3,\ldots\) nach den folgenden Regeln:
Ist \(n_{2k}\) bekannt, so wählt \(\mathcal A\) eine beliebige ganze Zahl \(n_{2k+1}\) mit \[ n_{2k}\le n_{2k+1}\le n_{2k}^{2}. \]
Ist \(n_{2k+1}\) bekannt, so wählt \(\mathcal B\) eine beliebige ganze Zahl \(n_{2k+2}\), sodass \[ \frac{n_{2k+1}}{n_{2k+2}} \] eine Potenz einer Primzahl mit positivem ganzzahligem Exponenten ist.
Spieler \(\mathcal A\) gewinnt das Spiel, indem er die Zahl 1990 wählt; Spieler \(\mathcal B\) gewinnt, indem er die Zahl 1 wählt. Für welche \(n_0\) gilt:
(a) \(\mathcal A\) hat eine Gewinnstrategie?
(b) \(\mathcal B\) hat eine Gewinnstrategie?
(c) Keiner der beiden Spieler hat eine Gewinnstrategie?
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Antwort
(a) Alle ganzen Zahlen \(n_0\ge8\).
(b) \(n_0\in\{2,3,4,5\}\).
(c) \(n_0\in\{6,7\}\).
Lösung
Wir bezeichnen die Zahl vor einem Zug von \(\mathcal A\) mit \(n\) und die von ihm gewählte Zahl mit \(m\). Es gilt also \(n\le m\le n^2\), und \(\mathcal B\) muss \(m\) durch \(m/p^a\) ersetzen, wobei \(p\) eine Primzahl ist, \(a\ge1\) und \(p^a\mid m\) gelten.
Gewinnstrategie für \(\mathcal A\), wenn \(8\le n_0\le1990\). Wir verwenden die folgende Tabelle:
| Aktuelles \(n\) | \(\mathcal A\) wählt | Alle möglichen Antworten von \(\mathcal B\) |
|---|---|---|
| \(45\le n\le1990\) | \(1990\) | \(\mathcal A\) gewinnt sofort |
| \(21\le n\le44\) | \(420\) | \(60,84,105,140,210\) |
| \(15\le n\le20\) | \(210\) | \(30,42,70,105\) |
| \(11\le n\le14\) | \(105\) | \(15,21,35\) |
| \(8\le n\le10\) | \(60\) | \(12,15,20,30\) |
Jede Wahl ist zulässig: Die gewählte Zahl ist mindestens so groß wie die obere Grenze ihres Intervalls und höchstens so groß wie das Quadrat der unteren Grenze. Die Listen der Antworten ergeben sich unmittelbar aus den Primfaktorzerlegungen \[ 420=2^2\cdot3\cdot5\cdot7,\qquad 210=2\cdot3\cdot5\cdot7,\qquad 105=3\cdot5\cdot7,\qquad 60=2^2\cdot3\cdot5. \] Jede Antwort in einer Zeile gehört zu einer weiter oben stehenden Zeile. Daher erreicht \(\mathcal A\) die erste Zeile und gewinnt nach höchstens fünf eigenen Zügen.
Gewinnstrategie für \(\mathcal A\), wenn \(n_0>1990\). Solange \(n>1990\) gilt, wählt er \[ m=60\left\lceil\frac n{60}\right\rceil. \] Dies ist zulässig, denn \[ n\le m<n+60<2n\le n^2. \]
Sei \(n'=m/p^a\) die Antwort von \(\mathcal B\). Wegen \(60\mid m\) gilt:
- Ist \(p=2\), so gilt \(15\mid n'\);
- ist \(p=3\), so gilt \(20\mid n'\);
- ist \(p=5\), so gilt \(12\mid n'\);
- andernfalls gilt \(60\mid n'\).
Folglich ist \[ 12\le n'\le\frac m2<n. \] Somit kann \(\mathcal B\) nicht gewinnen, und die aktuelle Zahl nimmt streng ab, solange sie größer als 1990 ist. Nach endlich vielen Runden liegt sie zwischen 12 und 1990, wo die Tabelle eine Gewinnstrategie für \(\mathcal A\) liefert.
Gewinnstrategie für \(\mathcal B\), wenn \(2\le n_0\le5\). Die aktuelle Zahl erfülle \(2\le n\le5\). Dann gilt \[ 2\le m\le n^2\le25. \] Wegen \(2\cdot3\cdot5=30>25\) hat die Zahl \(m\) höchstens zwei verschiedene Primteiler.
Ist \(m\) eine Primzahlpotenz, so wählt \(\mathcal B\) die Zahl 1 und gewinnt. Andernfalls schreiben wir \[ m=p^a q^b \] mit verschiedenen Primzahlen \(p,q\) und positiven ganzen Zahlen \(a,b\). Spieler \(\mathcal B\) dividiert durch die größere der beiden Zahlen \(p^a,q^b\), sodass \[ n'=\min(p^a,q^b)<\sqrt m\le n \] übrig bleibt. Die strenge Ungleichung gilt, weil Potenzen verschiedener Primzahlen nicht gleich sein können.
Bei dieser Strategie nimmt die positive ganze Zahl \(n\) nach jeder Runde streng ab, bis \(\mathcal B\) die Zahl 1 wählt. Während des gesamten Spiels sind die von \(\mathcal A\) gewählten Zahlen höchstens 25, sodass er nicht zuvor gewinnen kann.
Keiner der beiden Spieler hat eine Gewinnstrategie, wenn \(n_0=6\) oder \(7\). Wir geben für jeden Spieler eine Strategie an, die verhindert, dass der andere gewinnt.
Spieler \(\mathcal A\) kann stets 30 wählen. Dies ist zu Beginn zulässig, und die einzigen Antworten von \(\mathcal B\) sind \[ 30/2=15,\qquad30/3=10,\qquad30/5=6. \] Für jedes \(n\in\{6,10,15\}\) ist die Wahl von 30 erneut zulässig. Indem er diese Wahl wiederholt, verhindert er, dass \(\mathcal B\) jemals 1 wählen kann.
Umgekehrt kann \(\mathcal B\) dafür sorgen, dass die aktuelle Zahl stets höchstens 7 ist. Gilt nämlich \(2\le n\le7\), so ist \(m\le49\). Hat \(m\) höchstens zwei verschiedene Primteiler, so gewinnt die vorherige Strategie entweder sofort oder liefert \(n'<n\le7\).
Die einzigen ganzen Zahlen bis 49 mit mindestens drei verschiedenen Primteilern sind 30 und 42. Denn die drei kleinsten Primteiler einer solchen Zahl müssen \(2,3,5\) oder \(2,3,7\) sein: Jedes andere Tripel hat ein Produkt von mindestens \[ \min(2\cdot3\cdot11,\;2\cdot5\cdot7,\;3\cdot5\cdot7)=66. \] Außerdem ist jedes echte Vielfache von 30 oder 42 größer als 49. Für \(m=30\) beziehungsweise \(42\) dividiert Spieler \(\mathcal B\) durch 5 beziehungsweise 7, sodass 6 übrig bleibt.
Somit kann \(\mathcal B\) stets eine Zahl zurückgeben, die höchstens 7 ist, sofern er nicht bereits gewonnen hat. Die anschließend von \(\mathcal A\) gewählten Zahlen sind daher höchstens 49, sodass er niemals 1990 wählen kann. Damit ist bewiesen, dass keiner der beiden Spieler ausgehend von 6 oder 7 einen Gewinn erzwingen kann.
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1990 · Soru 5
Başlangıçta bir \(n_0>1\) tam sayısı veriliyor. \(\mathcal A\) ve \(\mathcal B\) adlı iki oyuncu, aşağıdaki kurallara göre sırayla \(n_1,n_2,n_3,\ldots\) tam sayılarını seçiyor:
\(n_{2k}\) sayısını bilen \(\mathcal A\), \[ n_{2k}\le n_{2k+1}\le n_{2k}^{2} \] koşulunu sağlayan herhangi bir \(n_{2k+1}\) tam sayısı seçer.
\(n_{2k+1}\) sayısını bilen \(\mathcal B\), \[ \frac{n_{2k+1}}{n_{2k+2}} \] oranı bir asal sayının pozitif tam sayı kuvveti olacak şekilde herhangi bir \(n_{2k+2}\) tam sayısı seçer.
\(\mathcal A\) oyuncusu 1990 sayısını seçerek, \(\mathcal B\) oyuncusu ise 1 sayısını seçerek oyunu kazanır. Hangi \(n_0\) değerleri için:
(a) \(\mathcal A\) oyuncusunun bir kazanma stratejisi vardır?
(b) \(\mathcal B\) oyuncusunun bir kazanma stratejisi vardır?
(c) Hiçbir oyuncunun bir kazanma stratejisi yoktur?
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Cevap
(a) Tüm \(n_0\ge8\) tam sayıları.
(b) \(n_0\in\{2,3,4,5\}\).
(c) \(n_0\in\{6,7\}\).
Çözüm
\(\mathcal A\) oyuncusunun bir hamlesinden önceki sayıyı \(n\), seçtiği sayıyı ise \(m\) ile gösterelim. Böylece \(n\le m\le n^2\) olur ve \(\mathcal B\), \(p\) asal, \(a\ge1\) ve \(p^a\mid m\) olmak üzere \(m\) sayısını \(m/p^a\) ile değiştirmelidir.
\(8\le n_0\le1990\) iken \(\mathcal A\) için kazanma stratejisi. Aşağıdaki tabloyu kullanalım:
| Mevcut \(n\) | \(\mathcal A\) oyuncusunun seçimi | \(\mathcal B\) oyuncusunun tüm olası yanıtları |
|---|---|---|
| \(45\le n\le1990\) | \(1990\) | \(\mathcal A\) hemen kazanır |
| \(21\le n\le44\) | \(420\) | \(60,84,105,140,210\) |
| \(15\le n\le20\) | \(210\) | \(30,42,70,105\) |
| \(11\le n\le14\) | \(105\) | \(15,21,35\) |
| \(8\le n\le10\) | \(60\) | \(12,15,20,30\) |
Her seçim kurallara uygundur: seçilen sayı, bulunduğu aralığın üst ucundan küçük değildir ve alt ucunun karesinden büyük değildir. Yanıt listeleri doğrudan \[ 420=2^2\cdot3\cdot5\cdot7,\qquad 210=2\cdot3\cdot5\cdot7,\qquad 105=3\cdot5\cdot7,\qquad 60=2^2\cdot3\cdot5 \] asal çarpanlara ayrılışlarından elde edilir. Bir satırdaki her yanıt daha önceki bir satıra aittir. Dolayısıyla \(\mathcal A\) ilk satıra ulaşır ve en fazla beş hamlesinin sonunda kazanır.
\(n_0>1990\) iken \(\mathcal A\) için kazanma stratejisi. \(n>1990\) olduğu sürece \[ m=60\left\lceil\frac n{60}\right\rceil \] seçilsin. Bu seçim kurallara uygundur, çünkü \[ n\le m<n+60<2n\le n^2. \]
\(\mathcal B\) oyuncusunun yanıtı \(n'=m/p^a\) olsun. \(60\mid m\) olduğundan:
- \(p=2\) ise \(15\mid n'\);
- \(p=3\) ise \(20\mid n'\);
- \(p=5\) ise \(12\mid n'\);
- diğer durumlarda \(60\mid n'\).
Sonuç olarak, \[ 12\le n'\le\frac m2<n. \] Böylece \(\mathcal B\) kazanamaz ve mevcut sayı 1990'dan büyük olduğu sürece kesin olarak azalır. Sonlu sayıda turun ardından 12 ile 1990 arasında bir değer alır; bu durumda tablo \(\mathcal A\) için bir kazanma stratejisi verir.
\(2\le n_0\le5\) iken \(\mathcal B\) için kazanma stratejisi. Mevcut sayının \(2\le n\le5\) koşulunu sağladığını varsayalım. O zaman \[ 2\le m\le n^2\le25 \] olur. \(2\cdot3\cdot5=30>25\) olduğundan \(m\) sayısının en fazla iki farklı asal böleni vardır.
\(m\) bir asal sayının kuvveti ise \(\mathcal B\), 1 sayısını seçer ve kazanır. Aksi takdirde, \(p,q\) farklı asal sayılar ve \(a,b\) pozitif tam sayılar olmak üzere \[ m=p^a q^b \] yazalım. \(\mathcal B\) oyuncusu \(p^a,q^b\) sayılarından büyük olanına böler ve geriye \[ n'=\min(p^a,q^b)<\sqrt m\le n \] kalır. Farklı asal sayıların kuvvetleri eşit olamayacağından kesin eşitsizlik geçerlidir.
Bu strateji, \(\mathcal B\) oyuncusu 1 sayısını seçene kadar her turun sonunda pozitif tam sayı \(n\) değerini kesin olarak azaltır. Süreç boyunca \(\mathcal A\) oyuncusunun seçimleri en fazla 25 olduğundan, önce o kazanamaz.
\(n_0=6\) veya \(7\) iken hiçbir oyuncunun kazanma stratejisi yoktur. Her oyuncu için diğerinin kazanmasını önleyen bir strateji vereceğiz.
\(\mathcal A\) oyuncusu her zaman 30 sayısını seçebilir. Bu seçim başlangıçta kurallara uygundur ve \(\mathcal B\) oyuncusunun olası yanıtları yalnızca \[ 30/2=15,\qquad30/3=10,\qquad30/5=6 \] olur. Her \(n\in\{6,10,15\}\) için 30 seçimi yine kurallara uygundur. Bu seçimi tekrarlamak, \(\mathcal B\) oyuncusunun hiçbir zaman 1 sayısını seçememesini sağlar.
Diğer yandan, \(\mathcal B\) mevcut sayıyı en fazla 7 olarak tutabilir. Gerçekten, \(2\le n\le7\) ise \(m\le49\) olur. \(m\) sayısının en fazla iki farklı asal böleni varsa, önceki strateji ya hemen kazandırır ya da \(n'<n\le7\) verir.
En fazla 49 olan ve en az üç farklı asal böleni bulunan tam sayılar yalnızca 30 ve 42'dir. Bunu görmek için, bu bölenlerin en küçük üçünün \(2,3,5\) veya \(2,3,7\) olması gerektiğine dikkat edelim: diğer her üçlünün çarpımı en az \[ \min(2\cdot3\cdot11,\;2\cdot5\cdot7,\;3\cdot5\cdot7)=66 \] olur. Ayrıca, 30 veya 42'nin kendisinden büyük her pozitif katı 49'u aşar. \(m=30\) veya \(42\) için \(\mathcal B\) oyuncusu sırasıyla 5 veya 7'ye böler ve geriye 6 kalır.
Dolayısıyla \(\mathcal B\), daha önce kazanmış olmadığı sürece, her zaman en fazla 7 olan bir sayı bırakabilir. Bu nedenle \(\mathcal A\) oyuncusunun sonraki seçimleri en fazla 49 olur ve hiçbir zaman 1990 sayısını seçemez. Bu, 6 veya 7'den başlandığında hiçbir oyuncunun kazanmayı garantileyemeyeceğini kanıtlar.
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1990 · Problema 5
Dado un entero inicial \(n_0>1\), dos jugadores, \(\mathcal A\) y \(\mathcal B\), eligen enteros \(n_1,n_2,n_3,\ldots\) alternativamente según las siguientes reglas:
Conocido \(n_{2k}\), \(\mathcal A\) elige cualquier entero \(n_{2k+1}\) tal que \[ n_{2k}\le n_{2k+1}\le n_{2k}^{2}. \]
Conocido \(n_{2k+1}\), \(\mathcal B\) elige cualquier entero \(n_{2k+2}\) tal que \[ \frac{n_{2k+1}}{n_{2k+2}} \] sea un primo elevado a una potencia entera positiva.
El jugador \(\mathcal A\) gana la partida al elegir el número 1990; el jugador \(\mathcal B\) gana al elegir el número 1. ¿Para qué valores de \(n_0\) se cumple que:
(a) \(\mathcal A\) tiene una estrategia ganadora?
(b) \(\mathcal B\) tiene una estrategia ganadora?
(c) Ninguno de los jugadores tiene una estrategia ganadora?
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Respuesta
(a) Todos los enteros \(n_0\ge8\).
(b) \(n_0\in\{2,3,4,5\}\).
(c) \(n_0\in\{6,7\}\).
Solución
Denotemos por \(n\) el número anterior a un turno de \(\mathcal A\), y por \(m\) el número que elige. Así, \(n\le m\le n^2\), y \(\mathcal B\) debe sustituir \(m\) por \(m/p^a\), donde \(p\) es primo, \(a\ge1\) y \(p^a\mid m\).
Estrategia ganadora para \(\mathcal A\) cuando \(8\le n_0\le1990\). Utilicemos la siguiente tabla:
| \(n\) actual | \(\mathcal A\) elige | Todas las respuestas posibles de \(\mathcal B\) |
|---|---|---|
| \(45\le n\le1990\) | \(1990\) | \(\mathcal A\) gana inmediatamente |
| \(21\le n\le44\) | \(420\) | \(60,84,105,140,210\) |
| \(15\le n\le20\) | \(210\) | \(30,42,70,105\) |
| \(11\le n\le14\) | \(105\) | \(15,21,35\) |
| \(8\le n\le10\) | \(60\) | \(12,15,20,30\) |
Cada elección es válida: es al menos el extremo superior de su intervalo y a lo sumo el cuadrado del extremo inferior. Las listas de respuestas se deducen directamente de las factorizaciones en primos \[ 420=2^2\cdot3\cdot5\cdot7,\qquad 210=2\cdot3\cdot5\cdot7,\qquad 105=3\cdot5\cdot7,\qquad 60=2^2\cdot3\cdot5. \] Cada respuesta de una fila pertenece a una fila anterior. Por tanto, \(\mathcal A\) alcanza la primera fila y gana en a lo sumo cinco de sus turnos.
Estrategia ganadora para \(\mathcal A\) cuando \(n_0>1990\). Siempre que \(n>1990\), elige \[ m=60\left\lceil\frac n{60}\right\rceil. \] Esta elección es válida porque \[ n\le m<n+60<2n\le n^2. \]
Sea \(n'=m/p^a\) la respuesta de \(\mathcal B\). Como \(60\mid m\):
- si \(p=2\), entonces \(15\mid n'\);
- si \(p=3\), entonces \(20\mid n'\);
- si \(p=5\), entonces \(12\mid n'\);
- en caso contrario, \(60\mid n'\).
En consecuencia, \[ 12\le n'\le\frac m2<n. \] Así pues, \(\mathcal B\) no puede ganar, y el número actual disminuye estrictamente siempre que supera 1990. Tras un número finito de rondas queda entre 12 y 1990, donde la tabla proporciona una estrategia ganadora para \(\mathcal A\).
Estrategia ganadora para \(\mathcal B\) cuando \(2\le n_0\le5\). Supongamos que el número actual satisface \(2\le n\le5\). Entonces \[ 2\le m\le n^2\le25. \] Como \(2\cdot3\cdot5=30>25\), el número \(m\) tiene a lo sumo dos divisores primos distintos.
Si \(m\) es una potencia de un primo, \(\mathcal B\) elige 1 y gana. En caso contrario, escribamos \[ m=p^a q^b \] con primos distintos \(p,q\) y enteros positivos \(a,b\). El jugador \(\mathcal B\) divide por el mayor de \(p^a,q^b\), dejando \[ n'=\min(p^a,q^b)<\sqrt m\le n. \] La desigualdad estricta se cumple porque las potencias de primos distintos no pueden ser iguales.
Esta estrategia hace disminuir estrictamente el entero positivo \(n\) después de cada ronda hasta que \(\mathcal B\) elige 1. Durante toda la partida, las elecciones de \(\mathcal A\) son a lo sumo 25, por lo que no puede ganar antes.
Ninguno de los jugadores tiene una estrategia ganadora cuando \(n_0=6\) o \(7\). Daremos a cada jugador una estrategia que impide que el otro gane.
El jugador \(\mathcal A\) puede elegir siempre 30. Esta elección es válida inicialmente, y las únicas respuestas de \(\mathcal B\) son \[ 30/2=15,\qquad30/3=10,\qquad30/5=6. \] Para cada \(n\in\{6,10,15\}\), la elección de 30 vuelve a ser válida. Repetirla impide que \(\mathcal B\) llegue a elegir 1.
Por otra parte, \(\mathcal B\) puede mantener el número actual a lo sumo en 7. En efecto, si \(2\le n\le7\), entonces \(m\le49\). Si \(m\) tiene a lo sumo dos divisores primos distintos, la estrategia anterior permite ganar inmediatamente o da \(n'<n\le7\).
Los únicos enteros que no superan 49 y tienen al menos tres divisores primos distintos son 30 y 42. Para verlo, los tres menores de esos divisores deben ser \(2,3,5\) o \(2,3,7\): cualquier otra terna tiene un producto de al menos \[ \min(2\cdot3\cdot11,\;2\cdot5\cdot7,\;3\cdot5\cdot7)=66. \] Además, cualquier múltiplo propio de 30 o de 42 supera 49. Para \(m=30\) o \(42\), el jugador \(\mathcal B\) divide por 5 o por 7, respectivamente, dejando 6.
Por tanto, \(\mathcal B\) siempre puede devolver un número a lo sumo igual a 7, salvo que ya haya ganado. Las elecciones posteriores del jugador \(\mathcal A\) son, por tanto, a lo sumo 49, de modo que nunca puede elegir 1990. Esto demuestra que ninguno de los jugadores puede forzar una victoria partiendo de 6 o de 7.
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1990 · 问题 5
给定初始整数 \(n_0>1\)，两名选手 \(\mathcal A\) 和 \(\mathcal B\) 按照以下规则交替选择整数 \(n_1,n_2,n_3,\ldots\)：
已知 \(n_{2k}\)，\(\mathcal A\) 选择任意整数 \(n_{2k+1}\)，使得 \[ n_{2k}\le n_{2k+1}\le n_{2k}^{2}. \]
已知 \(n_{2k+1}\)，\(\mathcal B\) 选择任意整数 \(n_{2k+2}\)，使得 \[ \frac{n_{2k+1}}{n_{2k+2}} \] 是某个素数的正整数次幂。
选手 \(\mathcal A\) 选出数 1990 时获胜；选手 \(\mathcal B\) 选出数 1 时获胜。对于哪些 \(n_0\)，有：
(a) \(\mathcal A\) 有必胜策略？
(b) \(\mathcal B\) 有必胜策略？
(c) 双方都没有必胜策略？
题目译自官方英文原文。 官方试卷 (PDF)
答案
(a) 所有整数 \(n_0\ge8\)。
(b) \(n_0\in\{2,3,4,5\}\)。
(c) \(n_0\in\{6,7\}\)。
解答
用 \(n\) 表示轮到 \(\mathcal A\) 行动前的数，用 \(m\) 表示其选择的数。于是 \(n\le m\le n^2\)，且 \(\mathcal B\) 必须将 \(m\) 替换为 \(m/p^a\)，其中 \(p\) 为素数，\(a\ge1\)，且 \(p^a\mid m\)。
当 \(8\le n_0\le1990\) 时，\(\mathcal A\) 的必胜策略。 使用下表：
| 当前的 \(n\) | \(\mathcal A\) 的选择 | \(\mathcal B\) 所有可能的应对 |
|---|---|---|
| \(45\le n\le1990\) | \(1990\) | \(\mathcal A\) 立即获胜 |
| \(21\le n\le44\) | \(420\) | \(60,84,105,140,210\) |
| \(15\le n\le20\) | \(210\) | \(30,42,70,105\) |
| \(11\le n\le14\) | \(105\) | \(15,21,35\) |
| \(8\le n\le10\) | \(60\) | \(12,15,20,30\) |
每个选择都符合规则：所选的数不小于对应区间的上端点，且不大于下端点的平方。由素因数分解 \[ 420=2^2\cdot3\cdot5\cdot7,\qquad 210=2\cdot3\cdot5\cdot7,\qquad 105=3\cdot5\cdot7,\qquad 60=2^2\cdot3\cdot5. \] 可直接得到表中列出的所有应对。每一行中的每个应对所得的数都属于更靠前的一行。因此，\(\mathcal A\) 最多行动五次，就能到达第一行并获胜。
当 \(n_0>1990\) 时，\(\mathcal A\) 的必胜策略。 只要 \(n>1990\)，就选择 \[ m=60\left\lceil\frac n{60}\right\rceil. \] 这一选择符合规则，因为 \[ n\le m<n+60<2n\le n^2. \]
设 \(\mathcal B\) 应对后所得的数为 \(n'=m/p^a\)。由于 \(60\mid m\)：
- 若 \(p=2\)，则 \(15\mid n'\)；
- 若 \(p=3\)，则 \(20\mid n'\)；
- 若 \(p=5\)，则 \(12\mid n'\)；
- 否则，\(60\mid n'\)。
因此， \[ 12\le n'\le\frac m2<n. \] 所以 \(\mathcal B\) 无法获胜，而且只要当前的数大于 1990，它就会严格减小。经过有限轮后，这个数将落在 12 与 1990 之间，此时上表给出了 \(\mathcal A\) 的必胜策略。
当 \(2\le n_0\le5\) 时，\(\mathcal B\) 的必胜策略。 假设当前的数满足 \(2\le n\le5\)。则 \[ 2\le m\le n^2\le25. \] 由于 \(2\cdot3\cdot5=30>25\)，数 \(m\) 至多有两个不同的素因子。
若 \(m\) 是素数幂，则 \(\mathcal B\) 选择 1 并获胜。否则，写成 \[ m=p^a q^b \] 其中 \(p,q\) 为不同的素数，\(a,b\) 为正整数。选手 \(\mathcal B\) 用 \(p^a,q^b\) 中较大的一个去除 \(m\)，得到 \[ n'=\min(p^a,q^b)<\sqrt m\le n. \] 严格不等号成立，是因为不同素数的正整数次幂不可能相等。
这一策略使正整数 \(n\) 在每轮之后都严格减小，直到 \(\mathcal B\) 选择 1 为止。在整个过程中，\(\mathcal A\) 所选的数均不超过 25，因此无法先行获胜。
当 \(n_0=6\) 或 \(7\) 时，双方都没有必胜策略。 我们分别给出双方阻止对方获胜的策略。
选手 \(\mathcal A\) 可以始终选择 30。初次这样选择符合规则，而 \(\mathcal B\) 仅有的应对为 \[ 30/2=15,\qquad30/3=10,\qquad30/5=6. \] 对于每个 \(n\in\{6,10,15\}\)，再次选择 30 仍然符合规则。反复这样选择，就能使 \(\mathcal B\) 永远无法选择 1。
反过来，\(\mathcal B\) 可以使当前的数始终不超过 7。事实上，若 \(2\le n\le7\)，则 \(m\le49\)。若 \(m\) 至多有两个不同的素因子，则前述策略要么使其立即获胜，要么得到 \(n'<n\le7\)。
不超过 49 且至少有三个不同素因子的整数只有 30 和 42。为说明这一点，注意其中最小的三个素因子必为 \(2,3,5\) 或 \(2,3,7\)：其他任意三元组的乘积至少为 \[ \min(2\cdot3\cdot11,\;2\cdot5\cdot7,\;3\cdot5\cdot7)=66. \] 此外，30 或 42 的任何大于自身的正整数倍都超过 49。对于 \(m=30\) 或 \(42\)，选手 \(\mathcal B\) 分别除以 5 或 7，得到 6。
因此，除非 \(\mathcal B\) 已经获胜，否则总能在应对后得到一个不超过 7 的数。于是选手 \(\mathcal A\) 此后所选的数均不超过 49，因此永远无法选择 1990。这就证明了从 6 或 7 出发，双方都无法确保获胜。
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1990 · Задача 5
Дано начальное целое число \(n_0>1\). Два игрока, \(\mathcal A\) и \(\mathcal B\), поочерёдно выбирают целые числа \(n_1,n_2,n_3,\ldots\) по следующим правилам:
Зная \(n_{2k}\), игрок \(\mathcal A\) выбирает любое целое число \(n_{2k+1}\), такое что \[ n_{2k}\le n_{2k+1}\le n_{2k}^{2}. \]
Зная \(n_{2k+1}\), игрок \(\mathcal B\) выбирает любое целое число \(n_{2k+2}\), такое что \[ \frac{n_{2k+1}}{n_{2k+2}} \] является натуральной степенью простого числа.
Игрок \(\mathcal A\) выигрывает, выбрав число 1990; игрок \(\mathcal B\) выигрывает, выбрав число 1. При каких \(n_0\):
(a) у \(\mathcal A\) есть выигрышная стратегия?
(b) у \(\mathcal B\) есть выигрышная стратегия?
(c) ни у одного из игроков нет выигрышной стратегии?
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Ответ
(a) Все целые числа \(n_0\ge8\).
(b) \(n_0\in\{2,3,4,5\}\).
(c) \(n_0\in\{6,7\}\).
Решение
Обозначим через \(n\) число перед ходом \(\mathcal A\), а через \(m\) — число, которое этот игрок выбирает. Тогда \(n\le m\le n^2\), а \(\mathcal B\) должен заменить \(m\) на \(m/p^a\), где \(p\) — простое число, \(a\ge1\) и \(p^a\mid m\).
Выигрышная стратегия для \(\mathcal A\) при \(8\le n_0\le1990\). Воспользуемся следующей таблицей:
| Текущее \(n\) | Выбор \(\mathcal A\) | Все возможные ответы \(\mathcal B\) |
|---|---|---|
| \(45\le n\le1990\) | \(1990\) | \(\mathcal A\) немедленно выигрывает |
| \(21\le n\le44\) | \(420\) | \(60,84,105,140,210\) |
| \(15\le n\le20\) | \(210\) | \(30,42,70,105\) |
| \(11\le n\le14\) | \(105\) | \(15,21,35\) |
| \(8\le n\le10\) | \(60\) | \(12,15,20,30\) |
Каждый выбор допустим: выбранное число не меньше верхней границы своего промежутка и не больше квадрата нижней границы. Списки ответов непосредственно следуют из разложений на простые множители \[ 420=2^2\cdot3\cdot5\cdot7,\qquad 210=2\cdot3\cdot5\cdot7,\qquad 105=3\cdot5\cdot7,\qquad 60=2^2\cdot3\cdot5. \] Каждый ответ в строке принадлежит промежутку из одной из предыдущих строк. Поэтому \(\mathcal A\) достигает первой строки и выигрывает не более чем за пять своих ходов.
Выигрышная стратегия для \(\mathcal A\) при \(n_0>1990\). Всякий раз, когда \(n>1990\), выбираем \[ m=60\left\lceil\frac n{60}\right\rceil. \] Этот выбор допустим, поскольку \[ n\le m<n+60<2n\le n^2. \]
Пусть ответ \(\mathcal B\) равен \(n'=m/p^a\). Так как \(60\mid m\):
- если \(p=2\), то \(15\mid n'\);
- если \(p=3\), то \(20\mid n'\);
- если \(p=5\), то \(12\mid n'\);
- в остальных случаях \(60\mid n'\).
Следовательно, \[ 12\le n'\le\frac m2<n. \] Таким образом, \(\mathcal B\) не может выиграть, а текущее число строго уменьшается, пока оно больше 1990. Через конечное число раундов оно окажется между 12 и 1990, где таблица даёт \(\mathcal A\) выигрышную стратегию.
Выигрышная стратегия для \(\mathcal B\) при \(2\le n_0\le5\). Предположим, что текущее число удовлетворяет условию \(2\le n\le5\). Тогда \[ 2\le m\le n^2\le25. \] Поскольку \(2\cdot3\cdot5=30>25\), число \(m\) имеет не более двух различных простых делителей.
Если \(m\) — степень простого числа, то \(\mathcal B\) выбирает 1 и выигрывает. В противном случае запишем \[ m=p^a q^b \] где \(p,q\) — различные простые числа, а \(a,b\) — положительные целые числа. Игрок \(\mathcal B\) делит на большее из чисел \(p^a,q^b\), оставляя \[ n'=\min(p^a,q^b)<\sqrt m\le n. \] Неравенство строгое, поскольку степени различных простых чисел не могут быть равны.
При этой стратегии положительное целое число \(n\) строго уменьшается после каждого раунда, пока \(\mathcal B\) не выберет 1. На протяжении всей игры числа, выбираемые \(\mathcal A\), не превосходят 25, поэтому этот игрок не может выиграть раньше.
Ни у одного из игроков нет выигрышной стратегии при \(n_0=6\) или \(7\). Укажем для каждого игрока стратегию, не позволяющую другому выиграть.
Игрок \(\mathcal A\) может всегда выбирать 30. Вначале этот выбор допустим, а единственные ответы \(\mathcal B\) таковы: \[ 30/2=15,\qquad30/3=10,\qquad30/5=6. \] Для каждого \(n\in\{6,10,15\}\) выбор 30 снова допустим. Повторяя его, игрок \(\mathcal A\) не позволяет \(\mathcal B\) когда-либо выбрать 1.
С другой стороны, \(\mathcal B\) может поддерживать текущее число не превосходящим 7. Действительно, если \(2\le n\le7\), то \(m\le49\). Если \(m\) имеет не более двух различных простых делителей, то предыдущая стратегия либо даёт немедленную победу, либо приводит к \(n'<n\le7\).
Единственные целые числа, не превосходящие 49 и имеющие не менее трёх различных простых делителей, — это 30 и 42. Чтобы убедиться в этом, заметим, что три наименьших таких делителя должны быть \(2,3,5\) или \(2,3,7\): произведение любой другой тройки не меньше \[ \min(2\cdot3\cdot11,\;2\cdot5\cdot7,\;3\cdot5\cdot7)=66. \] Кроме того, любое кратное 30 или 42, большее самого этого числа, превосходит 49. При \(m=30\) или \(42\) игрок \(\mathcal B\) делит на 5 или 7 соответственно, оставляя 6.
Значит, \(\mathcal B\) всегда может вернуть число, не превосходящее 7, если ещё не выиграл. Поэтому последующие числа, выбираемые \(\mathcal A\), не превосходят 49, и этот игрок никогда не сможет выбрать 1990. Тем самым доказано, что при начальном числе 6 или 7 ни один из игроков не может гарантировать себе победу.
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1990 · المسألة 5
انطلاقًا من عدد صحيح معطى \(n_0>1\)، يختار لاعبان، \(\mathcal A\) و\(\mathcal B\)، أعدادًا صحيحة \(n_1,n_2,n_3,\ldots\) بالتناوب وفق القواعد الآتية:
بمعرفة \(n_{2k}\)، يختار \(\mathcal A\) أي عدد صحيح \(n_{2k+1}\) بحيث \[ n_{2k}\le n_{2k+1}\le n_{2k}^{2}. \]
بمعرفة \(n_{2k+1}\)، يختار \(\mathcal B\) أي عدد صحيح \(n_{2k+2}\) بحيث يكون \[ \frac{n_{2k+1}}{n_{2k+2}} \] قوة لعدد أولي ذات أس صحيح موجب.
يفوز اللاعب \(\mathcal A\) باللعبة باختيار العدد 1990؛ ويفوز اللاعب \(\mathcal B\) باختيار العدد 1. لأي قيم \(n_0\):
(a) يمتلك \(\mathcal A\) استراتيجية فوز؟
(b) يمتلك \(\mathcal B\) استراتيجية فوز؟
(c) لا يمتلك أي من اللاعبين استراتيجية فوز؟
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الإجابة
(a) جميع الأعداد الصحيحة \(n_0\ge8\).
(b) \(n_0\in\{2,3,4,5\}\).
(c) \(n_0\in\{6,7\}\).
الحل
لنرمز بـ \(n\) إلى العدد قبل دور اللاعب \(\mathcal A\)، وبـ \(m\) إلى العدد الذي يختاره. إذن \(n\le m\le n^2\)، وعلى \(\mathcal B\) أن يستبدل \(m\) بالعدد \(m/p^a\)، حيث \(p\) أولي، و\(a\ge1\)، و\(p^a\mid m\).
استراتيجية فوز للاعب \(\mathcal A\) عندما \(8\le n_0\le1990\). نستخدم الجدول الآتي:
| العدد الحالي \(n\) | اختيار \(\mathcal A\) | جميع الردود الممكنة للاعب \(\mathcal B\) |
|---|---|---|
| \(45\le n\le1990\) | \(1990\) | يفوز \(\mathcal A\) فورًا |
| \(21\le n\le44\) | \(420\) | \(60,84,105,140,210\) |
| \(15\le n\le20\) | \(210\) | \(30,42,70,105\) |
| \(11\le n\le14\) | \(105\) | \(15,21,35\) |
| \(8\le n\le10\) | \(60\) | \(12,15,20,30\) |
كل اختيار مسموح به: فهو لا يقل عن الطرف الأعلى للفترة المقابلة له ولا يزيد على مربع طرفها الأدنى. وتنتج قوائم الردود مباشرة من التحليلات إلى عوامل أولية \[ 420=2^2\cdot3\cdot5\cdot7,\qquad 210=2\cdot3\cdot5\cdot7,\qquad 105=3\cdot5\cdot7,\qquad 60=2^2\cdot3\cdot5. \] كل رد في أحد الصفوف ينتمي إلى صف سابق. لذلك يصل \(\mathcal A\) إلى الصف الأول ويفوز بعد خمسة أدوار له على الأكثر.
استراتيجية فوز للاعب \(\mathcal A\) عندما \(n_0>1990\). كلما كان \(n>1990\)، يختار \[ m=60\left\lceil\frac n{60}\right\rceil. \] هذا الاختيار مسموح به لأن \[ n\le m<n+60<2n\le n^2. \]
ليكن رد \(\mathcal B\) هو \(n'=m/p^a\). بما أن \(60\mid m\):
- إذا كان \(p=2\)، فإن \(15\mid n'\)؛
- إذا كان \(p=3\)، فإن \(20\mid n'\)؛
- إذا كان \(p=5\)، فإن \(12\mid n'\)؛
- فيما عدا ذلك، \(60\mid n'\).
وبالتالي، \[ 12\le n'\le\frac m2<n. \] إذن لا يستطيع \(\mathcal B\) الفوز، ويتناقص العدد الحالي تناقصًا صارمًا كلما تجاوز 1990. وبعد عدد منتهٍ من الجولات، يقع بين 12 و1990، حيث يعطي الجدول للاعب \(\mathcal A\) استراتيجية فوز.
استراتيجية فوز للاعب \(\mathcal B\) عندما \(2\le n_0\le5\). لنفترض أن العدد الحالي يحقق \(2\le n\le5\). عندئذ \[ 2\le m\le n^2\le25. \] بما أن \(2\cdot3\cdot5=30>25\)، فإن للعدد \(m\) قاسمين أوليين متميزين على الأكثر.
إذا كان \(m\) قوة لعدد أولي، يختار \(\mathcal B\) العدد 1 ويفوز. وإلا نكتب \[ m=p^a q^b \] حيث \(p,q\) عددان أوليان متميزان و\(a,b\) عددان صحيحان موجبان. يقسم اللاعب \(\mathcal B\) على الأكبر من \(p^a,q^b\)، فيتبقى \[ n'=\min(p^a,q^b)<\sqrt m\le n. \] تتحقق المتباينة الصارمة لأن قوتين لعددين أوليين متميزين لا يمكن أن تتساويا.
تجعل هذه الاستراتيجية العدد الصحيح الموجب \(n\) يتناقص تناقصًا صارمًا بعد كل جولة حتى يختار \(\mathcal B\) العدد 1. وطوال اللعب، لا تتجاوز اختيارات \(\mathcal A\) العدد 25، ولذلك لا يمكنه أن يفوز أولًا.
لا يمتلك أي من اللاعبين استراتيجية فوز عندما \(n_0=6\) أو \(7\). نعطي لكل لاعب استراتيجية تمنع الآخر من الفوز.
يمكن للاعب \(\mathcal A\) أن يختار العدد 30 دائمًا. هذا الاختيار مسموح به في البداية، والردود الوحيدة للاعب \(\mathcal B\) هي \[ 30/2=15,\qquad30/3=10,\qquad30/5=6. \] ولكل \(n\in\{6,10,15\}\)، يكون اختيار 30 مسموحًا به مرة أخرى. ويمنع تكراره اللاعب \(\mathcal B\) من اختيار 1 في أي وقت.
وبالمقابل، يستطيع \(\mathcal B\) إبقاء العدد الحالي عند 7 على الأكثر. بالفعل، إذا كان \(2\le n\le7\)، فإن \(m\le49\). وإذا كان للعدد \(m\) قاسمان أوليان متميزان على الأكثر، فإن الاستراتيجية السابقة إما تحقق الفوز فورًا أو تعطي \(n'<n\le7\).
العددان الصحيحان الوحيدان اللذان لا يتجاوزان 49 ولهما ثلاثة قواسم أولية متميزة على الأقل هما 30 و42. ولإثبات ذلك، لا بد أن تكون أصغر ثلاثة من هذه القواسم هي \(2,3,5\) أو \(2,3,7\): فكل ثلاثية أخرى حاصل ضربها لا يقل عن \[ \min(2\cdot3\cdot11,\;2\cdot5\cdot7,\;3\cdot5\cdot7)=66. \] علاوة على ذلك، فإن أي مضاعف للعدد 30 أو 42 أكبر من العدد نفسه يتجاوز 49. عندما \(m=30\) أو \(42\)، يقسم اللاعب \(\mathcal B\) على 5 أو 7، على الترتيب، فيتبقى 6.
ومن ثم يستطيع \(\mathcal B\) دائمًا أن يعيد عددًا لا يتجاوز 7، ما لم يكن قد فاز بالفعل. لذلك لا تتجاوز اختيارات اللاعب \(\mathcal A\) اللاحقة العدد 49، فلا يستطيع أبدًا اختيار 1990. وهذا يثبت أن أيًّا من اللاعبين لا يستطيع ضمان الفوز انطلاقًا من 6 أو 7.
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).