|
darkosos
Darko Šoš
Beograd
Član broj: 5053
Poruke: 1131
*.dynamic.isp.telekom.rs.
|
U nedostatku bolje ideje:
znaci fora je da je tih osam brojeva dovoljno zbijeno u prostoru 1,2,..17 da njihove medjusobne razlike moraju da se ponove dovoljan broj puta.
Da formalizujem nesto od toga.
Prvo, neka elementi a1 do a8 formiraju rastuci niz (to ne smanjuje opstost);
dalje, posmatrajmo razlike uzastopnih brojeva: a2-a1, a3-a2, ... , a8-a7
njihov zbir je a8-a1 sto ne moze biti vece od 17-1=16;
e sad, treba sastaviti zbir 7 razlika, tako da dobijemo zbir do 16, a da ne ponovimo ni jednu razliku vise od 2 puta;
dakle da pokusamo, pa da vidimo da ne moze :)
razlike su prirodni brojevi od 1 do 16 (u stvari ne vece od 10 jer ne bi mogli da uguramo 7 brojeva);
probacu da pokazem da zbir dve razlika ne bi smeo da bude ni jednak ni veci od 8:
pp da je zbir 2 razlike 8: ostalo je 16 - 8 = 8 da bude zbir jos 5 razlika (od polaznih 7)
ovo jedino je moguce na jedan od sledecih nacina:
4+1+1+1+1 (ponovili smo 1 cetiri puta)
3+2+1+1+1 (ponovili smo 1 tri puta)
2+2+2+1+1 (ponovili smo 2 tri puta).
Ako je zbir veci od 8, situacija je jos gora; necu to strogo pokazivati, ali mozemo da zamislimo da ako nam ostane npr zbir 7 na 5 brojeva,
oduzmemo po 1 iz gornjih zbirova, gde moze, pa cemo dobiti jos vise ponavljanja.
Dakle, ne mozemo imati dve razlike po 4; ako bi imali negde razliku 5 ili vise, onda bi sve ostale bile 2 ili manje i lako se vidi da bi ih bilo dovoljno za trazeno ponavljanje.
Uh, znaci dobio sam da su razlike u skupu {1,2,3,4}, pri cemu 4 ne sme da se ponovi dva puta.
Probajmo da sastavimo zbir do 16 pomocu ovih brojeva a da ne ponovimo ni jedan vise od dvaput:
1+1+2+2+3+3+4 = 16.
Ostalo je jos da se pokaze da ovde negde mora biti "skrivena" jos jedna razlika, sada neuzastopnih clanova niza, koja je u skupu {1,2,3}.
Ako napravimo uredjenu sedmorku, ona korespondira originalnom nizu brojeva:
npr, (1,1,2,2,3,3,4) bi odgovarala brojevima 1, 2, 3, 5, 7, 10, 13, 17;
ali tu npr imamo jos jednu razliku 2: izmedju 3 i 1. To nas navodi na sledece: dve uzastopne razlike a, b brojeva x, y i z donose razliku a+b izmedju z i x.
Posto zbir bilo koje dve razlike iz skupa {1,2,3} donosi novu razliku koja se ponavlja, a 4 ne moze biti svima komsija, to bi bio kraj.
Ako bi hteli da sastavimo zbir razlika manji od 16, vec bi morali da upotrebimo neki od brojeva 1, 2, 3 bar tri puta.
Iskomplikovao sam ga bas, ali eto... Cini mi se da se do zakljucka o razlikama do 4 izmedju komsija moze lakse doci, ali izmice mi.
|
Registrovani: 4 ( zeoN_Rider, Edward Furlong, zelenizub78, Ivan Dimkovic )
Kombinatorni zadatak
