Simulazione Cesenatico Torino (Spinelli)

[LukasEta]

E' possibile avere i testi della gara individuale?? Sarei interessato a provare a risolverli per allenamento a Cesenatico...

[afullo]

Sì, allego testi e soluzioni di entrambe le prove.

[LukasEta]

Sì, allego testi e soluzioni di entrambe le prove.

Merci!

[afullo]

Sì, allego testi e soluzioni di entrambe le prove.

Merci!

Di niente, adesso ne inserisco altre date nelle settimane scorse nella attualmente poco utilizzata sezione del giornalino.

Nel frattempo se riesci a scrivere delle belle soluzioni di 3 e 5b, e completare quella del problema 6, passamele che le inserisco, ne avevo realizzata una del 3 ma ho osservato qualche giorno fa essere sbagliata (e infatti ieri ci abbiamo messo un po' a correggere i relativi esercizi), del 5b non mi sono posto più di tanto il problema in quanto era immaginabile che non venisse risolto (mi aspettavo invece qualcosa di più dal 5a), del 6 anche avevo intuito che qualcuno avrebbe trovato la strategia minimizzante ma senza riuscire a dimostrare rigorosamente che si trattava effettivamente di quella di minimo...

[sasha™]

Per il 3 forse ne ho una carina... Spoilero.

Testo nascosto:

Osserviamo che $1\equiv 9 \pmod 4$ e $3 \equiv 7 \equiv -1 \pmod 4$.
Siano $a_1 ... a_p$ e $b_1 ... b_q$ gli esponenti dei primi, congrui a $1$ e $-1$ rispettivamente, nella fattorizzazione di $n$, esclusi $2$ e $5$ (perché, se un divisore ha uno di questi fattori, non finisce certo con $1$, $3$, $7$ o $9$. ).

Allora i divisori congrui a $1 \pmod 4$ sono $\displaystyle \prod(a_i+1) \cdot \prod{\lfloor \frac{b_i+2}{2} \rfloor}$ (ossia i primi congrui a $-1 \pmod 4$ possono avere solo esponente pari).
I divisori congrui a $-1 \pmod 4$ sono $\displaystyle \prod{a_i+1} \cdot \prod{\lfloor \frac{b_i+1}{2} \rfloor}$, cioè una quantità minore o uguale.

[afullo]

Per il 3 forse ne ho una carina... Spoilero.

Testo nascosto:

Osserviamo che $1\equiv 9 \pmod 4$ e $3 \equiv 7 \equiv -1 \pmod 4$.
Siano $a_1 ... a_p$ e $b_1 ... b_q$ gli esponenti dei primi, congrui a $1$ e $-1$ rispettivamente, nella fattorizzazione di $n$, esclusi $2$ e $5$ (perché, se un divisore ha uno di questi fattori, non finisce certo con $1$, $3$, $7$ o $9$. ).

Allora i divisori congrui a $1 \pmod 4$ sono $\displaystyle \prod(a_i+1) \cdot \prod{\lfloor \frac{b_i+2}{2} \rfloor}$ (ossia i primi congrui a $-1 \pmod 4$ possono avere solo esponente pari).
I divisori congrui a $-1 \pmod 4$ sono $\displaystyle \prod{a_i+1} \cdot \prod{\lfloor \frac{b_i+1}{2} \rfloor}$, cioè una quantità minore o uguale.

Ricapitolando:

Testo nascosto:

• Si definiscono classi di equivalenza tra gli interi positivi nel seguente modo: due appartengono alla stessa classe se e soltanto se i loro fattori primi diversi da 2 e da 5 sono gli stessi e sono elevati agli stessi esponenti;
• Risulta immediato constatare che in ognuna di queste classi di equivalenza esiste uno e un soltanto numero che in notazione decimale termina per 1, 3, 7 o 9; prendiamo esso come rappresentante della classe.
• Si quozienta dunque l'insieme degli interi positivi rispetto a questa relazione di equivalenza, e sulle classi C si può definire una proiezione C --> {-1;1} che manda una classe nella congruenza modulo 4 del suo elemento rappresentante, che è ben definita e rispetta le operazioni, infatti sull'insieme delle classi è possibile definire un prodotto sempre considerando gli elementi rappresentanti, che si comporta bene rispetto alla relazione di equivalenza;
• Si contano le classi, svolgendo il conto che hai fatto tu, e tenendo conto del fatto che il numero di classi coincide col numero di divisori che ci interessano, per l'unicità cui al secondo punto.

[dario2994]

Nel frattempo se riesci a scrivere delle belle soluzioni di 3 e 5b, e completare quella del problema 6, passamele che le inserisco, ne avevo realizzata una del 3 ma ho osservato qualche giorno fa essere sbagliata (e infatti ieri ci abbiamo messo un po' a correggere i relativi esercizi), del 5b non mi sono posto più di tanto il problema in quanto era immaginabile che non venisse risolto (mi aspettavo invece qualcosa di più dal 5a), del 6 anche avevo intuito che qualcuno avrebbe trovato la strategia minimizzante ma senza riuscire a dimostrare rigorosamente che si trattava effettivamente di quella di minimo...

Bon... giusto per dire... i problemi erano molto difficili per essere un cesenatico. Che il 5a sia rimasto irrisolto (o forse no?) mi pare normalissimo... è un IMO6 manco troppo vecchio e manco facile... non vedo proprio perchè sarebbe dovuto essere risolto, la soluzione è tra il delirante e il miracoloso... riguardo al 5b invece non capisco cosa ci sia di difficile, a meno di castronerie mie acrobatiche è equivalente a dimostrare che il 2011-esimo polinomio ciclotomico non si scompone, ma quello oltre a essere un fatto noto è pure relativamente facile da dimostrare dato che 2011 è primo (o forse ho preso una cantonata sul 5b? )
Per il 3 ho una soluzione... la scrivo qui come abbozzo nel caso serva: ad ogni divisore associo gli esponenti dei primi congrui a 3,7 che lo compongono... allora fa parte di f(n) se la somma è pari, fa parte di g(n) se la somma è dispari... da qui si riconduce a mostrare che dati $(a_1,a_2,\dots a_k)$ interi positivi (gli esponenti dei primi =3,7 (10) )
$\displaystyle \left|\left\{(b_1,b_2,\dots b_k):\ \forall\ 0\le i\le k 0\le b_i\le a_i\wedge \sum b_i\equiv 1\pmod 2\right\}\right|\le$
$\displaystyle \le \left|\left\{(b_1,b_2,\dots b_k):\ \forall\ 0\le i\le k 0\le b_i\le a_i\wedge \sum b_i\equiv 0\pmod 2\right\}\right|$
E questo si dimostra ad esempio inducendo su k (il passo induttivo è un semplice riarrangiamento a 2 termini )

p.s. battutissimo sul tempo
p.p.s. leggendola al volo quella di sasha mi pare segata il motivo principe dell'errore a occhio mi pare sia che 10 non è divisibile per 4

[bĕlcōlŏn]

Testo nascosto:

(ossia i primi congrui a $-1 \pmod 4$ possono avere solo esponente pari).

Se ho capito quello che hai fatto, i primi congrui a -1 modulo 4 non è detto che debbano avere per forza esponenti pari... può essere anche che un numero pari di fattori congrui a -1 abbia degli esponenti dispari e gli altri abbiano esponenti pari, e in tal caso il prodotto fa sempre 1.

Propongo la mia soluzione. Innanzitutto noto l'insieme dei divisori di $ n $ che termina per $ 1,3,7,9 $ è lo stesso togliendo tutte le potenze di $ 2 $ e $ 5 $. Ora considero la fattorizzazione di $ \dfrac{n}{2^{v_2n}\cdot 5^{v_5n}} $ che chiamo $ \displaystyle\prod_{i=1}^n p_i^{a_i} $, in maniera tale che $ p_1<p_2<...<p_n $. Inoltre, modulo 10, ognuno di questi primi può essere $ 1,3,7,9 $.
Ora dimostro che $ \forall k \leq n $ si ha che $ \displaystyle\prod_{i=1}^k p_i^{a_i} $ è tale che il numero di divisori che terminano per $ 1,9 $ è maggiore o uguale del numero di divisori che terminano per $ 3,7 $.
Parto con $ k=1 $. Però dimostro prima questo lemma.

Lemma: $ n = p_i^{a_i} $ è tale che $ f(n)\geq g(n) $.
Nel caso in cui $ p_i \equiv 1,9 \pmod (10) $ la tesi è chiaramente verificata. Se $ p_i \equiv 3,7 (\pmod 10) $ bisogna scriversi tutti i divisori, ovvero la serie delle potenze $ p_i^{0},p_i^{1},... $ e mostrare che in qualunque punto la si tronchi, il numero di resti 1 e 9 è maggiore del numero di resti 3 e 7. Per fare questo basta notare la periodicità delle potenze:
-Nel caso $ p_i\equiv 3 \pmod (10) $ si ha 1,3,9,7,1,3,... e qui non faccio troppo il formale ma si vede chiaramente che se si tronca in posizione pari si ha uguaglianza, altrimenti si ha il maggiore stretto.
-Nel cao $ p_i\equiv 7 \pmod (10) $ si ha 1,7,9,3,1,7,... e qui come prima.

Quindi comincio col dire che, per il lemma, la tesi vale per $ k=1 $. Ora suppongo valga per un certo $ s $ e dimostro che vale per $ s+1 $. So che, per ipotesi induttiva, $ \displaystyle\prod_{i=1}^s p_i^{a_i} $ è tale che il numero di divisori che terminano con 1,9 (a) è maggiore o uguale del numero di divisori che terminano con 3,7 (b). Quindi $ a \geq b $. Ora chiamo A l'insieme di cardinalità (a+b) di divisori modulo 10 di $ \displaystyle\prod_{i=1}^s p_i^{a_i} $ (contando, quindi gli elementi con molteplicità). I divisori di $ \displaystyle\prod_{i=1}^{s+1} p_i^{a_i} $ sono dati da tutti gli elementi dei vari insiemi $p_{s+1}^0\cdot A$, $p_{s+1}^1\cdot A$,..., $p_{s+1}^{s+1}\cdot A$ dove le potenze di $p_{s+1}$ sono intese modulo 10 e la moltiplicazione fra un numero e un insieme è quell'insieme i cui elementi si ottengono moltiplicando quel numero con tutti quelli dell'insieme.
Ora sia $ X $ il numero delle potenze di $ p_{s+1} $ congrue a 1 o 9, e $ Y $il numero di quelle congrue a 3 o 7. (e per il lemma 1 sappiamo che $ X \geq Y $).
Moltiplicare per 1 o 9 manda 1,9 in 1,9 e 3,7 in 3,7. Mentre moltiplicare per 3,7 manda 1,9 in 3,7 e 3,7 in 1,9. Dunque tutti gli elementi congrui a 1,9 sono $ Xa+Yb $ mentre quelli congrui a 3,7 sono $ Xb+Ya $. Ora basta mostrare che $ Xa+Yb \geq Xb+Ya \Leftrightarrow X(a-b) \geq Y(a-b) $ che è vero dato $ X \geq Y $.

Quindi, in particolare, ho dimostrato che la tesi vale per $ k=n $, ovvero per quel numero iniziale $ \displaystyle\prod_{i=1}^n p_i^{a_i} $.

Spero si capisca tutto
Ps. Battuto sul tempo

[afullo]

p.p.s. leggendola al volo quella di sasha mi pare segata il motivo principe dell'errore a occhio mi pare sia che 10 non è divisibile per 4

Dove risulta la cosa? 10 appartiene alla classe di 1, e la proiezione lo manda in 1.

Quello che a rileggere bene mi convince di meno è che i divisori congrui a 1 modulo 4 possano soltanto avere, oltre a primi congrui a 1 modulo 4, primi congrui a -1 modulo 4 elevati ad esponenti pari, e non ad esponenti dispari. Però, per esempio, 21 = 3 * 7...

[dario2994]

Gli errori in quella di sasha sono 2, uno è che se un numero finisce per 1 nella scrittura decimale non per forza è congruo a 1 modulo 4 e l'altro è che comunque non tutti gli esponenti dei primi congrui a -1 mod 4 (in realtà congrui a 3,7 mod 9) devono essere pari perchè il divisore complessivo sia =1 mod 4 (o finisca per 1,-1 mod 10). L'errore che ho evidenziato io comunque è quasi ininfluente dato che pur parlando di mod 4 alla fine è come se sostituisse semplicemente 1,9 con 1 e 3,7 con -1 che in ogni caso funge (forse per puro caso). L'errore che hai notato tu invece è proprio un errore (la dimostrazione mia è uguale a quella di belcolon, che però è scritta decentemente, suggerisco la lettura di quella )

[sasha™]

Cantonata colossale, chiedo scusa.

Mi giustifico un po' dicendo che il motivo per cui "funziona" non è un miracolo, è che effettivamente 1 e 9 si comportano come 1, mentre 3 e 7 come -1, nel senso che una moltiplicazione per 1 o 9 manda un 1 o un 9 in un 1 o un 9 e un 3 o un 7 in un 3 o un 7, mentre una moltiplicazione per 3 o 7 manda un 1 o un 9 in un 3 o un 7 e viceversa, e questa è l'associazione che ho fatto (sbagliando come un idiota, ma pazienza). Poi ho sbagliato anche il conto dei divisori, è patologico.

[LukasEta]

Scusate, provo a scriverne una io molto poco formale e molto probabilmente con delle falle, però è quello che io sarei riuscito a dire in gara


Per prima cosa noto che non mi interessano gli eventuali divisori di $n$ pari e/o divisibili per $5$: infatti l'ultima cifra di siffatti divisori non potrà mai appartenere all'insieme $(1,3,7,9)$.
-Noto che studiando l'andamento dell'ultima cifra dei prodotti di numeri primi (che compaiono nella fattorizzazione di $n$) che finiscono tutti con 3 (eventualmente anche per se stessi), se i fattori sono in numero pari ottengo come prodotto un divisore che finisce per 1 o per 9.
-Lo stesso dicasi di numeri primi che finiscono con 7.
*-In entrambi i casi, se i fattori sono in numero dispari, otterrò come ultima cifra o 3 o 7.

- Per quando riguarda il prodotto di fattori che finiscono tutti per 1 o per 9, otterrò in ogni caso un prodotto che finisce per 1 o per 9.

Quindi , considerando un divisore qualunque formato dal prodotto di certi numeri primi diversi da 2, prima moltiplico tra loro tutti i primi che finiscono per 1 o per 9, ottenendo un fattore che finisce per 1 o per 9, poi moltiplico questo fattore per i restanti primi che finiscono per 3 o 7 (conto $k$ volte un primo elevato alla $k$). Se questi "restanti primi" sono in numero pari, otterrò un prodotto che finisce per 1 o per 9, altrimenti un prodotto che finisce per 3 o per 7.

-Noto adesso che se i "restanti primi" sono in numeri di $2k+1$, (ottenendo quindi un divisore che finisce per 3 o 7), posso associare a tale divisore $d_1$ un nuovo divisore $d_2$ che si ottiene dividendo il divisore iniziale per un primo(che compare nella fattorizzazione del divisore) che finisce per 3 o per 7 ($d_2$ ha quindi $2k$ numeri primi nella fattorizzazione tali che finiscano per 3 o 7): $d_2$ avrà quindi per quanto detto prima la proprietà di finire per 1 o per 9. Quindi, per ogni divisore di $n$ in cui i "restanti primi" sono in numero dispari,dal momento che tra $0$ e $2k+1$ compresi ci sono tanti numeri pari quanti numeri dispari,a ogni divisore del divisore considerato che finisce per 3 o 7 posso associare un divisore del divisore considerato che finisce per 1 o 9.

-Nel caso in in cui i "restanti primi" del divisore considerato siano in numero pari, dal momento che tra 0 e un numero pari ci sono più numeri pari che numeri dispari, a maggior ragione saranno più i divisori del divisore che finiscono per 1 o 9 di quelli che finiscono per 3 o 7.

-dal momento che non esiste nessun divisore in cui $g(d)>f(d)$, qualunque sia $n$ varrà $f(n)\geq g(n)$.


Lo so, sto delirando

[sasha™]

Per quanto, causa cantonate pazzesche di prima, non abbia diritto di parola, direi che bisogna verificare che i $d_2$ siano tutti distinti. Ho provato a correggere (cioè rifare da capo ) la mia ma mi sono fermato proprio a questo punto. Ci stavo pensando... Forse dire "divido $d_1$ per il più grosso primo tale che..." anziché "per un primo tale che" basta, ora ci penso. EDIT: No, neanche. Bisogna trovare un modo di associarli univocamente.

[afullo]

L'errore che ho evidenziato io comunque è quasi ininfluente dato che pur parlando di mod 4 alla fine è come se sostituisse semplicemente 1,9 con 1 e 3,7 con -1 che in ogni caso funge

Sempre utilizzando il linguaggio delle classi di equivalenza, partizionando l'insieme degli interi positivi che finiscono per 1, 3, 7 o 9, in una classe contenente quelli che finiscono per 1 o 9, e in una contenente quelli che finiscono per 3 o 7, è possibile porre su tale partizione in due classi un'operazione di moltiplicazione tra le classi ben definita, e si ha un isomorfismo di gruppi tra {(3,7);(1,9)} e {-1;1} che associa (3,7) a -1 e (1,9) a 1...

[Children of the forest]

i ragattsi di torino che erano a cesenatico lo scorso anno avranno fatto a questa prova in media 10punti più che a cesenatico dello scorso anno. trovo sciocco giudiicare difficili questi testi.
enigma da 2 a 25, meraldi e yang anche 10punti in più etc etc.

@chi dice che era difficile, troppo per cesenatico. Se andrete a cesenatico vi consiglio di guardare i testi degli scorsi anni, 2010 e 2008 in particolare, perchè mi sa che non l'avete fatto...