2007 interi
-
pi_greco_quadro
- Messaggi: 158
- Iscritto il: 01 gen 1970, 01:00
- Località: Verona
2007 interi
Dunque... ci vengono dati $ 2007 $ interi positivi distinti e sappiamo che, comunque ne scegliamo $ 10 $, troviamo sempre lo stesso minimo comune multiplo. Allora qual'è la cardinalità massima di un sottoinsieme dei numeri dati e tale che tutti i suoi elementi siano coprimi tra di loro?
Disco es cultura, metal es religion (Metal py)
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"
Mi sembra o banale, o mal posto, o ambiguo.
Se intendi "per un'opportuna scelta dei 2007 interi", allora la soluzione è 2007. Basta prendere 2007 primi distinti.
Se invece intendi "per qualunque scelta dei 2007 interi", allora il problema è ambiguo, infatti prendendo 2008 primi distinti, allora la scelta
$ \{ p_0 p_1, p_0 p_2, p_0 p_3 \dots p_0 p_{2007} \} $
non ha nessun sottoinsieme di numeri coprimi, se intendi un sottinsieme con MCD = 1; in alternativa la soluzione è 1, se intendi un sottoinsieme di interi coprimi a due a due.
Se intendi "per un'opportuna scelta dei 2007 interi", allora la soluzione è 2007. Basta prendere 2007 primi distinti.
Se invece intendi "per qualunque scelta dei 2007 interi", allora il problema è ambiguo, infatti prendendo 2008 primi distinti, allora la scelta
$ \{ p_0 p_1, p_0 p_2, p_0 p_3 \dots p_0 p_{2007} \} $
non ha nessun sottoinsieme di numeri coprimi, se intendi un sottinsieme con MCD = 1; in alternativa la soluzione è 1, se intendi un sottoinsieme di interi coprimi a due a due.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
pi_greco_quadro
- Messaggi: 158
- Iscritto il: 01 gen 1970, 01:00
- Località: Verona
No scusa... l'insieme che ci viene dato deve rispettare la proprietà che comunque scelti $ 10 $ elementi al suo interno, essi abbiano lo stesso minimo comune multiplo, quindi per esempio non ci potrà essere l'insieme con i 2007 primi perché non soddisfa tale proprietà...
Il testo originale comunque diceva We are given 2007 distinct positive integers, any 10 of which have the same least common multiple. Find the maximum number of pairwise relatively coprime numbers among them...
Quindi il senso è quello. Se ci sono altri dubbi chiedi pure. Ciao
Il testo originale comunque diceva We are given 2007 distinct positive integers, any 10 of which have the same least common multiple. Find the maximum number of pairwise relatively coprime numbers among them...
Quindi il senso è quello. Se ci sono altri dubbi chiedi pure. Ciao
Disco es cultura, metal es religion (Metal py)
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"
Got it. Per punizione scriverò 10 volte la frase...il minimo comune multiplo e il massimo comun divisore sono due cose diverse
il minimo comune multiplo e il massimo comun divisore sono due cose diverse
il minimo comune multiplo e il massimo comun divisore sono due cose diverse
il minimo comune multiplo e il massimo comun divisore sono due cose diverse
il minimo comune multiplo e il massimo comun divisore sono due cose diverse
il minimo comune multiplo e il massimo comun divisore sono due cose diverse
il minimo comune multiplo e il massimo comun divisore sono due cose diverse
il minimo comune multiplo e il massimo comun divisore sono due cose diverse
il minimo comune multiplo e il massimo comun divisore sono due cose diverse
il minimo comune multiplo e il massimo comun divisore sono due cose diverse
...sigh...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Ok. Dopo la figuraccia sul m.c.m., ho un debito con questo problema; cerchiamo di colmarlo. La risposta è 9.
Notazione: Chiamo $ A $ l'insieme di 2007 interi.
Sia $ M $ il m.c.m. di dieci elementi qualunque di $ A $ (il valore di $ M $ non dipende per ipotesi dalla particolare scelta della decupla).
Fissato un primo $ p $, sia $ f(p) $ la massima potenza di $ p $ che divide $ M $, ossia $ p^{f(p)} \big \| M $.
Consideriamo l'insieme degli elementi di $ A $ che non sono divisi per $ p^{f(p)} $. Indico con $ A_p $ tale insieme. In simboli:
$ $ A_p := \left \{ a \in A \big | v_p(a) < f(p) \right \} $.
-------
E' possibile scegliere $ A $ in modo che ve ne siano 9 coprimi a due a due.
Dim.: Siano $ p_1, p_2, \dots, p_{1998} $ numeri primi distinti. Sia $ $ Q:= \prod_{i=1}^{1998} p_i $. Scegliamo $ A $ composto dai seguenti elementi:
$ $ a_1 = \prod_{i=1}^{222} p_i $
$ $ a_2 = \prod_{i=223}^{444} p_i $
$ \vdots $
$ $ a_9 = \prod_{i=1777}^{1998} p_i $
$ $ b_1 = \frac{Q}{p_1} $
$ $ b_2 = \frac{Q}{p_2} $
$ \vdots $
$ $ b_{1998} = \frac{Q}{p_{1998}} $
EDIT: corretti i b_i. Grazie.
I primi 9 sono coprimi a due a due. Dico che se se ne prendono 10, il m.c.m. della decupla è $ Q $.
Infatti, ci sono due possibilità. Se almeno due sono dei $ b_i $, il loro m.c.m. è $ Q $. Se invece solo uno è un $ b_i $, allora devo aver scelto tutti e nove gli $ a_i $, quindi il loro m.c.m. è di nuovo $ Q $. []
-------
Fatto: Per ogni primo $ p $, $ A_p $ ha al massimo 9 elementi.
Dim.: Se avesse almeno 10 elementi, potrei scegliere una decupla tutta contenuta in $ A_p $. Il m.c.m. di tale decupla non è divisibile per $ p^f(p) $, quindi non è $ M $. Assurdo. []
Comunque scelto $ A $, non è possibile sceglierne 10 di essi coprimi a due a due.
Dim: Supponiamo invece che sia possibile scegliere 10 interi di $ A $ a due a due coprimi. Sia $ B $ l'insieme di tali 10 interi.
Sia $ p $ un primo. Voglio dimostrare che ogni numero in $ A \setminus B $ è divisibile esattamente per $ p^{f(p)} $.
Se $ p $ è un primo che non divide $ M $, allora banalmente $ f(p) = 0 $ e tutti i numeri sono divisibili per $ p^{f(p)} = 1 $.
Sia $ p $ un primo che invece divide $ M $. Dato che $ A_p $ ha al più 9 elementi, esiste un elemento di $ B $ divisibile per $ p $. Dato che devono essere coprimi, nessun altro elemento di $ B $ è divisibile per $ p $, quindi $ A_p $ è constituito esattamente dai 9 elementi di $ B $ non divisibili per $ p $. Ma allora tutti gli elementi di $ A \setminus B $ sono divisibili esattamente per $ p^{f(p)} $.
Ma allora tutti gli elementi di $ A \setminus B $ hanno la medesima fattorizzazione in primi, quindi non possono essere distinti [anzi, sono tutti uguali a $ M $]. Assurdo. []
Notazione: Chiamo $ A $ l'insieme di 2007 interi.
Sia $ M $ il m.c.m. di dieci elementi qualunque di $ A $ (il valore di $ M $ non dipende per ipotesi dalla particolare scelta della decupla).
Fissato un primo $ p $, sia $ f(p) $ la massima potenza di $ p $ che divide $ M $, ossia $ p^{f(p)} \big \| M $.
Consideriamo l'insieme degli elementi di $ A $ che non sono divisi per $ p^{f(p)} $. Indico con $ A_p $ tale insieme. In simboli:
$ $ A_p := \left \{ a \in A \big | v_p(a) < f(p) \right \} $.
-------
E' possibile scegliere $ A $ in modo che ve ne siano 9 coprimi a due a due.
Dim.: Siano $ p_1, p_2, \dots, p_{1998} $ numeri primi distinti. Sia $ $ Q:= \prod_{i=1}^{1998} p_i $. Scegliamo $ A $ composto dai seguenti elementi:
$ $ a_1 = \prod_{i=1}^{222} p_i $
$ $ a_2 = \prod_{i=223}^{444} p_i $
$ \vdots $
$ $ a_9 = \prod_{i=1777}^{1998} p_i $
$ $ b_1 = \frac{Q}{p_1} $
$ $ b_2 = \frac{Q}{p_2} $
$ \vdots $
$ $ b_{1998} = \frac{Q}{p_{1998}} $
EDIT: corretti i b_i. Grazie.
I primi 9 sono coprimi a due a due. Dico che se se ne prendono 10, il m.c.m. della decupla è $ Q $.
Infatti, ci sono due possibilità. Se almeno due sono dei $ b_i $, il loro m.c.m. è $ Q $. Se invece solo uno è un $ b_i $, allora devo aver scelto tutti e nove gli $ a_i $, quindi il loro m.c.m. è di nuovo $ Q $. []
-------
Fatto: Per ogni primo $ p $, $ A_p $ ha al massimo 9 elementi.
Dim.: Se avesse almeno 10 elementi, potrei scegliere una decupla tutta contenuta in $ A_p $. Il m.c.m. di tale decupla non è divisibile per $ p^f(p) $, quindi non è $ M $. Assurdo. []
Comunque scelto $ A $, non è possibile sceglierne 10 di essi coprimi a due a due.
Dim: Supponiamo invece che sia possibile scegliere 10 interi di $ A $ a due a due coprimi. Sia $ B $ l'insieme di tali 10 interi.
Sia $ p $ un primo. Voglio dimostrare che ogni numero in $ A \setminus B $ è divisibile esattamente per $ p^{f(p)} $.
Se $ p $ è un primo che non divide $ M $, allora banalmente $ f(p) = 0 $ e tutti i numeri sono divisibili per $ p^{f(p)} = 1 $.
Sia $ p $ un primo che invece divide $ M $. Dato che $ A_p $ ha al più 9 elementi, esiste un elemento di $ B $ divisibile per $ p $. Dato che devono essere coprimi, nessun altro elemento di $ B $ è divisibile per $ p $, quindi $ A_p $ è constituito esattamente dai 9 elementi di $ B $ non divisibili per $ p $. Ma allora tutti gli elementi di $ A \setminus B $ sono divisibili esattamente per $ p^{f(p)} $.
Ma allora tutti gli elementi di $ A \setminus B $ hanno la medesima fattorizzazione in primi, quindi non possono essere distinti [anzi, sono tutti uguali a $ M $]. Assurdo. []
Ultima modifica di Marco il 20 feb 2007, 16:21, modificato 1 volta in totale.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
pi_greco_quadro
- Messaggi: 158
- Iscritto il: 01 gen 1970, 01:00
- Località: Verona