OliForum Matematico

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

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..

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 $

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?

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?

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).

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.

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.

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?

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?

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)

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?

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

no, non ci credo

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.

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 svolgimento

viewtopic.php?t=11280

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

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"

?