Matematikos mėgėjams. Nors „neįveikiamas“ uždavinys įveiktas – prieš akis nauji iššūkiai

Komentarai Prisijungti

Viršuje:   Seniausi | Naujausi

ICan 2010-03-25 22:54
cia ta pati istorija. problema kad 1 ir 13 turi tik po viena galima kaimyna taigi velgi niekaip nesudeliosi skaiciu, 1(. 9, 8 )
xuy 2010-03-26 10:59
DzeiPi 2010-03-26 11:18
ICan teisus. Plačiau jo sprendimą galima pakomentuoti taip: Skaičiai 1, 2, 3, 11, 12, 13 negali būti kaimynais, todėl dalis jų turi išsidėstyti į kas antrą poziciją, o tarp kažkurių diejų iš jų turi būti dviejų pozicijų atstumas. Kadangi 1 ir 13 neturi bendrų kaimynų, tai būtent jie ir yra tie tarp kurių turi įsiterpti kažkurie du skaičiai iš likusiųjų (4, 5, 6, 7, 8, 9, 10). Svarstant kaip likusius skaičius (4, 5, 6, 7, 8, 9, 10) išdėlioti tarp išvardintų, matyti, kad 4 ir 10 turi tik po vieną kaimyną (iš išvardintųjų), tad jie gali būti patalpinami tik nebent į tas dvi pozicijas tarp 1 ir 13. Tačiau 4 ir 10 nėra tarpusavyje kaimynais, todėl abu kartu negali užimti tas dvi pozicijas tarp 1 ir 13. Gavom prieštaravimą. Todėl skaičių neįmanoma sudėlioti taip, kaip prašoma.
rwc 2010-03-26 13:36
DzeiPi 2010-03-26 14:31
Galima ir plačiau: Tarkim skaičiai 1, 2, 3, 11, 12, 13 jau išdėlioti - visi kas antrą poziciją, o tarp 1 ir 13 yra dvi laisvos pozicijos (kad tik taip turi būti pagrįsta mano antstesnio komentaro pradžioje). Bandom išdėlioti likusius skaičius 4, 5, 6, 7, 8, 9, 10. Imam 4 kur jį galima pasodinti tarp išvardintųjų (1, 2, 3, 11, 12, 13). Kadangi 4 gali glaustis tik prie 1 ir nei prie vieno iš kitų išvardintųjų šešetuko, tai vienintelė vieta kur jis gali tikėtis būti pasodintas yra prie 1 iš tos pusės kur yra dvi laisvos vietos (t.y. tarp 1 ir 13). Lygiai taip pat 10 gali tikėtis būti pasadintas tik prie 13 iš tos pusės kur yra laisvos dvi vietos, t.y. tarp 1 ir 13. Bet prie vieneto jau sėdi 4, tad taip išėitų, kad 10 turi sėstis tarp 4 ir 13 (t.y. eilė 1, 4, 10, 13). Bet 10 negali sėdėti prie 4 nes nėra pakankamai jam artimas. Taip gaunam prieštaravimą: 4 ir 10 turi būti tik tarp 1 ir 13, tačiau jie ten negali būti nes nėra tarpusavyje pakankamai artimi.
rwc 2010-03-26 14:35
Kodėl tarp 1 ir 13 yra dvi laisvos pozicijos, o ne tarp, pvz., 2 ir 12? [Edit]Berods, taip, mums reikia dviejų "skylių", vienos ketvertui, kitos dešimtukui... Bet negi čia uždavinys, identiškas pirmajam? Arba profesorius mane išdūrė, arba pats išsidūrė, arba čia kažkur logikos klaida.
DzeiPi 2010-03-26 14:48
Nes nėra tokio skaičiaus, kuris būtų artimas ir 1 ir 13. T.y. reikia skaičius 1, 2, 3, 11, 12, 13 susodinti į 13 vietų taip, kad jie nesėdėtų greta. Akivaizdu, kad kažkur greta bus dvi laisvos vietos. Jei tos dvi greta esančios vietos bus ne tarp 1 ir 13, tai vadinasi tarp 1 ir 13 galės būti tik viena laisva vieta. Tokiu atveju, į tą laisvą vietą tarp 1 ir 13 ką galėsim pasodinti? Nieko! Nes 1 ir 13 bendrų kaimynų neturi. Taigi tarp 1 ir 13 turi būti dvi laisvos vietos.
rwc 2010-03-26 14:51
Pala, tarp 1 ir 11, 2 ir 12, 3 ir 13 nereikia tarpų. Pvz (čia minusą skaityti kaip -x-): 1-11-13-3-2-12-- Ar mums nepakanka skaičių tarp 12--1? Edit: šiuo atveju nepakanka... Išties lieka 4 ir 10.
DzeiPi 2010-03-26 15:01
10 gali pasodinti tik prie 13 ir kad iš kitos jo pusės nebūtų nei vieno šešetuko (1, 2, 3, 11, 12, 13). Taigi, kažkurioje 13 pusėje turi būti bent dvi laisvos vietos; Lygiai taip pat su 4 - gali pasodinti tik prie 1 ir kad iš šešetuko (1, 2, 3, 11, 12, 13) greta niekas daugiau nesėdėtų, tai prie 1 turi būti dvi laisvos vietos. Kadangi dvi laisvos vietos greta gali pasitaikyti tik vieną kartą, tai nebent tarp 1 ir 13.
rwc 2010-03-26 15:13
Taip, su n=10,...13 uždavinys neturi sprendinio, nes turim 6 ne kaimynus ir 2 kaimynus tik vienam iš "nedraugiškų". Lieka per mažai "draugiškų" skaičių (2...5), o reikia 6 "draugiškų", norint sudaryti 6 "nedraugiškų" poras. O kaip su 14,15?
wdm 2010-03-26 15:46
jei norit patikrinti tiesa ar dzeipi teorija galit pasinaudot brutforcu http://uostas.net/?page=cat&cat=list&id=91 cia apt-get php5-cli programele man an laptopo norejo skaiciuot 3 dienas paliksiu per nakti gal kas galingesni kompa turi
rwc 2010-03-26 16:34
DzeiPi teisus. Visgi uždavinys įdomiausias su n=14...21. Su 15 vienas iš sprendinių (reikia praleisti 1 skaičių dviguboje sekoje 7k grįžimui nuo 11; arba prie 2 nuo 12; sukeičiam 1 ir 2; visus >=7 padidinam vienetu): 2-5-1-6-3-8-4-9-13-10-14-11-15-12-7. Su 16, darom tą patį, praleidžiam dar ir 10: 2-5-1-6-3-8-4-9-14-11-15-12-16-13-10-7. Ir taip toliau... Akivaizdu, kad 17 taip pat išreiškiamas dviguba 7k (pasiliekam 6, 11 ir 16). Klausimas: ar visas ilgesnes sekas įmanoma taip "uždaryti" praleidus reikiamą kiekį skaičių? Ir labiausiai "nervinantis" klausimas: kaip su 14?
DzeiPi 2010-03-26 16:42
Vaizdingiau (nežinia ar aiškiau) būtų taip: 1, 2, 3, 11, 12, 13 negali būti kaimynais, tad juos pirmiau ir susodinam, kad nei vienas nebūtų greta kito. Tada ateina 4 ir pareiškia, kad sėdės tik greta 1 ir kad nei vienas iš kitų jau sėdinčių nebūtų greta. 4 tuo tarpų išeina nusiraminti, pakvėpuoti grynu oru. Dėl šio reikalavimo greta 1 paliekam dvi laisvas vietas. Ateina 10 ir pareiškia, kad sėdės tik greta 13 ir nei vieno iš jau sėdinčių (ir susinervinęs irgi išeina). Randam genialų sprendimą - paliekam dvi laisvas vietas tarp 1 ir 13. Ateina kartu 4 ir 10 ir pareiškia, kad greta tikrai jau nesėdės, mat nėra pakankamai artimi. Ir čia mes jau pasiduodam
Evaldas 2010-03-26 16:50
Čia ne į matematiką, o labiau į rimtą galvosūkį panašu man : )
rwc 2010-03-26 17:22
DzeiPi 2010-03-26 19:25
rwc, sugadinai studentams Daivai, Marijai ir Ramūnui visą malonumą, nes pagal indukcinę apibendrinančią išvadą sekantis jų naujas uždavinys galėjo būti 14 skaičių sodinimas rateliu
rwc 2010-03-27 02:41
Beje, su 19 ir 20 pateiktos sekos neteisingos. Klaidos lengvai randamos, ir tai - ta pati klaida. Tačiau teisingos sekos (žinau jas) ir jos tinka tam pačiam "rekurentiniam įterpimui" (1, ... n-4, ||, n, ... 4). Trivialus uždavinys - kas suras?