Siano $ a_i, i \in \{1,2,...9\} $ interi positivi distinti nella cui fattorizzazione non compaiono mai primi superiori a 3.
Dimostrare che è possibile scegliere una terna il cui prodotto sia un cubo perfetto.
combinatoria base
combinatoria base
The only goal of science is the honor of the human spirit.
-
antosecret
- Messaggi: 214
- Iscritto il: 01 gen 1970, 01:00
- Località: Catania
-
antosecret
- Messaggi: 214
- Iscritto il: 01 gen 1970, 01:00
- Località: Catania
Ok.
Visto che nesuno ci prova posto l'inizio....
I 9 $ a_i $ possono essere fattorizzati nella forma $ 2^{x_i} \cdot 3^{y_i} $
Affinchè il prodotto di 3 a_i sia un cubo perfetto deve essere
$ x_1+x_2+x_3 \equiv 0 \mod3 $
$ y_1+y_2+y_3 \equiv 0 \mod3 $
E' semplice dimostrare che le due congruenze sono vere separatamente (presi 9 numeri, 3 hanno sicuramente lo stesso resto modulo 3 quindi il loro prodotto è congruo a 0 modulo 3).
Non riesco però a dimostrare che le 2 congruenze possono valere contemporaneamente.
Qualcuno mi aiuta???
Visto che nesuno ci prova posto l'inizio....
I 9 $ a_i $ possono essere fattorizzati nella forma $ 2^{x_i} \cdot 3^{y_i} $
Affinchè il prodotto di 3 a_i sia un cubo perfetto deve essere
$ x_1+x_2+x_3 \equiv 0 \mod3 $
$ y_1+y_2+y_3 \equiv 0 \mod3 $
E' semplice dimostrare che le due congruenze sono vere separatamente (presi 9 numeri, 3 hanno sicuramente lo stesso resto modulo 3 quindi il loro prodotto è congruo a 0 modulo 3).
Non riesco però a dimostrare che le 2 congruenze possono valere contemporaneamente.
Qualcuno mi aiuta???
-
antosecret
- Messaggi: 214
- Iscritto il: 01 gen 1970, 01:00
- Località: Catania
Ok. Seguendo il tuo suggerimento...
Lemma 1: E' sufficiente che ci siano 5 coppie distinte (mod 3) affinché ne esistano 3 con somma (0,0).
Dimostrazione:
Prendiamo 5 generiche coppie distinte (x_i,y_i) di interi modulo 3.
Consideriamo i valori di $ x_i $:
1) Se 3 $ x_i $ hanno lo stesso valore, poichè le coppie devono essere distinte, si avrà $ y_1 = 0, y_2 = 1, y_3 = 2 \rightarrow x \equiv 3k \equiv 0 $ e $ y \equiv 1+2+3 \equiv 0 $. E il lemma è dimostrato.
2) Se meno di 3 $ x_i $ hanno lo stesso valore allora, per il pigeon hole, ci sono esattamente 3 valori di $ x_i $ diversi. Allora abbiamo una classe (chiamiamola 1) da un elemento ( in cui ad un $ x_1 $ corrisponde un preciso valore di $ y_1 $ e 2 classi (chiamiamole 2 e 3) in cui gli $ y_i $ assumono 2 valori diversi per ognuna.
Consideriamo allora la somma tra $ y_1 $ e uno dei 2 valori di $ y_2 $.
2.1)Se uno dei 2 valori possibili di $ y_3 $ rende la somma multipla di 3 allora il lemma è dimostrato.
2.2)Se ciò non succede basta considerare la somma con l'altro valore di $ y_2 $. Per questo valore esisterà sicuramente un valore di $ y_3 $ che renda la somma multipla di 3 (infatti se abbiamo 2 valori diversi di $ y_3 $ e li sommiamo a 2 diversi resti modulo 3, almeno una delle somme sarà congrua a 0 modulo 3). Anche in questo caso il lemma è dimostrato.
----
Dimostrazione:
Se tra le 9 coppie ce ne sono almeno 3 che sono, pur essendo distinte, sono congrue tra loro modulo 3 allora il prodotto tra gli $ a_i $ corrispondenti sarà un cubo perfetto. (infatti $ 3k \equiv 0 \mod3 $)
Se ciò non si verifica allora ci saranno al massimo 2 coppie congrue tra loro modulo 3 per ogni classe di congruenza.
Ma allora ci saranno, per il principio dei piccioni, almeno 5 coppie distinte modulo 3.
Quindi, per il lemma 1, ci saranno 3 coppie con somma (0,0) e quindi almeno 3 numeri il cui prodotto sia un cubo perfetto.
---------------------------------------------------------------------
Credo che la dimostrazione funzioni anche se la parte del lemma è decisamente molto contorta (specialmente la fine). Qualcuno ha dei suggerimenti da darmi per migliorarla, anche in vista del rigore necessario a Cesenatico?? (quest'anno parteciperò alle nazionali e sto cercando di prepararmi al meglio...)
Lemma 1: E' sufficiente che ci siano 5 coppie distinte (mod 3) affinché ne esistano 3 con somma (0,0).
Dimostrazione:
Prendiamo 5 generiche coppie distinte (x_i,y_i) di interi modulo 3.
Consideriamo i valori di $ x_i $:
1) Se 3 $ x_i $ hanno lo stesso valore, poichè le coppie devono essere distinte, si avrà $ y_1 = 0, y_2 = 1, y_3 = 2 \rightarrow x \equiv 3k \equiv 0 $ e $ y \equiv 1+2+3 \equiv 0 $. E il lemma è dimostrato.
2) Se meno di 3 $ x_i $ hanno lo stesso valore allora, per il pigeon hole, ci sono esattamente 3 valori di $ x_i $ diversi. Allora abbiamo una classe (chiamiamola 1) da un elemento ( in cui ad un $ x_1 $ corrisponde un preciso valore di $ y_1 $ e 2 classi (chiamiamole 2 e 3) in cui gli $ y_i $ assumono 2 valori diversi per ognuna.
Consideriamo allora la somma tra $ y_1 $ e uno dei 2 valori di $ y_2 $.
2.1)Se uno dei 2 valori possibili di $ y_3 $ rende la somma multipla di 3 allora il lemma è dimostrato.
2.2)Se ciò non succede basta considerare la somma con l'altro valore di $ y_2 $. Per questo valore esisterà sicuramente un valore di $ y_3 $ che renda la somma multipla di 3 (infatti se abbiamo 2 valori diversi di $ y_3 $ e li sommiamo a 2 diversi resti modulo 3, almeno una delle somme sarà congrua a 0 modulo 3). Anche in questo caso il lemma è dimostrato.
----
Dimostrazione:
Se tra le 9 coppie ce ne sono almeno 3 che sono, pur essendo distinte, sono congrue tra loro modulo 3 allora il prodotto tra gli $ a_i $ corrispondenti sarà un cubo perfetto. (infatti $ 3k \equiv 0 \mod3 $)
Se ciò non si verifica allora ci saranno al massimo 2 coppie congrue tra loro modulo 3 per ogni classe di congruenza.
Ma allora ci saranno, per il principio dei piccioni, almeno 5 coppie distinte modulo 3.
Quindi, per il lemma 1, ci saranno 3 coppie con somma (0,0) e quindi almeno 3 numeri il cui prodotto sia un cubo perfetto.
---------------------------------------------------------------------
Credo che la dimostrazione funzioni anche se la parte del lemma è decisamente molto contorta (specialmente la fine). Qualcuno ha dei suggerimenti da darmi per migliorarla, anche in vista del rigore necessario a Cesenatico?? (quest'anno parteciperò alle nazionali e sto cercando di prepararmi al meglio...)
-
antosecret
- Messaggi: 214
- Iscritto il: 01 gen 1970, 01:00
- Località: Catania
La tua dimostrazione ovviamente è giusta, però si può spendere qualche parola in più giusto per rendere un po' più chiaro il ragionamento... Ad esempio:
Supponiamo che non ci siano residui che si ripetono 3 volte nè tra gli $ x_i $ nè tra gli $ y_i $.
Ci saranno allora 5 coppie di cui le prime due con $ x_1 $, la terza e la quarta con $ x_2 $ e la quinta con $ x_3 $, dove $ x_1,x_2,x_3 $ sono tutti i residui mod 3.
Intanto prendo la coppia con $ x_3 $. Insieme a $ x_3 $ ci sarà un $ y_3 $; se questo $ y_3 $ non compare nelle altre quattro coppie sono a posto perché le altre quattro coppie saranno tutte le combinazioni di $ x_1,x_2 $ con $ y_1,y_2 $ (dove $ y_1,y_2,y_3 $ sono tutti i residui mod 3) e mi basta prendere ad esempio $ (x_1,y_1) $ e $ (x_2,y_2) $.
Se invece $ y_3 $ compare in un'altra coppia (in più di due non può comparire), supponiamo che compaia insieme a $ x_2 $; allora escludo questa coppia $ (x_2,y_3) $ e prendo invece l'altra con $ x_2 $, diciamo $ (x_2,y_2) $. Le due rimanenti dovranno necessariamente essere $ (x_1,y_1) $ e $ (x_1,y_2) $, e mi basta prendere $ (x_1,y_1) $.
In conclusione riesco sempre a prendere tre coppie del tipo $ (x_1,y_1),(x_2,y_2),(x_3,y_3) $ con somma $ (0,0) $ mod 3.
Supponiamo che non ci siano residui che si ripetono 3 volte nè tra gli $ x_i $ nè tra gli $ y_i $.
Ci saranno allora 5 coppie di cui le prime due con $ x_1 $, la terza e la quarta con $ x_2 $ e la quinta con $ x_3 $, dove $ x_1,x_2,x_3 $ sono tutti i residui mod 3.
Intanto prendo la coppia con $ x_3 $. Insieme a $ x_3 $ ci sarà un $ y_3 $; se questo $ y_3 $ non compare nelle altre quattro coppie sono a posto perché le altre quattro coppie saranno tutte le combinazioni di $ x_1,x_2 $ con $ y_1,y_2 $ (dove $ y_1,y_2,y_3 $ sono tutti i residui mod 3) e mi basta prendere ad esempio $ (x_1,y_1) $ e $ (x_2,y_2) $.
Se invece $ y_3 $ compare in un'altra coppia (in più di due non può comparire), supponiamo che compaia insieme a $ x_2 $; allora escludo questa coppia $ (x_2,y_3) $ e prendo invece l'altra con $ x_2 $, diciamo $ (x_2,y_2) $. Le due rimanenti dovranno necessariamente essere $ (x_1,y_1) $ e $ (x_1,y_2) $, e mi basta prendere $ (x_1,y_1) $.
In conclusione riesco sempre a prendere tre coppie del tipo $ (x_1,y_1),(x_2,y_2),(x_3,y_3) $ con somma $ (0,0) $ mod 3.
-
antosecret
- Messaggi: 214
- Iscritto il: 01 gen 1970, 01:00
- Località: Catania