nessuna terna in progressione

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

nessuna terna in progressione

Messaggio da jordan » 22 set 2008, 01:14

Mostrare che nell’insieme $ S=\{2008,2009,…,4200\} $ è possibile scegliere $ 5^3 $ elementi tali che tra di essi non esiste nessuna terna in progressione aritmetica.

Bonus: Mostrare che nell’insieme $ S'=\{2008,2009,…,3100\} $ è possibile scegliere ancora $ 5^3 $ elementi tali che tra di essi non esiste nessuna terna in progressione aritmetica.
trovare un intero piu piccolo di 3100 tale che la tesi resti ancoravera :wink:
Ultima modifica di jordan il 22 set 2008, 08:15, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.

bestiedda
Messaggi: 213
Iscritto il: 15 nov 2007, 20:20

Messaggio da bestiedda » 22 set 2008, 07:54

prima parte

nell'insieme ci sono $ 2193 $ elementi: le possibili triple di elementi distinti fra gli elementi dell'insieme sono
esattamente $ ${2193\choose 3} $ ovvero $ $\frac{2193\cdot2192\cdot2191}{6}=1755376616 $ . Ora, tre naturali distinti $ $a,b,c $ con $ $a<b<c $ sono in progressione aritmetica se $ $b-a=c-b $ , ovvero se $ $2b=a+c $ . Dunque per calcolare il numero di triple in progressione aritmetica ORDINATA con $ $a,b,c $ scelti nell'insieme $ $S $ basta vedere quante triple soddisfano l'equazione, e questo è abbastanza facile: per $ $b=2008 $ e $ $b=4200 $ non ci sono triple possibili perchè uno fra $ $a $ e $ $c $ dovrebbe essere esterno ad $ $S $. Per tutti gli altri valori di $ $b $ esistono una o più coppie $ $(a,c) $ tali che $ $a+c=2b $:
queste coppie sono tante quanti sono gli elementi di $ $S $minori di $ $b $ solamente se $ $b<3104$ $


continua..
marco

bestiedda
Messaggi: 213
Iscritto il: 15 nov 2007, 20:20

Messaggio da bestiedda » 22 set 2008, 07:55

ovvero nella prima metà di $ $S $ : infatti per ogni elemento minore di $ $b $ ve ne è uno e uno solo maggiore che sommato al primo dia $ $2b $ . Per $ $b>3104 $ , analogamente, abbiamo tante coppie $ $(a,b) $ quanti sono gli elementi di $ $S $ maggiori di $ $b $, perchè per ogni elemento maggiore di $ $b $ ve ne è uno e uno solo minore di $ $b $ tale che i due, sommati, diano $ $2b $. Per $ $b=3104 $ il numero di elementi di $ $S $ minori è uguale al numero di elementi maggiori, ovvero $ $1096 $, da cui esattamente $ $1096 $ coppie $ $(a,c) $. Dunque il numero di triple in progressione aritmetiche con elementi scelti nell'insieme $ $S $ è dato da $ $2(1+2+...+1095)+1096=\frac{2(1095\cdot1096)}{2}=1200120 $. Questo numero va moltiplicato per il numero delle possibili disposizioni di $ $a,b,c $ , ovvero 6, perchè il problema non esplicita che le terne debbano essere in progressione aritmetica ordinata. $ $1200120\cdot6=7200720 $.
Ora togliamo questo numero al numero di triple totali e otteniamo il numero di triple NON in progressione aritmetica : $ $1755376616-7200720=1748175896 $
Il problema chiedeva se era possibile scegliere $ $5^3 $ elementi dell'insieme tali che nessuna possibile terna fosse in progressione aritmetica, ovvero se era possibile che vi fossero $ ${125\choose 3}=317750 $ triple di naturali distinti dell'insieme $ $S $ NON in progressione aritmetica, e questo è palesemente vero in quanto $ $1748175896>317750 $
marco

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 22 set 2008, 08:34

bestiedda ha scritto:[...]Per $ $b>3104 $ , analogamente, abbiamo tante coppie $ $(a,b) $ quanti sono gli elementi di $ $S $ maggiori di $ $b $[...]
Ciao bestiedda :)
potevi anche chiarire xo che $ 3014=AM(2008,4200) $..
bestiedda ha scritto:[...] è dato da $ $2(1+2+...+1095)+1096=\frac{2(1095\cdot1096)}{2}=1200120 $.
$ 2\sum_1^n{i}+(n+1)=(n+1)^2 $..

