Castelli in aria (Cesenatico 2015)
Re: Castelli in aria (Cesenatico 2015)
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
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
"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!
"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!
Re: Castelli in aria (Cesenatico 2015)
@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
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
- Allegati
-
- 1011.0076v1.pdf
- (87.48 KiB) Scaricato 6458 volte
Re: Castelli in aria (Cesenatico 2015)
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$.
$$\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]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: Castelli in aria (Cesenatico 2015)
@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")
(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.
Re: Castelli in aria (Cesenatico 2015)
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]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: Castelli in aria (Cesenatico 2015)
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$
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)
Re: Castelli in aria (Cesenatico 2015)
Effettivamente non usa i generatori, viene trovata una bigezione con un insieme di residui "più grandi" e imposta l'uguaglianza
Perchè l'insieme dei residui $k-esimi$ modulo un primo ha cardinalità maggiore di 1 (tranne nel caso in cui $p-1 \mid k$)?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é?)
Il problema non è il problema, il problema sei tu.
Re: Castelli in aria (Cesenatico 2015)
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.)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$)?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: Castelli in aria (Cesenatico 2015)
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 ??
Re: Castelli in aria (Cesenatico 2015)
Ah - ora vedo su wikipedia che si chiama così, ma non sapevo neppure che avesse un nome a parte.gpzes ha scritto: ..Più che Ruffini non era Teorema di Lagrange ??
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: Castelli in aria (Cesenatico 2015)
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)
ma in TdN lo conoscevo sotto quel nome..
https://en.wikipedia.org/wiki/Lagrange% ... er_theory)
Re: Castelli in aria (Cesenatico 2015)
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]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]