I problemi del pupazzo

XXI Gara Nazionale a Squadre – Finale nazionale 17 settembre 2020 – Numero 3

Appena creato, il pupazzo di neve comincia a vaneggiare sparando problemi a raffica: per esempio, esclama
«Siano $(x_i, y_i)$ , per $i=1,2,...,k$ , tutte le coppie ordinate di interi positivi che soddisfano $x^x+y^y + 11 = 13 x^y y^x$ .»
«Che carino! Lo chiamerò Olaforum, con tutti questi problemi», decide Gianna.
Ma il pupazzo la ignora e continua «Quanto vale il prodotto di tutti gli $x_i^2 + y_i^2$ ?»

Passo 1

Le variabili $x$ e $y$ possono essere scambiate l’una con l’altra nella formula senza alterare il risultato.
Se $(a, b)$ è una soluzione allora lo è anche $(b, a)$ .
Cerchiamo le soluzioni $(x, y)$ con $x \le y$ e dopo includiamo anche la soluzione $(y, x)$

Passo 2

Sia (x, x) una coppia soluzione
$x^x+x^x + 11 = 13\cdot x^x\cdot x^x$
$2\cdot x^x + 11 = 13\cdot x^{2\cdot x}$
$13\cdot x^{2\cdot x}-2\cdot x^x -11 = 0$
…
x = 1
Infatti
- $1^1 + 1^1+11 = 13\cdot 1^1 \cdot 1^1$
- $1 + 1 + 11 = 13\cdot 1 \cdot 1$
- 13 = 13
L’unica soluzione con $x = y$ è $(1, 1)$ , tutte le eventuali altre saranno con $x \neq y$

Passo 3

Proviamo le coppie (1,1), (1,2), (1,3), (1,4), (1,5)

Passo 4

Abbiamo individuato 3 soluzioni

(1, 1)
(1, 3)
(3, 1)

Se non esistono altre soluzioni allora la risposta al quesito è

$(1^2 + 1^2) \cdot (1^2 + 3^2)\cdot (3^2+1^2)$ = $(1+1)\cdot (1+9)\cdot (9+1)$ = $2\cdot 10 \cdot 10$ = 200

Passo 5

La risposta per ogni quesito deve essere compresa tra 0000 e 9999
Se esiste un’altra soluzione $(a, b)$ allora $200\cdot (a^2+b^2) < 10000$
$(a^2+b^2) < 50$
Rimangono da controllare: (1, 6), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5)
Completiamo la tabella precedente

x=1 y=1	x=1 y=2	x=1 y=3	x=1 y=4	x=1 y=5	x=1 y=6
13 = 13	16 = 26	39 = 39	268 = 52	3137 = 65	46668 = 78
…	…	x=2 y=3	x=2 y=4	x=2 y=5	x=2 y=6
…	…	42 = 936	271 = 3328	3140 = 10400	46671 = 29952
…	…	…	x=3 y=4	x=3 y=5	x=3 y=6
…	…	…	276 = 67392	3163 = 394875	46694 = 2047032
…	…	…	…	x=4 y=5	…
…	…	…	…	3392 = 8320000	…

Non esistono altre soluzioni…

Passo 6?

Esistono soluzioni con valori più grandi?

Osservazione 1

Il secondo membro è un multiplo di 13 (è divisibile per 13)
Il primo membro deve essere un multiplo di 13 (divisibile per 13)
$x^x+y^y + 11 \equiv 0\ (\text{mod}\ 13)$
$x^x+y^y \equiv 2\ (\text{mod}\ 13)$
Ci sono tre possibilità

$x^x \equiv 0\ (\text{mod}\ 13)$ e $y^y \equiv 2\ (\text{mod}\ 13)$
$x^x \equiv 1\ (\text{mod}\ 13)$ e $y^y \equiv 1\ (\text{mod}\ 13)$
$x^x \equiv 2\ (\text{mod}\ 13)$ e $y^y \equiv 0\ (\text{mod}\ 13)$

Osservazione 2

Calcoliamo il resto della divisione per 13 di $x^x$ al crescere della $x$

$1^1 = 1 \equiv 1\ (\text{mod}\ 13)$
$2^2 = 4 \equiv 4\ (\text{mod}\ 13)$
$3^3 = 27 = 2\cdot 13+1 \equiv 1\ (\text{mod}\ 13)$
$4^4 = 16\cdot 16 \equiv 3\cdot 3 \equiv 9\ (\text{mod}\ 13)$
$5^5 = ... \equiv 5\ (\text{mod}\ 13)$
$6^6 = ... \equiv 12\ (\text{mod}\ 13)$
$7^7 = ... \equiv 6\ (\text{mod}\ 13)$
$8^8 = (2^4)^6 = (16)^6 \equiv 3^6 \equiv (3^3)^2 \equiv 1^2 \equiv 1\ (\text{mod}\ 13)$
$9^9 = (3^3)^6 \equiv 1^6 \equiv 1\ (\text{mod}\ 13)$
$10^{10} = ... \equiv 3\ (\text{mod}\ 13)$
$11^{11} = ... \equiv 6\ (\text{mod}\ 13)$
$12^{12} = ... \equiv 1\ (\text{mod}\ 13)$
$13^{13} \equiv 0^{13} \equiv 0\ (\text{mod}\ 13)$
$14^{14} \equiv 1^{14} \equiv 1\ (\text{mod}\ 13)$
$15^{15} = 3^{15}\cdot 5^{15}\equiv ... \equiv 8\ (\text{mod}\ 13)$
$16^{16} = ... \equiv 3\ (\text{mod}\ 13)$
…

Non compare il 2…

x=1 y=1	x=1 y=2	x=1 y=3	x=1 y=4	x=1 y=5
$1^1 + 1^1+11 = 13\cdot 1^1 \cdot 1^1$	$1^1 + 2^2+11 = 13\cdot 1^2 \cdot 2^1$	$1^1 + 3^3+11 = 13\cdot 1^3 \cdot 3^1$	$1^1 + 4^4+11 = 13\cdot 1^4 \cdot 4^1$	$1^1 + 5^5+11 = 13\cdot 1^5 \cdot 5^1$
$1 + 1 + 11 = 13\cdot 1 \cdot 1$	$1 + 4 + 11 = 13\cdot 1 \cdot 2$	$1 + 27 + 11 = 13\cdot 1 \cdot 3$	$1 + 256 + 11 = 13\cdot 1 \cdot 4$	$1 + 3125 + 11 = 13\cdot 1 \cdot 5$
13 = 13	16 = 26	39 = 39	268 = 52	3137 = 65