Pagina 1 di 1
sottoinsieme A
Inviato: 18 dic 2009, 20:12
da danielf
un sottoinsieme A dei numeri naturale compresi tra 1 a 100 è tale che la somma di due suoi elementi qualsiasi è divisibile per 6.quanti elementi può avere al massimo il sottoinsieme A?
io avevo calcolato i numeri divisibili per 6 tra 1 e 100,ma penso sia sbagliato perchè mi viene 16 invece dovrebbe esser 17..
Inviato: 18 dic 2009, 20:21
da jordan
3,9,15,...
Inviato: 18 dic 2009, 20:37
da danielf
jordan ha scritto:3,9,15,...
perchè consideri solo i multipli di 3dispari?
Inviato: 18 dic 2009, 20:49
da jordan
Allora con il tuo esempio hai mostrato che il massimo è almeno 16.
Con il mio esempio ho mostrato che il massimo è almeno 17.
Come si dimostra che il massimo è effettivamente 17?
Ovviamente tutti gli elementi devono avere la stessa parità. Quindi la congruenza modulo 2 è messa apposto, basta sceglierli o tutti pari o tutti dispari.
Resta da sistemare la congruenza modulo 3. Hai per ipotesi che se prendi due a caso allora la loro somma è multipla di 3. Significa che se hai un numero della forma 3k+1 allora tutti gli altri sono 3a-1,3b-1,3c-1,... (perchè sommati a 3k+1 devono dare somma multipla di 3). Ma 3 non divide (3a-1)+(3b-1). Quindi non esiste nessun elemento della forma 3k+1. Lo stesso ragionamento per dire che nessun elemento è della forma 3k-1. Quindi sono tutti multipli di 3.
Adesso quindi tutti e soli i possibili sottoinsiemi che soddisfano la tesi sono:
un solo elemento (che non ha neanche tanto senso..);
due elementi con somma multipla di 6;
un sottoinsieme con almeno 3 elementi che ha tutti gli elementi multipli di 6;
un sottoinsieme con almeno 3 elementi che ha tutti gli elementi della forma 6k+3.
Si vede che il massimo è proprio l'esempio precedente..
Inviato: 12 feb 2010, 12:30
da sharpo
calcolatrice online
jordan ha scritto:Allora con il tuo esempio hai mostrato che il massimo è almeno 16.
Con il mio esempio ho mostrato che il massimo è almeno 17.
Come si dimostra che il massimo è effettivamente 17?
Ovviamente tutti gli elementi devono avere la stessa parità. Quindi la congruenza modulo 2 è messa apposto, basta sceglierli o tutti pari o tutti dispari.
Resta da sistemare la congruenza modulo 3. Hai per ipotesi che se prendi due a caso allora la loro somma è multipla di 3. Significa che se hai un numero della forma 3k+1 allora tutti gli altri sono 3a-1,3b-1,3c-1,... (perchè sommati a 3k+1 devono dare somma multipla di 3). Ma 3 non divide (3a-1)+(3b-1). Quindi non esiste nessun elemento della forma 3k+1. Lo stesso ragionamento per dire che nessun elemento è della forma 3k-1. Quindi sono tutti multipli di 3.
Adesso quindi tutti e soli i possibili sottoinsiemi che soddisfano la tesi sono:
un solo elemento (che non ha neanche tanto senso..);
due elementi con somma multipla di 6;
un sottoinsieme con almeno 3 elementi che ha tutti gli elementi multipli di 6;
un sottoinsieme con almeno 3 elementi che ha tutti gli elementi della forma 6k+3.
Si vede che il massimo è proprio l'esempio precedente..
Perfetto si capisce bene.