Da Mosca a Shanghai

[Federico II]

CHN1 e RUS3 (sono questi i veri nomi di quelli che qualcuno crede siano ITA1 e ITA3) stanno mettendo a punto un piano malvagio per distruggere l'Italia. Hanno costruito una nuova lunghissima muraglia, la Muraglia Cino-Sovietica, e stanno preparando le loro armi segrete dietro di essa. La Muraglia si estende per una lunghezza di un numero intero di nikkiuoyi, dalla casa di RUS3 (a Mosca) a quella di CHN1 (a Shanghai). Questo numero intero di nikkiuoyi potrebbe sembrare scelto a caso, ma in realtà è il prodotto di $n$ interi positivi, i parametri di guerra su cui CHN1 e RUS3 si sono accordati. Questi parametri sono coprimi a due a due e tutti grandi almeno quanto la somma tra il numero di parametri e il numero di Paesi diversi sul cui suolo la Muraglia è costruita. Inoltre, il più piccolo tra tutti i parametri è un numero primo.
Costruire la Muraglia, viste le sue dimensioni, non è stato affatto facile. Per farlo, CHN1 e RUS3 hanno prima tracciato una linea sul terreno dove la Muraglia sarebbe sorta, poi hanno segnato su di essa vari punti per determinare le posizioni delle lastre di cemento armato da piazzare. In particolare, per segnare i punti hanno inviato $n$ automi, ognuno con uno dei parametri di guerra, da una parte all'altra della linea, e ognuno era programmato per segnare un punto ogni $p$ nikkiuoyi, dove $p$ è il suo parametro. Tutti iniziavano segnando il punto di partenza (che potrebbe essere tanto a casa di RUS3 quanto a casa di CHN1), e se dovevano segnare un punto già segnato da un altro automa non cambiava niente: quel punto rimaneva segnato.
La Muraglia è stata infine costruita piazzando in ogni intervallo tra due punti segnati consecutivi una lastra di cemento armato che coprisse tutta la larghezza dell'intervallo e che fosse tanto larga quanto alta.
L'imponenza della Muraglia ha fatto insospettire il mondo, e le leggende su cosa stesse accadendo dietro sono giunte sino a Milano, dove ITA4 si è scosso e ha deciso di approfondire. Le sue spie hanno scoperto tutto, e ora ITA4 non vuole fare altro che distruggere il muro e così far crollare il piano segreto di CHN1 e RUS3. Per poter distruggere il muro ITA4 vorrebbe conoscerne l'area totale, ma le sue spie ci metteranno ancora un bel po' a fargliela sapere con esattezza (è dura misurare un muro così lungo!). Tuttavia ITA4 sa già che quest'area totale, se espressa in nikkiuoyi quadrati, è certamente un intero divisibile per il più piccolo dei parametri di guerra scelti da CHN1 e RUS3. Avete già capito perché?

[cip999]

Avevo in mente un bel sequel per la storia ma la voglia di scriverlo è circa nulla... Quindi niente, gli appassionati lettori del forum dovranno accontentarsi di una soluzione normale.

Testo nascosto:

