Matematikos mėgėjams. Ant ko laikosi pasaulis?

Kiekvienoje eiluteje yra po aritmetine progresija, Kiekviename stulpelyje yra po aritmetine progresija. Norint jas visas isardyti reikia ismesti istrizaine (91 - 10), taciau kita likusi istrizaine (1 - 10) bus vienintele (neradau kitu) aritmetine progresija. Gyvensim

Jo visgi neimanoma, apsizioplinau truputi

Kad panaikinti 91 aritmetinę progresiją, kurių d=1, būtina sunaikinti skaičius 10,20,30,40,50,60,70,80,90,100. Bet tada liks dar (82+10)*9/2=414 geometrinių progresijų, kurių d=2...10.

Norint kad iš duotų skaičių susidarytų aritmetinė progresija turi būti d<12, vadinasi, norint panaikinti bet kokią progresija, reikia pašalinti 11 skaičių. Geriausiu atveju pašalinti bus tik 10. Atsakymas: pasaulis - amžinas

Kad nesusidarytų progresija, reikia, kad bent: skaičiai išsidėstytų visose eilutėse ir visuose stulpeliuose bei kad atstumai tarp jų būtų mažesni už 11. Vienintelis toks variantas - išbraukyti šalutinę įstrižainę, ar bet kurią jai gretimą. Pvz., x ir x+11 netenkina, nes x+1,...,x+10 sudaro d+1 progresiją. x ir x+10 netinka, nes netenkinama "visų išbrauktų stulpelių sąlyga". Mažesnio už 9 šuoliuko negalime imti, nes arba apimsime mažesnį nei 90 plotą, arba turėsime pasinaudoti šuoliuku per 11. Vadinasi, lieka išbraukyti 9n+k seką, tačiau tada turėsime progresijas 9n+k+1, 9n+k+2 ir t.t.. Todėl pasaulio pabaigos niekada nebus. Tą pačią išvadą galime prieiti redukuodami: tarkime, turime n x n matricą, kurioje reikia išbraukti n langelių, kad negautume progresijos. Paimkim 2x2 - akivaizdu, kad sprendinio nėra. Paimkime bet kurį variantą ir įrašykime į 3x3 matricą. Bet kuriuo atveju gauname arba neužpildytą stulpelį, arba eilutę, arba 3 ilgio tarpą, arba išsidėstymą šalutinėje įstrižainėje+k. 4x4 tokiu būdu galime suredukuoti iki 3x3, 5x5 - į 4x4 ir t.t., įskaitant ir 10x10.

Na, nepyk, bet taip iki galo manęs ir neįtikinai, ir štai kodėl: manau, kad klysti teigdamas "Mažesnio už 9 šuoliuko negalime imti". Imkim ir pasvarstykim. Turime matricą iš 100 elementų bei 91-ą aritmetinę progresiją , kurios žingsnis yra 1 ir kurias norime "sunaikinti". Be abejonės tu teisus, atkreipdamas dėmesį į 9 "šuoliuką", tik teiginys turėtų būti "šuoliuko Tuo labai nesunku save įtikinti: jei skaičius išdėstytume tiese, tai, turėdami tokią "liniuotę", nesunkiai pamatytume, kad tarp dešimties kuoliukų (išbrauktų skaičių) yra 9 tarpai. Jei tie tarpai apimtų 9-ias duobutes (neišbrauktus skaičius), tai taip susmaigstydami kuoliukus apimtume 9x9=81 duobutes ir, jei pridėtume užimtas duobutes su kuoliukais, viso susidarytų 91 duobutė, taigi kraštams lieka viso labo 9 duobutės. Čia vėlgi labai nesunku susigaudyti, kad palikdami kraštams daugiau (bet išlaikydami 9 šuoliukų sąlygą ir kraštams), kažkur kuoliukų sekoje tuos tarpus galėsime sumažinti Kaip pavyzdį galima paimti ir jau minėtą skaičių aibę {10, 19, 28, 37, 46, 55, 64, 73, 82, 91} - įstrižainę, kuri "sunaikins" visas aritmetines progresijas, kurių žingsnis 1, o "šuoliukas" viso labo tik 8 Beje prie šios aibės dar sugrįšiu

