Castelli in aria (Cesenatico 2015)

[Lasker]

Scrivere la soluzione di questo problema è un po' una sofferenza, visto che in gara mi ero accorto di poterlo risolvere con un paio di lemmi che conoscevo ma l'ho lasciato subito perdere sopravvalutandolo e pensando che la scelta particolare del polinomio dovesse essere per forza importante (guardando male i numeri e perdendomi il $p(0)$ iniziale pensavo dovesse venire $0000$ del tutto indipendentemente dal polinomio in $t$; dando per scontato questo risultato come sbagliato ho smesso di credere alla veridicità del primo lemmino e invece di provarlo in casi particolari/dimostrarlo ho saltato l'esercizio passando ad altro ); mentre riprendendolo adesso a distanza di pochi mesi mi è uscito immediatamente e senza sforzi (è proprio vero che con la tensione della competizione è tutta un'altra cosa!).

Per un lemma noto (tra l'altro dimostrato quest'anno al Senior Medium e probabilmente innumerevoli volte in passato...), per qualsiasi polinomio $P$ di grado $\leq p-2$ (con $p$ primo) vale
$$\sum_{k=0}^{p-1} P(k)\equiv 0 \pmod p$$
Chiaramente, visto che $53$ è primo, il polinomio è di grado $50\leq51=53-2=\deg(P)-2$ e convenientemente $53\mid 2014$, ci basta valutare $P(2014)$ modulo $53$ per ottenere la risposta (gli altri "blocchi" di $53$ numeri consecutivi sono tutti divisibili per $p$ grazie al lemma e quindi non contano), facciamolo:
$$P(2014)=\prod_{k=1}^{50}[(51-k)2014+k]\equiv50! \pmod {53}$$
Ma noi sappiamo che $52!\equiv 52 \pmod {53}$ per il teorema di Wilson, quindi
$$50!=\frac{52!}{52\cdot 51}\equiv \frac{52}{(-1)\cdot (-2)} \pmod {53}\equiv \frac{52}{2}\pmod {53}\equiv 26 \pmod {53}$$
E abbiamo finito in un attimo un problema da $108$ punti

PS: questo secondo me è un TdN puro

[gpzes]

@Lasker ...non dirmi niente..quando c'è fretta non riesco nenache a darmi conto dove sono..figuriamoci
Forse confondo i posts ma avevo letto un tuo commento sui quesiti delle GaS..
Spesso, i più difficili, contrassegnati con una stellina, NON sono affatto banali!!!
Anzi..nel leggerli può capitare che li si affronti cercando dimostrazioni generali e dimenticando il tempo che scorre..
pessima strategia non essendo una gara individuale.
Forse abilità sta proprio nel riconoscere questo tipo di problemi e capire che bisogna solo limitarsi a fare dei calcoli, anche se lunghi,ma in maniera oculata
Ad ogni modo..il lemma è stato dimostrato ad esempio nel Stage Senior-Basic del 2010..
ma volevo allegare qui, forse per maggiore visibilità, un utilissimo articolo, almeno per me lo è, che spero sia gradito

[fph]

Un'altra dimostrazione di $\sum_{i=0}^{p-1} i^k\equiv 0 \mod p$ per ogni $0<k<p-1$ si ottiene adattando una delle dimostrazioni del piccolo teorema di Fermat: per ogni $g$ non multiplo di $p$, i numeri $0,g,2g,\dots,(p-1)g$ sono un sistema completo di residui, quindi
$$\sum_{i=0}^{p-1} i^k\equiv \sum_{i=0}^{p-1} (gi)^k = g^k \sum_{i=0}^{p-1} i^k.$$ Allora si deve avere $1\equiv g^k$ per ogni possibile scelta di $g$ oppure $\sum_{i=0}^{p-1} i^k\equiv 0$.

[wall98]

@fph ma i generatori, nei dimostrativi di livello winter camp e oltre, si riesce (in media) ad usarli bene? oppure tentare un approccio del genere risulta utile solamente nei problemi non particolarmente laboriosi tipo questo?

(pongo questa domanda per capire se è il caso di farci qualche problema così da imparare ad usarli, oppure dedicarmi ad altre "tecniche")

[fph]

Non li ho visti usati in molti problemi, devo ammettere. Anche in questa dimostrazione i generatori entrano un po' per caso verso la fine (se invece di $g$ lo chiamavo $a$ quasi uno non se ne accorgeva), sono i sistemi completi di residui che compaiono fin dall'inizio. Secondo me il concetto di "prendo un sistema completo di residui" è utile da avere in mente, semplifica il modo di vedere certe cose. E questa idea di "moltiplico tutto per $a$ e vedo che succede" qualche rara volta torna buona, in fondo è un'idea di tipo omogeneità. (Tutto questo nella rara minoranza di problemi di tdn che non si fanno macinando di LTE. )

[Drago96]

La dimostrazione di fph non usa i generatori: $g$ è un qualsiasi intero tale che $g^k\not\equiv1\pmod p$ (esiste sempre per $0<k<p-1$, perché?)
Ovviamente c'è anche il modo con i generatori, che è tipo: sia $g$ un generatore modulo $p$, allora $\displaystyle\sum_1^{p-1} i^k\equiv\sum_0^{p-2} (g^i)^k\equiv\sum_0^{p-2} (g^k)^i$ dove nel primo passaggio abbiamo riordinato i termini (c'è una corrispondenza biunivoca $\sigma:\{1,2,\dots,p-1\}\to\{0,1,\dots,p-2\}$ tale che $i\equiv g^{\sigma(i)}$)
L'ultima somma è una geometrica e dato che $g^k\not\equiv1$ abbiamo $\displaystyle\sum_0^{p-2} (g^k)^i\equiv\frac{(g^k)^{p-1}-1}{g^k-1}\equiv0\pmod p$

[wall98]

Effettivamente non usa i generatori, viene trovata una bigezione con un insieme di residui "più grandi" e imposta l'uguaglianza

La dimostrazione di fph non usa i generatori: $g$ è un qualsiasi intero tale che $g^k\not\equiv1\pmod p$ (esiste sempre per $0<k<p-1$, perché?)

Perchè l'insieme dei residui $k-esimi$ modulo un primo ha cardinalità maggiore di 1 (tranne nel caso in cui $p-1 \mid k$)?

[fph]

Perchè l'insieme dei residui $k-esimi$ modulo un primo ha cardinalità maggiore di 1 (tranne nel caso in cui $p-1 \mid k$)?

Perché $x^k-1\equiv 0$ ha al più $k$ soluzioni per Ruffini. (Che, tra l'altro, è il primo passo della dimostrazione dell'esistenza dei generatori che conosco io.)

[gpzes]

Solo una piccola precisazione…
Ciò che si ottiene è $\sum\limits_{k=0}^{2014}{P(k)\equiv P(2014)+2014\cdot P(0)\equiv P(0)\equiv 50!\quad (\bmod \ 53)}$

..Più che Ruffini non era Teorema di Lagrange ??

[fph]

..Più che Ruffini non era Teorema di Lagrange ??

Ah - ora vedo su wikipedia che si chiama così, ma non sapevo neppure che avesse un nome a parte.

[gpzes]

Oddio..ne ha fatti mai tanti di Teoremi che ufff ..
ma in TdN lo conoscevo sotto quel nome..
https://en.wikipedia.org/wiki/Lagrange% ... er_theory)

[fph]

Sìsì ho visto, non sto dicendo che è sbagliato chiamarlo così, solo che io non sapevo che avesse questo nome.