Castelli in aria (Cesenatico 2015)

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
Avatar utente
Lasker
Messaggi: 440
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: Castelli in aria (Cesenatico 2015)

Messaggio da Lasker » 18 ago 2015, 00:35

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 :cry: ); 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 :cry:

PS: questo secondo me è un TdN puro :)
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!

Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: Castelli in aria (Cesenatico 2015)

Messaggio da gpzes » 23 ago 2015, 22:36

@Lasker :wink: ...non dirmi niente..quando c'è fretta non riesco nenache a darmi conto dove sono..figuriamoci :oops: :oops: :?
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 :wink:
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 :) :wink:
Allegati
1011.0076v1.pdf
(87.48 KiB) Scaricato 1367 volte

fph
Site Admin
Messaggi: 3801
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Castelli in aria (Cesenatico 2015)

Messaggio da fph » 23 ago 2015, 23:21

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$.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

wall98
Messaggi: 167
Iscritto il: 27 mar 2013, 11:23
Località: Roma

Re: Castelli in aria (Cesenatico 2015)

Messaggio da wall98 » 23 ago 2015, 23:31

@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")
Il problema non è il problema, il problema sei tu.

fph
Site Admin
Messaggi: 3801
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Castelli in aria (Cesenatico 2015)

Messaggio da fph » 24 ago 2015, 00:29

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. :()
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
Drago96
Messaggi: 1144
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Castelli in aria (Cesenatico 2015)

Messaggio da Drago96 » 24 ago 2015, 00:37

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$
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

wall98
Messaggi: 167
Iscritto il: 27 mar 2013, 11:23
Località: Roma

Re: Castelli in aria (Cesenatico 2015)

Messaggio da wall98 » 24 ago 2015, 11:22

Effettivamente non usa i generatori, viene trovata una bigezione con un insieme di residui "più grandi" e imposta l'uguaglianza
Drago96 ha scritto: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$)?
Il problema non è il problema, il problema sei tu.

fph
Site Admin
Messaggi: 3801
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Castelli in aria (Cesenatico 2015)

Messaggio da fph » 24 ago 2015, 11:26

wall98 ha scritto: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.)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: Castelli in aria (Cesenatico 2015)

Messaggio da gpzes » 24 ago 2015, 21:53

:oops:
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 :oops: ??

fph
Site Admin
Messaggi: 3801
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Castelli in aria (Cesenatico 2015)

Messaggio da fph » 24 ago 2015, 22:11

gpzes ha scritto: ..Più che Ruffini non era Teorema di Lagrange :oops: ??
Ah - ora vedo su wikipedia che si chiama così, ma non sapevo neppure che avesse un nome a parte.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: Castelli in aria (Cesenatico 2015)

Messaggio da gpzes » 24 ago 2015, 22:25

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

fph
Site Admin
Messaggi: 3801
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Castelli in aria (Cesenatico 2015)

Messaggio da fph » 24 ago 2015, 22:31

Sìsì ho visto, non sto dicendo che è sbagliato chiamarlo così, solo che io non sapevo che avesse questo nome.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Rispondi