Taigi, po šiokio tokio nusivylimo, visgi niekaip nedavė ramybės klausimas - o kaip yra iš tikrųjų? Ne itin daug įdėjus pastangų, galima nesunkiai suvokti, kad galimų aritmetinių progresijų skaičių, prie to pačio aritmetinės progresijos skirtumo, aibė taip pat sudaro aritmetinę progresiją iš 11 elementų, o a=1 ir d=9. Taigi, iš viso yra 506 skaičių 10 iš 100 rinkiniai, kurio elementai sudaro aritmetinę progresiją. Ir galų gale norint tiksliai atsakyti į uždavinio klausimą, reikia pačiam atsakyti, ar egzistuoja toks skaičių 10 iš 100 rinkinys, kurio sankirta su visais iš aukščiau 506 rinkinių nebūtų lygi 0. Šiokia tokia neviltis apima, kai susikaičiuoji, kad egzistuoja 17310309456440 skirtingų skaičių 10 iš 100 rinkinių ir juos visus patikrinti užimtų tikrai ženklią gyvenimo dalį... Kad nenueiti šiuo, anaiptol ne pačiu racionaliausiu keliu, gerb. doc. R. Kašuba labai pagelbėjo formuluodamas uždavinio sąlygą Taigi, imame uždavinio sąlygos skaičių kvadratą ir bandome "bombarduoti", braukdami skaičius. Kad tai prasmingai ir logiškai daryti, pasiremiame keliomis sąlygomis: 1) kaip ne sykį buvo pastebėta, kad bet kuris stupelis ar eilutė sudaro aritmetinę progresiją, todėl, turėdami viso labo 10 "šūvių", nesunkiai suvokiame, kad vienoje elutėje ar stupelyje gali būti tik po vieną "šūvį"; 2) atstumas tarp paeiliui einančių skaičių negali būti didesnis kaip 9 (naikiname visas progresijas, kurios skirtumas 1). Imame pirmą stulpelį {1,11,21,31,41,51,61,71,81,91}. Ką gi, pradedame nuo pirmo elemento "1". Nesunku įsitikinti, kad jo negalima išbraukti nenusižengiant paminėtoms sąlygoms, nes išlaikydami tarpą, ne didesnį 9, sekantis, kurį turėtume braukti, būtų vienas iš {2,3,...,11}, bet tai prieštarautų 1-ai sąlygai. Nesunku įsitikinti, kad vienintelis varinatas, kuris neprieštarautų abiems sąlygoms - "91". Imant paskutinį stulpelį (tik žiūrint skaičių mažėjimo kryptimi), taip pat nesunku įsitikinti, kad vienintelis variantas - išbraukti "10". Imame 2-ą stulpelį {12,22,32,42,52,62,72,82} (atsižvelgiau, kad "10" ir "91" jau išbraukti). "12" išbraukti negalime, nes atsižvelgiant į 1-ą ir 2-ą sąlygą, turėtume braukti "31", bet jis tame pačiame stulpelyje, kaip ir "91". Taigi, vėl vienintelis variantas - "82". Analgiškai priešpaskutiniame - "19". Taigi, jau išbraukėme "10", "19", "82" ir "91". Turėdami tai mintyje ir analogiškai samprotaudami, nesunkiai randame, kad norint išpildyti abi sąlygas - jas tenkins variantas - {10, 19, 28, 37, 46, 55, 64, 73, 82, 91}. Bet čia, net ir per daug neįgudusia akimi, galima pastebėti, kad kita įstrižainė {1,12,23,34,45,56,67,78,89,100} - taip pat aritmetinė progresija, bet jos nei vienas elementas po mūsų "šaudymo" nenukentėjo! Taigi, per daug nesijaudinant dėl likusių 17310309456439 variantų, galima visiškai užtikrintai teigti, kad bent jau dėl šios priežasties pasaulio pabaiga neateis

