IMO 1992 · Problem 6
For each positive integer \(n\), \(S(n)\) is defined to be the greatest integer such that, for every positive integer \(k \le S(n)\), \(n^2\) can be written as the sum of \(k\) positive squares.
(a) Prove that \(S(n) \le n^2 - 14\) for each \(n \ge 4\).
(b) Find an integer \(n\) such that \(S(n) = n^2 - 14\).
(c) Prove that there are infinitely many integers \(n\) such that \(S(n) = n^2 - 14\).
Official text of the problem. Official problem paper (PDF)
Answer
For (b), \(n=13\) works: \(S(13)=155\).
For (c), every \(n=13\cdot 2^t\), where \(t\) is a nonnegative integer, satisfies \(S(n)=n^2-14\).
Solution
All squares below are squares of positive integers.
(a) Suppose \(n^2\) were a sum of \(n^2-13\) positive squares: \[ n^2=a_1^2+\cdots+a_{n^2-13}^2. \] Subtracting the number of summands gives \[ 13=\sum_{i=1}^{n^2-13}(a_i^2-1). \] Each summand on the right belongs to \[ \{0,3,8,15,24,\ldots\}. \] Thus \(13=3u+8v\) for some nonnegative integers \(u,v\). Necessarily \(v=0\) or \(v=1\), but neither \(13\) nor \(13-8=5\) is divisible by \(3\). This is impossible.
For \(n\ge4\), the integer \(n^2-13\) is positive, so its failure implies \[ \boxed{S(n)\le n^2-14}. \]
To construct examples attaining this bound, we first prove an elementary lemma.
Lemma. If positive integers \(N,k\) satisfy \[ N-k\ge14 \qquad\text{and}\qquad 9k\ge N+35, \] then \(N\) is a sum of exactly \(k\) positive squares.
Proof. Put \(d=N-k\). Since \(3\) is relatively prime to \(8\), there is an integer \(a\in\{0,1,\ldots,7\}\) such that \(3a\equiv d\pmod8\). Write \[ d=3a+8b. \] Here \(b\) is an integer, and it is nonnegative: otherwise \[ d\le3\cdot7-8=13, \] contrary to \(d\ge14\). Moreover, \[ a+b=\frac{d+5a}{8} \le\frac{N-k+35}{8} \le k. \] Consequently, \[ N= \underbrace{2^2+\cdots+2^2}_{a\text{ terms}} +\underbrace{3^2+\cdots+3^2}_{b\text{ terms}} +\underbrace{1^2+\cdots+1^2}_{k-a-b\text{ terms}}, \] as required. A group containing zero terms is simply omitted. \(\square\)
(b) We show that \(169=13^2\) is a sum of \(k\) positive squares for every \(1\le k\le155\).
For \(23\le k\le155\), the lemma applies, because \[ 169-k\ge14, \qquad 9k\ge207\ge169+35. \]
It remains to handle \(1\le k\le22\). The cases \(k=1,2\) follow from \[ 169=13^2=12^2+5^2. \] For the other cases, use the following operation: whenever an even square occurs, replace it by four equal squares, \[ (2u)^2=u^2+u^2+u^2+u^2. \] Each operation increases the number of summands by exactly \(3\).
Starting from the identities in the table, repeatedly apply this operation to the indicated squares, stopping at any intermediate stage.
| Initial representation of \(169\) | Squares to split completely | Numbers of summands obtained |
|---|---|---|
| \(12^2+4^2+3^2\) | \(12^2\) into sixteen \(3^2\)'s, and \(4^2\) into sixteen \(1^2\)'s | \(3,6,9,\ldots,33\) |
| \(10^2+8^2+2^2+1^2\) | \(8^2\) into sixty-four \(1^2\)'s | \(4,7,10,\ldots,67\) |
| \(12^2+4^2+2^2+2^2+1^2\) | \(4^2\) into sixteen \(1^2\)'s | \(5,8,11,\ldots,20\) |
Every intermediate number listed occurs because each individual split adds exactly three summands. These three progressions cover every integer from \(3\) through \(22\).
Thus every \(k\le155\) is possible. Together with part (a), this proves \[ \boxed{S(13)=155=13^2-14}. \]
(c) We prove that whenever \(n\ge13\) satisfies \[ S(n)=n^2-14, \] the integer \(2n\) also attains the bound.
Write \(m=n^2\), so \(m\ge169\). For every \[ 1\le k\le m-14, \] there is a representation \[ m=a_1^2+\cdots+a_k^2. \] Doubling each base gives \[ 4m=(2a_1)^2+\cdots+(2a_k)^2, \] with the same number of summands.
For the remaining integers \[ m-13\le k\le4m-14, \] we have \(4m-k\ge14\), and \[ 9k\ge9m-117\ge4m+35, \] where the last inequality follows from \(5m\ge152\). The lemma, with \(N=4m\), therefore supplies a representation with exactly \(k\) positive squares.
Hence \(4m=(2n)^2\) has representations for every \(1\le k\le4m-14\). Applying part (a) yields \[ S(2n)=(2n)^2-14. \]
Starting with \(n=13\) and iterating, we obtain \[ \boxed{S(13\cdot2^t)=(13\cdot2^t)^2-14\qquad(t=0,1,2,\ldots)}. \] These integers are distinct, proving that there are infinitely many.
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1992 · Aufgabe 6
Für jede positive ganze Zahl \(n\) sei \(S(n)\) die größte ganze Zahl mit der Eigenschaft, dass sich \(n^2\) für jede positive ganze Zahl \(k \le S(n)\) als Summe von \(k\) positiven Quadratzahlen schreiben lässt.
(a) Beweise, dass \(S(n) \le n^2 - 14\) für jedes \(n \ge 4\) gilt.
(b) Finde eine ganze Zahl \(n\), für die \(S(n) = n^2 - 14\) gilt.
(c) Beweise, dass es unendlich viele ganze Zahlen \(n\) gibt, für die \(S(n) = n^2 - 14\) gilt.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Antwort
Für (b) ist \(n=13\) geeignet: \(S(13)=155\).
Für (c) erfüllt jede Zahl \(n=13\cdot 2^t\), wobei \(t\) eine nichtnegative ganze Zahl ist, die Gleichung \(S(n)=n^2-14\).
Lösung
Alle im Folgenden vorkommenden Quadrate sind Quadrate positiver ganzer Zahlen.
(a) Angenommen, \(n^2\) ließe sich als Summe von \(n^2-13\) positiven Quadratzahlen darstellen: \[ n^2=a_1^2+\cdots+a_{n^2-13}^2. \] Subtrahiert man die Anzahl der Summanden, so erhält man \[ 13=\sum_{i=1}^{n^2-13}(a_i^2-1). \] Jeder Summand auf der rechten Seite gehört zu \[ \{0,3,8,15,24,\ldots\}. \] Somit ist \(13=3u+8v\) für gewisse nichtnegative ganze Zahlen \(u,v\). Notwendigerweise ist \(v=0\) oder \(v=1\), aber weder \(13\) noch \(13-8=5\) ist durch \(3\) teilbar. Dies ist unmöglich.
Für \(n\ge4\) ist die ganze Zahl \(n^2-13\) positiv, also folgt aus der Unmöglichkeit einer solchen Darstellung \[ \boxed{S(n)\le n^2-14}. \]
Um Beispiele zu konstruieren, die diese Schranke erreichen, beweisen wir zunächst einen elementaren Hilfssatz.
Hilfssatz. Erfüllen positive ganze Zahlen \(N,k\) die Bedingungen \[ N-k\ge14 \qquad\text{und}\qquad 9k\ge N+35, \] so ist \(N\) eine Summe von genau \(k\) positiven Quadratzahlen.
Beweis. Setze \(d=N-k\). Da \(3\) und \(8\) teilerfremd sind, gibt es eine ganze Zahl \(a\in\{0,1,\ldots,7\}\) mit \(3a\equiv d\pmod8\). Wir schreiben \[ d=3a+8b. \] Dabei ist \(b\) eine ganze Zahl, und sie ist nichtnegativ: Andernfalls wäre \[ d\le3\cdot7-8=13, \] im Widerspruch zu \(d\ge14\). Außerdem gilt \[ a+b=\frac{d+5a}{8} \le\frac{N-k+35}{8} \le k. \] Folglich ist \[ N= \underbrace{2^2+\cdots+2^2}_{a\text{ Summanden}} +\underbrace{3^2+\cdots+3^2}_{b\text{ Summanden}} +\underbrace{1^2+\cdots+1^2}_{k-a-b\text{ Summanden}}, \] wie gefordert. Eine Gruppe mit null Summanden wird einfach weggelassen. \(\square\)
(b) Wir zeigen, dass \(169=13^2\) für jedes \(1\le k\le155\) eine Summe von \(k\) positiven Quadratzahlen ist.
Für \(23\le k\le155\) ist der Hilfssatz anwendbar, denn \[ 169-k\ge14, \qquad 9k\ge207\ge169+35. \]
Es bleibt, \(1\le k\le22\) zu behandeln. Die Fälle \(k=1,2\) folgen aus \[ 169=13^2=12^2+5^2. \] Für die übrigen Fälle verwenden wir die folgende Operation: Wann immer eine gerade Quadratzahl vorkommt, ersetzen wir sie durch vier gleiche Quadratzahlen, \[ (2u)^2=u^2+u^2+u^2+u^2. \] Jede Operation erhöht die Anzahl der Summanden um genau \(3\).
Ausgehend von den Identitäten in der Tabelle wenden wir diese Operation wiederholt auf die angegebenen Quadratzahlen an und können dabei nach jedem Zwischenschritt aufhören.
| Ausgangsdarstellung von \(169\) | Vollständig zu zerlegende Quadratzahlen | Erhaltene Anzahlen von Summanden |
|---|---|---|
| \(12^2+4^2+3^2\) | \(12^2\) in sechzehn Summanden \(3^2\) und \(4^2\) in sechzehn Summanden \(1^2\) | \(3,6,9,\ldots,33\) |
| \(10^2+8^2+2^2+1^2\) | \(8^2\) in vierundsechzig Summanden \(1^2\) | \(4,7,10,\ldots,67\) |
| \(12^2+4^2+2^2+2^2+1^2\) | \(4^2\) in sechzehn Summanden \(1^2\) | \(5,8,11,\ldots,20\) |
Jede angegebene Zwischenanzahl tritt auf, da jede einzelne Zerlegung genau drei Summanden hinzufügt. Diese drei arithmetischen Folgen decken jede ganze Zahl von \(3\) bis \(22\) ab.
Somit ist jedes \(k\le155\) möglich. Zusammen mit Teil (a) beweist dies \[ \boxed{S(13)=155=13^2-14}. \]
(c) Wir beweisen: Erfüllt \(n\ge13\) die Gleichung \[ S(n)=n^2-14, \] so erreicht auch die ganze Zahl \(2n\) die Schranke.
Setze \(m=n^2\), also ist \(m\ge169\). Für jedes \[ 1\le k\le m-14, \] gibt es eine Darstellung \[ m=a_1^2+\cdots+a_k^2. \] Verdoppelt man jede Basis, so erhält man \[ 4m=(2a_1)^2+\cdots+(2a_k)^2, \] mit derselben Anzahl von Summanden.
Für die verbleibenden ganzen Zahlen \[ m-13\le k\le4m-14, \] gilt \(4m-k\ge14\), und \[ 9k\ge9m-117\ge4m+35, \] wobei die letzte Ungleichung aus \(5m\ge152\) folgt. Der Hilfssatz liefert daher mit \(N=4m\) eine Darstellung als Summe von genau \(k\) positiven Quadratzahlen.
Somit besitzt \(4m=(2n)^2\) für jedes \(1\le k\le4m-14\) eine solche Darstellung. Die Anwendung von Teil (a) ergibt \[ S(2n)=(2n)^2-14. \]
Beginnen wir mit \(n=13\) und wiederholen diesen Schritt, so erhalten wir \[ \boxed{S(13\cdot2^t)=(13\cdot2^t)^2-14\qquad(t=0,1,2,\ldots)}. \] Diese ganzen Zahlen sind paarweise verschieden, womit bewiesen ist, dass es unendlich viele gibt.
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1992 · Soru 6
Her pozitif \(n\) tam sayısı için \(S(n)\), her pozitif \(k \le S(n)\) tam sayısı için \(n^2\) sayısının \(k\) pozitif tam kare toplamı olarak yazılabilmesini sağlayan en büyük tam sayı olarak tanımlanıyor.
(a) Her \(n \ge 4\) için \(S(n) \le n^2 - 14\) olduğunu kanıtlayınız.
(b) \(S(n) = n^2 - 14\) olacak şekilde bir \(n\) tam sayısı bulunuz.
(c) \(S(n) = n^2 - 14\) olacak şekilde sonsuz çoklukta \(n\) tam sayısı bulunduğunu kanıtlayınız.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Cevap
(b) için \(n=13\) uygundur: \(S(13)=155\).
(c) için, \(t\) negatif olmayan bir tam sayı olmak üzere, her \(n=13\cdot 2^t\) sayısı \(S(n)=n^2-14\) eşitliğini sağlar.
Çözüm
Aşağıdaki tüm kareler, pozitif tam sayıların kareleridir.
(a) \(n^2\)'nin \(n^2-13\) pozitif tam karenin toplamı olduğunu varsayalım: \[ n^2=a_1^2+\cdots+a_{n^2-13}^2. \] Her iki taraftan terim sayısını çıkarırsak \[ 13=\sum_{i=1}^{n^2-13}(a_i^2-1). \] Sağdaki her terim \[ \{0,3,8,15,24,\ldots\} \] kümesine aittir. Dolayısıyla negatif olmayan bazı \(u,v\) tam sayıları için \(13=3u+8v\) olur. Zorunlu olarak \(v=0\) veya \(v=1\) olmalıdır, ancak ne \(13\) ne de \(13-8=5\), \(3\)'e bölünür. Bu imkânsızdır.
\(n\ge4\) için \(n^2-13\) tam sayısı pozitiftir; dolayısıyla bu sayıda terimle bir gösterimin mümkün olmaması \[ \boxed{S(n)\le n^2-14} \] sonucunu verir.
Bu sınıra ulaşan örnekler oluşturmak için önce temel bir yardımcı önerme kanıtlayalım.
Yardımcı önerme. Pozitif \(N,k\) tam sayıları \[ N-k\ge14 \qquad\text{ve}\qquad 9k\ge N+35, \] koşullarını sağlıyorsa \(N\), tam olarak \(k\) pozitif tam karenin toplamıdır.
Kanıt. \(d=N-k\) olsun. \(3\) ile \(8\) aralarında asal olduğundan \(3a\equiv d\pmod8\) olacak şekilde bir \(a\in\{0,1,\ldots,7\}\) tam sayısı vardır. \[ d=3a+8b \] yazalım. Burada \(b\) bir tam sayıdır ve negatif değildir: aksi takdirde \[ d\le3\cdot7-8=13, \] olur ve bu, \(d\ge14\) ile çelişir. Ayrıca, \[ a+b=\frac{d+5a}{8} \le\frac{N-k+35}{8} \le k. \] Dolayısıyla, istendiği gibi, \[ N= \underbrace{2^2+\cdots+2^2}_{a\text{ terim}} +\underbrace{3^2+\cdots+3^2}_{b\text{ terim}} +\underbrace{1^2+\cdots+1^2}_{k-a-b\text{ terim}}, \] olur. Sıfır terim içeren bir grup yazılmaz. \(\square\)
(b) Her \(1\le k\le155\) için \(169=13^2\)'nin \(k\) pozitif tam karenin toplamı olduğunu gösterelim.
\(23\le k\le155\) için yardımcı önerme uygulanabilir, çünkü \[ 169-k\ge14, \qquad 9k\ge207\ge169+35. \]
Geriye \(1\le k\le22\) durumlarını ele almak kalır. \(k=1,2\) durumları \[ 169=13^2=12^2+5^2 \] eşitliğinden elde edilir. Diğer durumlar için şu işlemi kullanalım: bir çift sayının karesi bulunduğunda, onu dört eşit kareyle değiştirelim, \[ (2u)^2=u^2+u^2+u^2+u^2. \] Her işlem terim sayısını tam olarak \(3\) artırır.
Tablodaki özdeşliklerden başlayarak belirtilen karelere bu işlemi art arda uygulayalım ve herhangi bir ara aşamada duralım.
| \(169\)'un başlangıçtaki gösterimi | Tamamen parçalanacak kareler | Elde edilen terim sayıları |
|---|---|---|
| \(12^2+4^2+3^2\) | \(12^2\) on altı tane \(3^2\)'ye, \(4^2\) ise on altı tane \(1^2\)'ye | \(3,6,9,\ldots,33\) |
| \(10^2+8^2+2^2+1^2\) | \(8^2\) altmış dört tane \(1^2\)'ye | \(4,7,10,\ldots,67\) |
| \(12^2+4^2+2^2+2^2+1^2\) | \(4^2\) on altı tane \(1^2\)'ye | \(5,8,11,\ldots,20\) |
Her bir parçalama terim sayısını tam olarak üç artırdığı için listelenen tüm ara sayılar elde edilir. Bu üç aritmetik dizi, \(3\)'ten \(22\)'ye kadar her tam sayıyı kapsar.
Dolayısıyla her \(k\le155\) mümkündür. (a) şıkkıyla birlikte bu, \[ \boxed{S(13)=155=13^2-14} \] eşitliğini kanıtlar.
(c) \(n\ge13\) sayısı \[ S(n)=n^2-14, \] eşitliğini sağladığında \(2n\) tam sayısının da sınıra ulaştığını kanıtlayalım.
\(m=n^2\) yazalım; böylece \(m\ge169\) olur. Her \[ 1\le k\le m-14, \] için \[ m=a_1^2+\cdots+a_k^2 \] biçiminde bir gösterim vardır. Karesi alınan her sayıyı iki katına çıkararak \[ 4m=(2a_1)^2+\cdots+(2a_k)^2, \] gösterimini aynı terim sayısıyla elde ederiz.
Geriye kalan \[ m-13\le k\le4m-14, \] tam sayıları için \(4m-k\ge14\) olur ve \[ 9k\ge9m-117\ge4m+35, \] burada son eşitsizlik \(5m\ge152\)'den elde edilir. Dolayısıyla yardımcı önerme, \(N=4m\) alınarak, tam olarak \(k\) pozitif tam kare içeren bir gösterim verir.
O hâlde \(4m=(2n)^2\)'nin her \(1\le k\le4m-14\) için bir gösterimi vardır. (a) şıkkını uygulayarak \[ S(2n)=(2n)^2-14 \] elde ederiz.
\(n=13\) ile başlayıp bu işlemi yineleyerek \[ \boxed{S(13\cdot2^t)=(13\cdot2^t)^2-14\qquad(t=0,1,2,\ldots)} \] elde ederiz. Bu tam sayılar birbirinden farklı olduğundan, sonsuz çoklukta oldukları kanıtlanır.
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1992 · Problema 6
Para cada entero positivo \(n\), se define \(S(n)\) como el mayor entero tal que, para todo entero positivo \(k \le S(n)\), \(n^2\) se puede escribir como suma de \(k\) cuadrados positivos.
(a) Demostrar que \(S(n) \le n^2 - 14\) para todo \(n \ge 4\).
(b) Hallar un entero \(n\) tal que \(S(n) = n^2 - 14\).
(c) Demostrar que existen infinitos enteros \(n\) tales que \(S(n) = n^2 - 14\).
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Respuesta
Para (b), sirve \(n=13\): \(S(13)=155\).
Para (c), todo \(n=13\cdot 2^t\), donde \(t\) es un entero no negativo, satisface \(S(n)=n^2-14\).
Solución
Todos los cuadrados que aparecen a continuación son cuadrados de enteros positivos.
(a) Supongamos que \(n^2\) fuera una suma de \(n^2-13\) cuadrados positivos: \[ n^2=a_1^2+\cdots+a_{n^2-13}^2. \] Restando el número de sumandos, obtenemos \[ 13=\sum_{i=1}^{n^2-13}(a_i^2-1). \] Cada sumando del miembro derecho pertenece a \[ \{0,3,8,15,24,\ldots\}. \] Por tanto, \(13=3u+8v\) para ciertos enteros no negativos \(u,v\). Necesariamente, \(v=0\) o \(v=1\), pero ni \(13\) ni \(13-8=5\) son divisibles por \(3\). Esto es imposible.
Para \(n\ge4\), el entero \(n^2-13\) es positivo, por lo que la imposibilidad de una representación con ese número de sumandos implica \[ \boxed{S(n)\le n^2-14}. \]
Para construir ejemplos que alcancen esta cota, primero demostramos un lema elemental.
Lema. Si los enteros positivos \(N,k\) satisfacen \[ N-k\ge14 \qquad\text{y}\qquad 9k\ge N+35, \] entonces \(N\) es una suma de exactamente \(k\) cuadrados positivos.
Demostración. Sea \(d=N-k\). Como \(3\) es primo relativo con \(8\), existe un entero \(a\in\{0,1,\ldots,7\}\) tal que \(3a\equiv d\pmod8\). Escribamos \[ d=3a+8b. \] Aquí, \(b\) es un entero y es no negativo: de lo contrario, \[ d\le3\cdot7-8=13, \] en contradicción con \(d\ge14\). Además, \[ a+b=\frac{d+5a}{8} \le\frac{N-k+35}{8} \le k. \] En consecuencia, \[ N= \underbrace{2^2+\cdots+2^2}_{a\text{ términos}} +\underbrace{3^2+\cdots+3^2}_{b\text{ términos}} +\underbrace{1^2+\cdots+1^2}_{k-a-b\text{ términos}}, \] como se requería. Un grupo que contenga cero términos simplemente se omite. \(\square\)
(b) Mostramos que \(169=13^2\) es una suma de \(k\) cuadrados positivos para todo \(1\le k\le155\).
Para \(23\le k\le155\), se puede aplicar el lema, porque \[ 169-k\ge14, \qquad 9k\ge207\ge169+35. \]
Queda por tratar \(1\le k\le22\). Los casos \(k=1,2\) se deducen de \[ 169=13^2=12^2+5^2. \] Para los demás casos, usamos la siguiente operación: siempre que aparezca un cuadrado par, lo sustituimos por cuatro cuadrados iguales, \[ (2u)^2=u^2+u^2+u^2+u^2. \] Cada operación aumenta el número de sumandos en exactamente \(3\).
Partiendo de las identidades de la tabla, aplicamos repetidamente esta operación a los cuadrados indicados y nos detenemos en cualquier etapa intermedia.
| Representación inicial de \(169\) | Cuadrados que se descomponen por completo | Números de sumandos obtenidos |
|---|---|---|
| \(12^2+4^2+3^2\) | \(12^2\) en dieciséis cuadrados \(3^2\), y \(4^2\) en dieciséis cuadrados \(1^2\) | \(3,6,9,\ldots,33\) |
| \(10^2+8^2+2^2+1^2\) | \(8^2\) en sesenta y cuatro cuadrados \(1^2\) | \(4,7,10,\ldots,67\) |
| \(12^2+4^2+2^2+2^2+1^2\) | \(4^2\) en dieciséis cuadrados \(1^2\) | \(5,8,11,\ldots,20\) |
Se obtiene cada número intermedio indicado porque cada descomposición individual añade exactamente tres sumandos. Estas tres progresiones cubren todos los enteros desde \(3\) hasta \(22\).
Así, todo \(k\le155\) es posible. Junto con el apartado (a), esto demuestra \[ \boxed{S(13)=155=13^2-14}. \]
(c) Demostramos que, siempre que \(n\ge13\) satisface \[ S(n)=n^2-14, \] el entero \(2n\) también alcanza la cota.
Escribamos \(m=n^2\), de modo que \(m\ge169\). Para todo \[ 1\le k\le m-14, \] existe una representación \[ m=a_1^2+\cdots+a_k^2. \] Al duplicar cada base, obtenemos \[ 4m=(2a_1)^2+\cdots+(2a_k)^2, \] con el mismo número de sumandos.
Para los enteros restantes \[ m-13\le k\le4m-14, \] tenemos \(4m-k\ge14\), y \[ 9k\ge9m-117\ge4m+35, \] donde la última desigualdad se deduce de \(5m\ge152\). Por tanto, el lema, con \(N=4m\), proporciona una representación con exactamente \(k\) cuadrados positivos.
Así pues, \(4m=(2n)^2\) tiene representaciones para todo \(1\le k\le4m-14\). Aplicando el apartado (a), obtenemos \[ S(2n)=(2n)^2-14. \]
Partiendo de \(n=13\) e iterando, obtenemos \[ \boxed{S(13\cdot2^t)=(13\cdot2^t)^2-14\qquad(t=0,1,2,\ldots)}. \] Estos enteros son distintos, lo que demuestra que hay infinitos.
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1992 · 问题 6
对于每个正整数 \(n\)，定义 \(S(n)\) 为满足下述条件的最大整数：对于每个正整数 \(k \le S(n)\)，\(n^2\) 都能表示为 \(k\) 个正平方数之和。
(a) 证明：对于每个 \(n \ge 4\)，都有 \(S(n) \le n^2 - 14\)。
(b) 求一个整数 \(n\)，使得 \(S(n) = n^2 - 14\)。
(c) 证明：存在无穷多个整数 \(n\)，使得 \(S(n) = n^2 - 14\)。
题目译自官方英文原文。 官方试卷 (PDF)
答案
对于 (b)，\(n=13\) 符合要求：\(S(13)=155\)。
对于 (c)，每个形如 \(n=13\cdot 2^t\) 的数都满足 \(S(n)=n^2-14\)，其中 \(t\) 为非负整数。
解答
下文中所有平方数均指正整数的平方。
(a) 假设 \(n^2\) 可以表示为 \(n^2-13\) 个正平方数之和： \[ n^2=a_1^2+\cdots+a_{n^2-13}^2. \] 两边减去加数的个数，得 \[ 13=\sum_{i=1}^{n^2-13}(a_i^2-1). \] 右边的每个加数都属于集合 \[ \{0,3,8,15,24,\ldots\}. \] 因此，存在非负整数 \(u,v\)，使得 \(13=3u+8v\)。必有 \(v=0\) 或 \(v=1\)，但 \(13\) 和 \(13-8=5\) 都不能被 \(3\) 整除。这是不可能的。
当 \(n\ge4\) 时，整数 \(n^2-13\) 为正，故不能表示为这个数目的正平方数之和意味着 \[ \boxed{S(n)\le n^2-14}. \]
为构造达到此上界的例子，先证明一个初等引理。
引理。 若正整数 \(N,k\) 满足 \[ N-k\ge14 \qquad\text{且}\qquad 9k\ge N+35, \] 则 \(N\) 可以表示为恰好 \(k\) 个正平方数之和。
证明。 令 \(d=N-k\)。由于 \(3\) 与 \(8\) 互质，存在整数 \(a\in\{0,1,\ldots,7\}\)，使得 \(3a\equiv d\pmod8\)。写成 \[ d=3a+8b. \] 这里 \(b\) 是整数，且为非负数：否则 \[ d\le3\cdot7-8=13, \] 与 \(d\ge14\) 矛盾。此外， \[ a+b=\frac{d+5a}{8} \le\frac{N-k+35}{8} \le k. \] 因此， \[ N= \underbrace{2^2+\cdots+2^2}_{a\text{ 项}} +\underbrace{3^2+\cdots+3^2}_{b\text{ 项}} +\underbrace{1^2+\cdots+1^2}_{k-a-b\text{ 项}}, \] 符合要求。若某一组的项数为零，只需略去该组即可。\(\square\)
(b) 下面证明：对于每个 \(1\le k\le155\)，\(169=13^2\) 都可以表示为 \(k\) 个正平方数之和。
当 \(23\le k\le155\) 时，可以应用引理，因为 \[ 169-k\ge14, \qquad 9k\ge207\ge169+35. \]
只需再处理 \(1\le k\le22\) 的情形。\(k=1,2\) 的情形由下式可得： \[ 169=13^2=12^2+5^2. \] 对于其余情形，采用如下操作：每当出现一个偶数的平方时，将其替换为四个相等的平方数， \[ (2u)^2=u^2+u^2+u^2+u^2. \] 每次操作都使加数的个数恰好增加 \(3\)。
从表中的恒等式出发，对所指定的平方数反复进行上述操作，并可在任意中间阶段停止。
| \(169\) 的初始表示 | 要完全拆分的平方数 | 得到的加数个数 |
|---|---|---|
| \(12^2+4^2+3^2\) | 将 \(12^2\) 拆成十六个 \(3^2\)，并将 \(4^2\) 拆成十六个 \(1^2\) | \(3,6,9,\ldots,33\) |
| \(10^2+8^2+2^2+1^2\) | 将 \(8^2\) 拆成六十四个 \(1^2\) | \(4,7,10,\ldots,67\) |
| \(12^2+4^2+2^2+2^2+1^2\) | 将 \(4^2\) 拆成十六个 \(1^2\) | \(5,8,11,\ldots,20\) |
列出的每个中间项数都能得到，因为每次单独的拆分都使加数的个数恰好增加三。这三个等差数列覆盖了从 \(3\) 到 \(22\) 的每个整数。
因此，每个 \(k\le155\) 都可以实现。结合 (a)，这就证明了 \[ \boxed{S(13)=155=13^2-14}. \]
(c) 下面证明：只要 \(n\ge13\) 满足 \[ S(n)=n^2-14, \] 整数 \(2n\) 也能达到此上界。
记 \(m=n^2\)，则 \(m\ge169\)。对于每个 \[ 1\le k\le m-14, \] 都存在表示 \[ m=a_1^2+\cdots+a_k^2. \] 将每个底数加倍，得 \[ 4m=(2a_1)^2+\cdots+(2a_k)^2, \] 加数的个数保持不变。
对于其余的整数 \[ m-13\le k\le4m-14, \] 有 \(4m-k\ge14\)，且 \[ 9k\ge9m-117\ge4m+35, \] 其中最后一个不等式由 \(5m\ge152\) 得到。因此，在引理中取 \(N=4m\)，就能得到恰好由 \(k\) 个正平方数组成的表示。
所以，对于每个 \(1\le k\le4m-14\)，\(4m=(2n)^2\) 都有相应的表示。应用 (a)，得 \[ S(2n)=(2n)^2-14. \]
从 \(n=13\) 开始反复应用上述结论，得到 \[ \boxed{S(13\cdot2^t)=(13\cdot2^t)^2-14\qquad(t=0,1,2,\ldots)}. \] 这些整数互不相同，故满足条件的整数有无穷多个。
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1992 · Задача 6
Для каждого положительного целого числа \(n\) величина \(S(n)\) определяется как наибольшее целое число, для которого при каждом положительном целом \(k \le S(n)\) число \(n^2\) можно представить в виде суммы \(k\) квадратов положительных целых чисел.
(a) Докажите, что \(S(n) \le n^2 - 14\) для каждого \(n \ge 4\).
(b) Найдите целое число \(n\), для которого \(S(n) = n^2 - 14\).
(c) Докажите, что существует бесконечно много целых чисел \(n\), для которых \(S(n) = n^2 - 14\).
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Ответ
В пункте (b) подходит \(n=13\): \(S(13)=155\).
В пункте (c) каждое число \(n=13\cdot 2^t\), где \(t\) — неотрицательное целое число, удовлетворяет равенству \(S(n)=n^2-14\).
Решение
Все квадраты ниже — квадраты положительных целых чисел.
(a) Предположим, что \(n^2\) представимо в виде суммы \(n^2-13\) квадратов положительных целых чисел: \[ n^2=a_1^2+\cdots+a_{n^2-13}^2. \] Вычитая число слагаемых, получаем \[ 13=\sum_{i=1}^{n^2-13}(a_i^2-1). \] Каждое слагаемое справа принадлежит множеству \[ \{0,3,8,15,24,\ldots\}. \] Таким образом, \(13=3u+8v\) для некоторых неотрицательных целых \(u,v\). Необходимо, чтобы \(v=0\) или \(v=1\), но ни \(13\), ни \(13-8=5\) не делится на \(3\). Это невозможно.
При \(n\ge4\) целое число \(n^2-13\) положительно, поэтому невозможность такого представления означает, что \[ \boxed{S(n)\le n^2-14}. \]
Чтобы построить примеры, в которых эта оценка достигается, сначала докажем элементарную лемму.
Лемма. Если положительные целые числа \(N,k\) удовлетворяют условиям \[ N-k\ge14 \qquad\text{и}\qquad 9k\ge N+35, \] то \(N\) представимо в виде суммы ровно \(k\) квадратов положительных целых чисел.
Доказательство. Положим \(d=N-k\). Поскольку \(3\) взаимно просто с \(8\), существует целое число \(a\in\{0,1,\ldots,7\}\), для которого \(3a\equiv d\pmod8\). Запишем \[ d=3a+8b. \] Здесь \(b\) — целое число, причём оно неотрицательно: иначе \[ d\le3\cdot7-8=13, \] что противоречит условию \(d\ge14\). Кроме того, \[ a+b=\frac{d+5a}{8} \le\frac{N-k+35}{8} \le k. \] Следовательно, \[ N= \underbrace{2^2+\cdots+2^2}_{a\text{ слагаемых}} +\underbrace{3^2+\cdots+3^2}_{b\text{ слагаемых}} +\underbrace{1^2+\cdots+1^2}_{k-a-b\text{ слагаемых}}, \] что и требовалось. Группа, содержащая ноль слагаемых, просто опускается. \(\square\)
(b) Покажем, что \(169=13^2\) представимо в виде суммы \(k\) квадратов положительных целых чисел для каждого \(1\le k\le155\).
При \(23\le k\le155\) применима лемма, поскольку \[ 169-k\ge14, \qquad 9k\ge207\ge169+35. \]
Остаётся рассмотреть \(1\le k\le22\). Случаи \(k=1,2\) следуют из равенств \[ 169=13^2=12^2+5^2. \] В остальных случаях воспользуемся следующей операцией: если среди слагаемых есть квадрат чётного числа, заменим его четырьмя равными квадратами, \[ (2u)^2=u^2+u^2+u^2+u^2. \] Каждая операция увеличивает число слагаемых ровно на \(3\).
Начиная с тождеств в таблице, будем многократно применять эту операцию к указанным квадратам, останавливаясь на любом промежуточном этапе.
| Исходное представление числа \(169\) | Квадраты, которые нужно полностью разбить | Получаемые количества слагаемых |
|---|---|---|
| \(12^2+4^2+3^2\) | \(12^2\) на шестнадцать слагаемых \(3^2\), а \(4^2\) на шестнадцать слагаемых \(1^2\) | \(3,6,9,\ldots,33\) |
| \(10^2+8^2+2^2+1^2\) | \(8^2\) на шестьдесят четыре слагаемых \(1^2\) | \(4,7,10,\ldots,67\) |
| \(12^2+4^2+2^2+2^2+1^2\) | \(4^2\) на шестнадцать слагаемых \(1^2\) | \(5,8,11,\ldots,20\) |
Каждое указанное промежуточное количество достигается, поскольку отдельное разбиение добавляет ровно три слагаемых. Эти три прогрессии охватывают все целые числа от \(3\) до \(22\) включительно.
Таким образом, каждое \(k\le155\) возможно. Вместе с пунктом (a) это доказывает, что \[ \boxed{S(13)=155=13^2-14}. \]
(c) Докажем, что если \(n\ge13\) удовлетворяет равенству \[ S(n)=n^2-14, \] то для целого числа \(2n\) оценка также достигается.
Обозначим \(m=n^2\), так что \(m\ge169\). Для каждого \[ 1\le k\le m-14, \] существует представление \[ m=a_1^2+\cdots+a_k^2. \] Удваивая каждое возводимое в квадрат число, получаем \[ 4m=(2a_1)^2+\cdots+(2a_k)^2, \] с тем же числом слагаемых.
Для остальных целых чисел \[ m-13\le k\le4m-14, \] имеем \(4m-k\ge14\), и \[ 9k\ge9m-117\ge4m+35, \] где последнее неравенство следует из \(5m\ge152\). Поэтому лемма при \(N=4m\) даёт представление в виде суммы ровно \(k\) квадратов положительных целых чисел.
Следовательно, \(4m=(2n)^2\) имеет представления для всех \(1\le k\le4m-14\). Применяя пункт (a), получаем \[ S(2n)=(2n)^2-14. \]
Начиная с \(n=13\) и повторяя этот переход, получаем \[ \boxed{S(13\cdot2^t)=(13\cdot2^t)^2-14\qquad(t=0,1,2,\ldots)}. \] Эти целые числа различны, что доказывает их бесконечность.
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1992 · المسألة 6
لكل عدد صحيح موجب \(n\)، يُعرَّف \(S(n)\) بأنه أكبر عدد صحيح بحيث يمكن، لكل عدد صحيح موجب \(k \le S(n)\)، كتابة \(n^2\) على صورة مجموع \(k\) مربعات موجبة.
(a) أثبت أن \(S(n) \le n^2 - 14\) لكل \(n \ge 4\).
(b) أوجد عددًا صحيحًا \(n\) بحيث \(S(n) = n^2 - 14\).
(c) أثبت وجود عدد لا نهائي من الأعداد الصحيحة \(n\) التي تحقق \(S(n) = n^2 - 14\).
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الإجابة
في (b)، يصلح \(n=13\): إذ إن \(S(13)=155\).
في (c)، كل عدد \(n=13\cdot 2^t\)، حيث \(t\) عدد صحيح غير سالب، يحقق \(S(n)=n^2-14\).
الحل
جميع المربعات الواردة أدناه هي مربعات أعداد صحيحة موجبة.
(a) لنفترض أن \(n^2\) مجموع \(n^2-13\) مربعًا موجبًا: \[ n^2=a_1^2+\cdots+a_{n^2-13}^2. \] بطرح عدد الحدود نحصل على \[ 13=\sum_{i=1}^{n^2-13}(a_i^2-1). \] كل حد في الطرف الأيمن ينتمي إلى \[ \{0,3,8,15,24,\ldots\}. \] إذن \(13=3u+8v\) لعددين صحيحين غير سالبين \(u,v\). ولا بد أن يكون \(v=0\) أو \(v=1\)، لكن لا \(13\) ولا \(13-8=5\) يقبل القسمة على \(3\). وهذا مستحيل.
عندما \(n\ge4\)، يكون العدد الصحيح \(n^2-13\) موجبًا، لذا فإن تعذر هذا التمثيل يقتضي \[ \boxed{S(n)\le n^2-14}. \]
لبناء أمثلة تبلغ هذا الحد، نثبت أولًا نتيجة مساعدة أولية.
نتيجة مساعدة. إذا كان العددان الصحيحان الموجبان \(N,k\) يحققان \[ N-k\ge14 \qquad\text{و}\qquad 9k\ge N+35, \] فإن \(N\) مجموع \(k\) مربعًا موجبًا بالضبط.
البرهان. لنضع \(d=N-k\). بما أن \(3\) أولي نسبيًا مع \(8\)، يوجد عدد صحيح \(a\in\{0,1,\ldots,7\}\) بحيث \(3a\equiv d\pmod8\). نكتب \[ d=3a+8b. \] هنا \(b\) عدد صحيح، وهو غير سالب: وإلا لكان \[ d\le3\cdot7-8=13, \] خلافًا لـ\(d\ge14\). وعلاوة على ذلك، \[ a+b=\frac{d+5a}{8} \le\frac{N-k+35}{8} \le k. \] وبالتالي، \[ N= \underbrace{2^2+\cdots+2^2}_{a\text{ حدًا}} +\underbrace{3^2+\cdots+3^2}_{b\text{ حدًا}} +\underbrace{1^2+\cdots+1^2}_{k-a-b\text{ حدًا}}, \] كما هو مطلوب. وتُحذف ببساطة أي مجموعة عدد حدودها صفر. \(\square\)
(b) نبيّن أن \(169=13^2\) مجموع \(k\) مربعًا موجبًا لكل \(1\le k\le155\).
عندما \(23\le k\le155\)، تنطبق النتيجة المساعدة، لأن \[ 169-k\ge14, \qquad 9k\ge207\ge169+35. \]
يبقى أن نعالج \(1\le k\le22\). تنتج الحالتان \(k=1,2\) من \[ 169=13^2=12^2+5^2. \] أما الحالات الأخرى، فنستخدم لها العملية الآتية: كلما ظهر مربع زوجي، نستبدل به أربعة مربعات متساوية، \[ (2u)^2=u^2+u^2+u^2+u^2. \] تزيد كل عملية عدد الحدود بمقدار \(3\) بالضبط.
انطلاقًا من المتطابقات في الجدول، نطبق هذه العملية مرارًا على المربعات المحددة، ونتوقف عند أي مرحلة وسيطة.
| التمثيل الابتدائي للعدد \(169\) | المربعات المراد تفكيكها بالكامل | أعداد الحدود الناتجة |
|---|---|---|
| \(12^2+4^2+3^2\) | \(12^2\) إلى ستة عشر حدًا كل منها \(3^2\)، و\(4^2\) إلى ستة عشر حدًا كل منها \(1^2\) | \(3,6,9,\ldots,33\) |
| \(10^2+8^2+2^2+1^2\) | \(8^2\) إلى أربعة وستين حدًا كل منها \(1^2\) | \(4,7,10,\ldots,67\) |
| \(12^2+4^2+2^2+2^2+1^2\) | \(4^2\) إلى ستة عشر حدًا كل منها \(1^2\) | \(5,8,11,\ldots,20\) |
يتحقق كل عدد وسيط مذكور لأن كل عملية تفكيك منفردة تضيف ثلاثة حدود بالضبط. وتغطي هذه المتتاليات الحسابية الثلاث كل عدد صحيح من \(3\) إلى \(22\).
إذن كل \(k\le155\) ممكن. وبالاقتران مع الجزء (a)، يثبت هذا أن \[ \boxed{S(13)=155=13^2-14}. \]
(c) نثبت أنه كلما حقق \(n\ge13\) العلاقة \[ S(n)=n^2-14, \] فإن العدد الصحيح \(2n\) يبلغ هذا الحد أيضًا.
نكتب \(m=n^2\)، ومن ثم \(m\ge169\). لكل \[ 1\le k\le m-14, \] يوجد تمثيل \[ m=a_1^2+\cdots+a_k^2. \] بمضاعفة أساس كل مربع نحصل على \[ 4m=(2a_1)^2+\cdots+(2a_k)^2, \] بعدد الحدود نفسه.
أما الأعداد الصحيحة المتبقية \[ m-13\le k\le4m-14, \] فإن \(4m-k\ge14\)، و \[ 9k\ge9m-117\ge4m+35, \] حيث تنتج المتباينة الأخيرة من \(5m\ge152\). ولذلك تعطي النتيجة المساعدة، مع \(N=4m\)، تمثيلًا يتألف من \(k\) مربعًا موجبًا بالضبط.
إذن للعدد \(4m=(2n)^2\) تمثيلات لكل \(1\le k\le4m-14\). وبتطبيق الجزء (a) نحصل على \[ S(2n)=(2n)^2-14. \]
بالبدء من \(n=13\) وتكرار ذلك، نحصل على \[ \boxed{S(13\cdot2^t)=(13\cdot2^t)^2-14\qquad(t=0,1,2,\ldots)}. \] هذه الأعداد الصحيحة مختلفة، مما يثبت أن عددها لا نهائي.
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).