bestiedda ha scritto:[...]Questo numero va moltiplicato per il numero delle possibili disposizioni di $ $a,b,c $ , ovvero 6, perchè il problema non esplicita che le terne debbano essere in progressione aritmetica ordinata. $ $1200120\cdot6=7200720 $[...]
mmm..e perchè?(questo pezzo poi non c'era nella tua soluzione..)
bestiedda ha scritto:[...]Ora togliamo questo numero al numero di triple totali e otteniamo il numero di triple NON in progressione aritmetica : $ $1755376616-7200720=1748175896 $[...]
Perchè una volta li ordini e una volta no? :?
bestiedda ha scritto:Il problema chiedeva se era possibile scegliere $ $5^3 $ elementi dell'insieme tali che nessuna possibile terna fosse in progressione aritmetica, ovvero se era possibile che vi fossero $ ${125\choose 3}=317750 $ triple di naturali distinti dell'insieme $ $S $ NON in progressione aritmetica, e questo è palesemente vero in quanto $ $1748175896>317750 $
Ma soprattutto questo punto..nessuno nota niente?
The only goal of science is the honor of the human spirit.

bestiedda
Messaggi: 213
Iscritto il: 15 nov 2007, 20:20

Messaggio da bestiedda » 22 set 2008, 14:29

jordan ha scritto:
bestiedda ha scritto:[...]Per $ $b>3104 $ , analogamente, abbiamo tante coppie $ $(a,b) $ quanti sono gli elementi di $ $S $ maggiori di $ $b $[...]
Ciao bestiedda :)
potevi anche chiarire xo che $ 3014=AM(2008,4200) $..
bestiedda ha scritto:[...] è dato da $ $2(1+2+...+1095)+1096=\frac{2(1095\cdot1096)}{2}=1200120 $.
$ 2\sum_1^n{i}+(n+1)=(n+1)^2 $..

non l'avevo notato