Chiamiamo $p_1 < p_2 < \cdots < p_n$ i parametri (e chi avrebbe mai detto che non sono per forza tutti primi?), dove $p_1$ è primo e $\ge n + 2$. Chiamiamo $x_1 < x_2 < \cdots < x_M$ le distanze (in nikkiuoyi) dei punti segnati sulla Muraglia dalla casa di RUS3. Ovviamente $x_1 = 0$ e $x_M = p_1p_2\cdots p_n$. Allora l'area complessiva della Muraglia è pari a $$S = \sum_{i = 1}^{M - 1} (x_{i + 1} - x_i)^2$$ e vogliamo mostrare che questo numero è divisibile per $p_1$.
Come suggeriscono i mandarini del mandarineto d'Abruzzo, il quadrato di un intero $m$ altro non è che la somma dei numeri dispari da $1$ a $2m - 1$, per cui possiamo scrivere $S$ come $$S = \sum_{i = 1}^{M - 1} \sum_{j = 1}^{x_{i + 1} - x_i} (2j - 1) = 2\left(\sum_{i = 1}^{M - 1} \sum_{j = 1}^{x_{i + 1} - x_i} j\right) - p_1\cdots p_n$$ Dato che $p_1 \ge n + 2 \ge 3$ è dispari, $p_1 \mid S$ se e solo se $\displaystyle p_1 \mid S' = \sum_{i = 1}^{M - 1} \sum_{j = 1}^{x_{i + 1} - x_i} j$. Ora, per complicare ulteriormente le cose, introduciamo la funzione $d(i)$ (per $1 \le i \le p_1\cdots p_n$), definita come la minima distanza (in nikkiuoyi, ovviamente) da $i$ a una delle posizioni segnate che precedono $i$ (eh?); ovvero $\displaystyle d(i) = \min_{x_j < i} \{i - x_j\}$. Allora, con un abile double-counting (o forse due...), scopriamo che $$S' = \sum_{i = 1}^{p_1\cdots p_n} d(i) = \sum_{k = 1}^{+\infty} \#\{1 \le i \le p_1\cdots p_n: \: d(i) \ge k\}$$
Sperando che tutto quello che ho scritto fin qui abbia senso, ora vogliamo sapere: fissato $k$, quanti sono gli $i$ tali che $d(i) \ge k$? Per $k > p_1$ la riposta è sicuramente $0$, in quanto in un blocco di (almeno) $p_1$ interi consecutivi ce n'è quanto meno uno divisibile per $p_1$. Per $1 \le k < p_1$, invece, $d(i) \ge k$ se e solo se $i$ è soluzione del sistema di congruenze $$\begin{cases} i \equiv a_1 \pmod{p_1} \\ i \equiv a_2 \pmod{p_2} \\ \quad \vdots \\ i \equiv a_n \pmod{p_n} \end{cases}$$ dove $k \le a_j \le p_j$ per $j = 1, \: \dots, \: n$. Ma, dato che i $p_j$ sono pairwise coprimi, fissati gli $a_j$ questo sistema ha una e una sola soluzione in $\{1, \: \dots, \: p_1\cdots p_n\}$ (per il TCR). Allora il numero di $i$ tali che $d(i) \ge k$ è pari al numero di modi di scegliere gli $a_j$, cioè a $(p_1 + 1 - k)(p_2 + 1 - k)\cdots(p_n + 1 - k)$. Per cui $$S' = \sum_{k = 1}^{p_1} (p_1 + 1 - k)(p_2 + 1 - k)\cdots(p_n + 1 - k)$$
Consideriamo dunque il polinomio $f(x) = (p_1 + 1 - x)(p_2 + 1 - x)\cdots(p_n + 1 - x)$: cosa possiamo dire di lui? Tante cose, ma in particolare che $\deg f = n \le p_1 - 2$. Ma allora, ricordando che $p_1$ è effettivamente primo, per il famoso lemmone vale $$S' = \sum_{k = 1}^{p_1} f(k) \equiv 0 \pmod{p_1}$$
E questo direi che conclude.

[Federico II]

Ok va bene, anche molto carina
Propongo una generalizzazione per cui passa la mia soluzione: dimostrare che, se la Muraglia non si limita necessariamente a due dimensioni, ma è costituita da blocchi aventi un numero $k$ di dimensioni pari al più al numero di Paesi per cui passa, allora il suo volume $k$-dimensionale (espresso in nikkiuoyi$^k$) è divisibile per il più piccolo dei parametri.

[cip999]

Ok, si dovrebbe generalizzare tranquillamente anche la mia (metto solo un outline).

Testo nascosto:

Scriviamo le potenze $k$-esime degli $(x_{i + 1} - x_i)$ come somme di potenze minori moltiplicate per un coefficiente opportuno, e poi separiamo tutte queste somme; ad esempio per $k = 3$ $$\sum_{i = 1}^{M - 1} (x_{i + 1} - x_i)^3 = \sum_{i = 1}^{M - 1} \sum_{j = 1}^{x_{i + 1} - x_j} (3j^2 - 3j + 1) = 3\sum_{i = 1}^{M - 1} \sum_{j = 1}^{x_{i + 1} - x_j} j^2 - 3\sum_{i = 1}^{M - 1} \sum_{j = 1}^{x_{i + 1} - x_j} j + p_1\cdots p_n$$
Per ipotesi induttiva abbiamo gratis la divisibilità per $p_1$ di tutte le somme di grado inferiore a $k - 1$, quindi ci rimane $\displaystyle \sum_{i =
1}^{M - 1} \sum_{j = 1}^{x_{i + 1} - x_i} j^{k - 1}$. Ora come prima definiamo $d$ (identica) e, con conteggi più o meno simili a quelli di prima e usando di nuovo l'espansione di una potenza in potenze minori otteniamo una roba del tipo $$\sum_{t = 1}^{p_1} (\alpha_{k - 2}t^{k - 2} + \cdots + \alpha_1t + \alpha_0) \cdot \#\{1 \le i \le p_1\cdots p_n: \: d(i) \ge t\}$$ E ora sappiamo che la cardinalità di quell'insieme è un polinomio in $t$ di grado $n$ (perché lo abbiamo fatto prima), quindi moltiplicato per il fattore precedente viene un polinomio di grado $n + k - 2 \le p_1 - 2$ e dunque siamo felici.

[Federico II]

Sì, immaginavo che si potesse fare così.