ar dar nenusibodo?

Tai išplaukia vienas iš kito. Jei eisime mažiau nei per 9, tuomet praleisime vieną stulpelį, ir į jį turėsime grįžti arba 11 šuoliuku, arba neužteks po vieną skaičių eilutėje (t.y., turėsime sukombinuoti tokį 11 ar didesnį šuoliuką keliais mažesniais).

progresiją: visada surasi tokį "ėjimą žirgu", kuriuo atliksi 10 žingsnių. Kad darydamas kitokį žingsnį nei n-1, iš karto praloši, ir galiausiai praloši visus ėjimus padaręs tokiu žingsniu. Tereikia išnagrinėti 3 variantus, ir - bam - įrodymas.

Sekoje 1,2,3,...,100 yra pasislėpę 505 aritmetinės progresijos (galit patikrint). Jeigu įrodytume, kad išmetus 10 skaičių, nesugadinamos lieka nors viena iš 505 aritmetinių progresijų, tai - pasaulis išgelbėtas. Bet... maksimaliai mes galime sugadinti tik 500 aritmetinių progresijų. Todėl, kad vienas išmestas skaičius daugiausiai gali sugadinti 50 progresijų. (Nes formuleje: a+d*n=konkretus skaičius nuo vieno iki 100, d ir n parinkti yra 50 būdų).

Paskutinių tavo teiginių dėl d ir n parinkimo nesupratau - gal gali tiksliau?

O kodėl tarpai tarp išbraukiamų skaičių turi būti vienodi? Be to pirmasis skaičius, kurį galėtume braukti atrodytų yra bet kuris iš {1,...,10}, kaip ir paskutinis, kurį išbrauktume vienas iš {91,...,100}, t.y. kraštams - pradžiai ir pabaigai - gali būti palikta nuo 9 iki 18 neišbrauktų skaičių, todėl kaip ir galėtų užtekti apimti ir mažesnį, t.y. 82 plotą. Taigi norėjau pasakyti tik tiek, kad skaitydamas pasigedau įrodymų, pagrindžiančių tavo teiginius

kitas išdėstymas turės bent vieną dešimties langelių skylę. Akivaizdžiau nei akivaizdu.

Na, nepyk, kad taip "prisikabinau" prie tavo įrodymo, bet visgi norisi, kad uždavinio sprendimas būtų įrodytas taip, kad, net ir tokiam, kaip aš, pakankamai toli esančiam nuo mokslo, nekeltų jokių abejonių. Dabar skaitant tavo teiginius, susidaro įspūdis, kad kai kur vadovaujamasi nuojauta, o ne griežtu įrodymu. Imkime kad ir paskutinius teiginius: skaičių seką - šalutinę įstrižainę. Dabar belieka parodyti bent vieną progresiją, su kuria ši įstrižainė neturi sankirtos, ir uždavinys - išspręstas Taigi, įrodinėjant trečią teiginį gaunamos tokios išvados, kad toliau nieko nebereikia. Štai todėl man kilo įtarimų, kad tavo trečias teiginys įrodytas buvo "iš akies" ar nuojautos.

Gerai, eisiu kitaip. Imu tik d1 sekas. Tarkim, kad pirmų ir paskutinių 9 langelių ginti nereikia. Reikia apginti tarpinius - nuo 10 iki 91. Vienintelis variantas, nepaliekant >9 tarpo, yra: 10,19,28,37,46,55,64,73,82,91. Jei kurį nors +9 pakeisime į mažesnį, tai privalėsime kitur turėti >9. T.y., mums reikia apimti 9*10+1 plotą dešimčia ėjimų, neviršijančių 9. Vienintelis būdas- eiti per 9. Jokios nuojautos, akivaizdu. Beje, gal kas nustatys, kiek reikia "išsprogdinti" mažiausiai langelių, ir pasiūlytų išsidėstymą, kad "pasaulio pabaiga" galėtų įvykti? Hint: "visi dešimti" saugo nuo d1,d3,d7,d9 bet nesaugo nuo d2,d4,d5,d6,d8,d10.