nessuna terna in progressione
nessuna terna in progressione
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
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
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.
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..
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
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 $
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
Ciao bestieddabestiedda ha scritto:[...]Per $ $b>3104 $ , analogamente, abbiamo tante coppie $ $(a,b) $ quanti sono gli elementi di $ $S $ maggiori di $ $b $[...]
potevi anche chiarire xo che $ 3014=AM(2008,4200) $..
$ 2\sum_1^n{i}+(n+1)=(n+1)^2 $..bestiedda ha scritto:[...] è dato da $ $2(1+2+...+1095)+1096=\frac{2(1095\cdot1096)}{2}=1200120 $.
mmm..e perchè?(questo pezzo poi non c'era nella tua soluzione..)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 $[...]
Perchè una volta li ordini e una volta 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 $[...]
Ma soprattutto questo punto..nessuno nota niente?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 $
The only goal of science is the honor of the human spirit.
jordan ha scritto:Ciao bestieddabestiedda ha scritto:[...]Per $ $b>3104 $ , analogamente, abbiamo tante coppie $ $(a,b) $ quanti sono gli elementi di $ $S $ maggiori di $ $b $[...]
potevi anche chiarire xo che $ 3014=AM(2008,4200) $..
$ 2\sum_1^n{i}+(n+1)=(n+1)^2 $..bestiedda ha scritto:[...] è dato da $ $2(1+2+...+1095)+1096=\frac{2(1095\cdot1096)}{2}=1200120 $.
non l'avevo notato
mmm..e perchè?(questo pezzo poi non c'era nella tua soluzione..)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 $[...]
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?
Perchè una volta li ordini e una volta 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 $[...]
cioè?
Ma soprattutto questo punto..nessuno nota niente?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 $
marco
-
- Messaggi: 741
- Iscritto il: 16 apr 2006, 11:34
- Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...
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).
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).
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.
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.
1. che idea! da cosa hai avuto questa intuizione?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.
2. potresti dimostrare che i numeri che in base 3 hanno solo cifre 0 e 1 non sono in progressione aritmetica?
marco
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è
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)
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 fallitojordan ha scritto:be adesso provaci te no?bestiedda ha scritto:2. potresti dimostrare che i numeri che in base 3 hanno solo cifre 0 e 1 non sono in progressione aritmetica?
marco
E' la mia stessa identica soluzione (con l'unica differenza che ho traslato tutto in B={0,1,2...2192} ), solo che non so se sono stato abbastanza chiaro nello svolgimentojulio14 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.
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)
ma per seguir virtute e canoscenza"(Dante)
Dal post in birreria:
Scusa se ti sembro stupido ma che cosa intendi con "numero triangolare" ?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? ...
"[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."