bestiedda ha scritto:[...]Questo numero va moltiplicato per il numero delle possibili disposizioni di $ $a,b,c $ , ovvero 6, perchè il problema non esplicita che le terne debbano essere in progressione aritmetica ordinata. $ $1200120\cdot6=7200720 $[...]
mmm..e perchè?(questo pezzo poi non c'era nella tua soluzione..)

la terna (1,2,3) è tale che i suoi elementi sono in progressione aritmetica, ma lo è anche la terna (3,2,1) e la terna (1,3,2) no?
bestiedda ha scritto:[...]Ora togliamo questo numero al numero di triple totali e otteniamo il numero di triple NON in progressione aritmetica : $ $1755376616-7200720=1748175896 $[...]
Perchè una volta li ordini e una volta no? :?

cioè?
bestiedda ha scritto:Il problema chiedeva se era possibile scegliere $ $5^3 $ elementi dell'insieme tali che nessuna possibile terna fosse in progressione aritmetica, ovvero se era possibile che vi fossero $ ${125\choose 3}=317750 $ triple di naturali distinti dell'insieme $ $S $ NON in progressione aritmetica, e questo è palesemente vero in quanto $ $1748175896>317750 $
Ma soprattutto questo punto..nessuno nota niente?
marco

pic88
Messaggi: 741
Iscritto il: 16 apr 2006, 11:34
Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...

Messaggio da pic88 » 22 set 2008, 15:24

Un motivo per cui la soluzione è sbagliata è che il fatto di trovare $ 125 \choose 3 $ terne non implica che esse provengano dallo stesso insieme di 125 elementi.
Questo è chiaro?

Del resto, vale anche$ 1748175896>166167000= {1000 \choose 3} $, però questo non implica che esista un insieme di 1000 elementi che soddisfi le caratteristiche richieste (anzi puoi ben vedere che NON esiste).

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 22 set 2008, 16:00

Soluzione portata da casa (suona ridicolo per un contest fatto a casa...(l'ultima volta che ho portato da casa una soluzione, ho preso uno granchio tremendo... speriamo di non ripetere la performance))

Per comodità traslo tutto in B={1,2,....2193}
A questo punto prendo tutti i numeri dell'insieme che in base 3 hanno solo cifre 1 e 0, si dimostra banalmente che non possono essere in progressione aritmetica e li si contano, e toh, viene fuori 132, più che sufficiente. :D
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

bestiedda
Messaggi: 213
Iscritto il: 15 nov 2007, 20:20

Messaggio da bestiedda » 22 set 2008, 16:02

julio14 ha scritto:Soluzione portata da casa (suona ridicolo per un contest fatto a casa...(l'ultima volta che ho portato da casa una soluzione, ho preso uno granchio tremendo... speriamo di non ripetere la performance))

Per comodità traslo tutto in B={1,2,....2193}
A questo punto prendo tutti i numeri dell'insieme che in base 3 hanno solo cifre 1 e 0, si dimostra banalmente che non possono essere in progressione aritmetica e li si contano, e toh, viene fuori 132, più che sufficiente. :D
1. che idea! da cosa hai avuto questa intuizione?
2. potresti dimostrare che i numeri che in base 3 hanno solo cifre 0 e 1 non sono in progressione aritmetica?
marco

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 22 set 2008, 16:06

bestiedda ha scritto:2. potresti dimostrare che i numeri che in base 3 hanno solo cifre 0 e 1 non sono in progressione aritmetica?
be adesso provaci te no? :wink:
The only goal of science is the honor of the human spirit.

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 22 set 2008, 16:07

1. te l'ho detto che era portata da casa! tra un po' salterà fuori qualcuno a dire perché non sono così geniale ad averla trovata
2. si dimostra banalmente=nella gara l'ho dimostrato, cioè
julio14 nelle soluzioni ha scritto:$ $c-b=b-a\rightarrow 2b=a+c $, assurdo in quanto $ $2b $ ha come cifre solo 0 e 2 mentre $ $a $ e $ $c $ essendo distinti avranno in almeno una posizione cifre diverse, e la somma di queste ultime sarà $ $0+1=1 $ (avendo solo cifre 0 e 1 l'n-esima cifra della somma è determinata unicamente dalle n-esime cifre degli addendi)
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

bestiedda
Messaggi: 213
Iscritto il: 15 nov 2007, 20:20

Messaggio da bestiedda » 22 set 2008, 16:09

jordan ha scritto:
bestiedda ha scritto:2. potresti dimostrare che i numeri che in base 3 hanno solo cifre 0 e 1 non sono in progressione aritmetica?
be adesso provaci te no? :wink:
era stato postato tempo fa un problema che si risolveva allo stesso modo "prog aritmetiche wanted" ricordi? Ci avevo provato l'altra volta e avevo fallito :wink:
marco

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 22 set 2008, 16:15

no, non ci credo :shock: :shock: :shock: :shock: :shock: :shock: :cry:
The only goal of science is the honor of the human spirit.

String
Messaggi: 225
Iscritto il: 01 giu 2008, 17:21

Messaggio da String » 22 set 2008, 16:17

julio14 ha scritto:Soluzione portata da casa (suona ridicolo per un contest fatto a casa...(l'ultima volta che ho portato da casa una soluzione, ho preso uno granchio tremendo... speriamo di non ripetere la performance))

Per comodità traslo tutto in B={1,2,....2193}
A questo punto prendo tutti i numeri dell'insieme che in base 3 hanno solo cifre 1 e 0, si dimostra banalmente che non possono essere in progressione aritmetica e li si contano, e toh, viene fuori 132, più che sufficiente. :D
E' la mia stessa identica soluzione (con l'unica differenza che ho traslato tutto in B={0,1,2...2192} :P ), solo che non so se sono stato abbastanza chiaro nello svolgimento :roll:
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)

bestiedda
Messaggi: 213
Iscritto il: 15 nov 2007, 20:20

Messaggio da bestiedda » 22 set 2008, 16:18

viewtopic.php?t=11280

non era stato risolto, ma qualcuno mi aveva dato quell'indicazione in MP
marco

Avatar utente
Algebert
Messaggi: 330
Iscritto il: 31 lug 2008, 20:09
Località: Carrara
Contatta:

Messaggio da Algebert » 22 set 2008, 16:18

Dal post in birreria:
jordan ha scritto:Adesso pensaci bene (apparte la terna $ (a_0, a_0+1+2, a_0+1+2+3) $ che volendo potevi escludere), considera questo problema:
"Trovare tutti gli $ a<b<c $ interi positivi tali che $ 2T_b=T_a+T_c $, ove $ T_n=\sum_1^n{i} $ è l'n-esimo numero triangolare".
ti sembra tanto banale? :?: :? ...
Scusa se ti sembro stupido ma che cosa intendi con "numero triangolare" :? ?
"[i]What is a good Olympiad problem?[/i] Its solution should not require any prerequisites except cleverness. A high scool student should not be at a disadvantage compared to a professional mathematician."

Rispondi