Matematiena

.AST .BIO .CHE .EKON .FILOL .FILOS .FIZ .GEO .INF .IST .MAT .Kita

Kalendorius Biblioteka Fotogalerija Video galerija Forumas Nuorodos Apie

Įkėlė: Karolis Karpavičius

2008 gruodžio 11 d., 15:39

Prieš porą savaičių man teko aplankyti vieną kalėdinį kaimelį. Vyriausio Senelio šalčio paklausiau, o kokia Jūsų kaimelio istorija? O jis man atsakė... jo atsakymas skamba lyg uždavinys... Deja, neturiu gerų matematiko savybių, tad prašau Jūsų, mielieji skaitytojai, pagalbos išsiaiškinant Kalėdų kaimelio istoriją:

Daugiau... Komentarai (18)

Pravoslavų Naujametinis uždavinys (tas pats)

Įkėlė: Matas Šileikis

2008 sausio 13 d., 02:00

Naujųjų metų proga senis Vladimiras V. Marozas pasikvietė ant kilimėlio n vaikučių ir dalino jiems k rūšių saldainius, bet jokiam vaikui nedavė dviejų vienodų saldainių, tačiau bent po saldainį gavo visi. Kita vertus, nebuvo tokios rūšies, kurią gautų kiekvienas.
Vaikai buvo godūs, ir viską iš karto sumaumojo, bet pasiliko popierėlius ir jais nesimainė tarpusavy. Padalinus paaiškėjo, kad kokią porą vaikų bepakviestume parodyti, kokius popierėlius turi, jie turėtų po lygiai vieną tos pačios spalvos popierėlį, pvz., galėjo būti taip: Rolandas turėjo raudoną, geltoną ir ultramarino, o Viktoras - raudoną ir oranžinį. Viktoras negali turėti geltono ir ultramarino, o Rolandas negali turėti oranžinio.
Senis Vladimiras iš tiesų buvo užimaskavęs Paulius Medkirtys, pasaulinis matematikas ir jis klausia, kiek mažiausia saldainių rūšių reikėjo tokiam darniam išdalinimui.

Komentarai (18)

Juokingai neįmanomi kombinatorikos uždaviniai

Įkėlė: Matas Šileikis

2007 lapkričio 19 d., 03:00

Noriu pasidalint tuo, ką sužinojau poroje Kembdridžo universiteto kombinatorikos paskaitų. Kombinatorika – matematikos šaka, iš esmės nagrinėjanti ko gero paprasčiausius objektus - baigtinių skaičių aibes – dažnai nustebina tuo, jog sunkius jos uždavinius galima suformuluoti labai paprastai.

Sotieji hipergrafai

Norint išsiaiškinti, ką reiškia elementari kombinatorikos sąvoka grafas, galima užmesti akį kad ir į Vikipediją. Man labiausia patinka toks apibrėžimas: grafas yra baigtinė aibė V (kurios elementai vadinami viršūnėmis) ir jos dvielemenčių poaibių (vadinamų briaunomis) aibė E, t. y., aibė sudaryta iš aibių {a, b}, kur a ir b yra V elementai. Toks apibrėžimas patogus, jį apibendrinant iki savokos r-tolygus hipergrafas (trumpiau vadintinas r-grafu), kuris yra panaši pora (V, E), kur E yra r-elemenčių V poaibių aibė. Spalvotu paveikslėliu kairėje pavaizduotas 3-grafas su trimis briaunomis; dešinėje – pilnasis grafas K₄, kurį galima tapatinti su tetraedru, kadangi kiekvieną briauną atitinka piramidės siena. Sakome, jog grafas H yra grafo G pografis, jei, negriežtai kalbant, galime „uždėti“ H viršūnes ant kurių nors G viršūnių taip, kad kiekviena H briauna sutaptų su kažkuria G briauna.

Taigi, dabar žino- me pakankamai sąvokų, kad galėtume susipažinti su tokia hipergrafų savybe kaip sotumas (galbūt jau įsigaliojęs lietuviškas terminas prisotintas grafas, bet nematau priežasties nevartoti trumpiausio vertimo; juolab tas, kas yra sotus, nėra nei neprivalgęs, nei persivalgęs, o užvalgęs lygiai tiek, kiek reikia). Žodžiu, hipergrafą H vadiname (stipriai) k-sočiuoju, jei jis neturi pografio K_k , bet prie jo pridėjus bet kurią vieną briauną, jame toks pografis atsiranda. Vienas iš kombinatorikos klausimų yra kiek daugiausia briaunų gali turėti n viršūnių k-sotusis r-grafas? Kai r = 2, t. y., nagrinėjame grafus, atsakymas paprastas – Turáno grafas T(n,r-1). (Turán – vengrų matematikas, o á – vengriška „a ilgoji“).

Jis konstruojamas padalinant n viršūnių į r-1 „partiją“ taip, kad aibių dydžiai būtų kuo vienodesni (blogiausiu atveju skiriasi vienetu, kartais – visos vienodo dydžio), bei sujungiant kiekvieną porą viršūnių, priklausančių skirtingoms „partijoms“. r-sotumas akivaizdus: jei pasirenkame bet kurias r viršūnių, bent dvi jų priklauso vienai „partijai“, dėl to yra nesujungtos briauna ir nėra pilnojo pografio viršūnės.

Kita vertus, bendru atveju (r-hipergrafų, r > 2) atsakymas visiškai nežinomas. Ir nors klausimas užduotas jau prieš daug dešimtmečių, niekas negali pasakyti netgi didžiausio skaičiaus briaunų, kurį gali turėti n viršūnių 4-sotusis 3-grafas (t.y., toks, kuriam iki piramidės trūksta vienos briaunos).

Besikertančios aibių sistemos

Žemiau pateikiami du neišspręsti du uždaviniai apie baigtinės aibės poaibių sistemą S, t. y., poaibių aibę, kuriuos pasiūlė vėlgi vengrų matematikas Simonovits ir matematikė Sós (čia vengrų kalbos specialistas galbūt įkištų trigrašį, kad „s“ vengrų kalboje skaitoma „š“).

Jei S yra tokia aibės [n] = {1, 2, ... n} poaibių sistema, kad kiekvienų dviejų jos poaibių A ir B sankirta turi aritmetinę progresiją iš trijų elementų (pvz., 2, 5, 8), tai S turi ne daugiau kaip 2^(n-3) elementų.
Jei S yra sistema grafų su viršūnių aibe [n] = {1, 2, ... n}, o kiekvienų dviejų grafų A ir B sankirtoje galima rasti trikampį, tuomet S turi ne daugiau kaip 2^(n(n-1)/2 – 3) elementų. Pastaba. Grafą galima sutapatinti su aibės [n(n-1)/2] = {1, 2, ... n(n-1)/2} poaibiu, kadangi egzistuoja lygiai n(n-1)/2 poros viršūnių, taigi šiuo atveju grafų sistema yra poaibių sistema. Pasiekimas. Jau įrodyta, kad elementų ne daugiau kaip 2^(n(n-1)/2 – 2).

Erdvės taškų spalvinimas (begalinėmis kreidelėmis)

Kiek mažiausia spalvų reikia, jog galėtume nuspalvinti n-matės (Euklidinės) erdvės R^n taškus taip, kad jokie du taškai esantys lygiai atstumu 1 vienas nuo kito nebūtų vienos spalvos. Pažymėkime tokį skaičių χ(R^n). Pastaba. Įvairiuose grafų teorijos tekstuose χ(G) vadinamas grafo G chromačiuoju skaičiumi. Šiuo atveju įsivaizduojame, kad kiekvieni du taškai, kurie yra vieneto atstumu, yra sujungti briauna.

Ne baisiai sunku įsitikinti, kad 4 ≤ χ(R^2) ≤ 7 (apatiniam įverčiui pabandykite rasti baigtinį grafą plokštumoje kurį galima nuspalvinti ne mažiau kaip 4 spalvomis, o viršutiniam – pabandykite padėlioti tinkamo dydžio daugiakampius) arba jog χ(R^n) ≤ 3^n (teisingai padengiant erdvę kubeliais).

O tai, kuris iš skaičių 4, 5, 6 ar 7 yra tikrasis plokštumos chromatusis skaičius, ir, žinoma, atitinkami skaičiai bet kuriai n-matei erdvei, kol kas lieka neįveiktu iššūkiu (Hadwiger–Nelson uždavinys) rimčiausiems kombinatorikams (tarp manęs ir jūsų sakant, kombinatoriams, jei tai neprikabins matematikams Ostapo Benderio įvaizdžio :).

Daugiau apie neįveiktus kombinatorikos uždavinius

Berašydamas šitą neišsamų straipsnelį, nesunkiai užkliuvau už neišspręstų uždavinių sąrašo. Tai klausimai, į kuriuos atsakiusieji bus pagerbti matematikų pasaulyje (ne, tai ne vietinis skelbimas olimpiados.lt). Ir dažniausiai ne vien už tai, kad įveikė kažką, ko dešimtis metų nepadarė kiti, bet už naujus sprendimo būdus ir atradimus, kurie iškyla išradingam protui besikaunant su vaikiško paprastumo klausimais.

Komentarai (5)

Aštuonkampioji savaitė

Įkėlė: Matas Šileikis

2007 sausio 3 d., 00:13

Taigi antro uždavinėlio sprendimo savaitė baigėsi. Ji buvo sėkmingesnė, nei pirmojo - turime teisingai išsprendusįjį Arūną Radzvilavičių iš Elektrėnų.

Sąlyga: Taisyklingojo n-kampio kraštines ir įstrižaines (t.y., visas kitas atkarpas jungiančias viršūnes) reikia nudažyti taip, kad jokios dvi bendrą tašką turinčios atkarpos nebūtų vienodos spalvos. Kiek mažiausia spalvų reikia tokiam išmoningam nudažymui?

Sprendimas: Visų pirma įrodome, kad reikės bent n spalvų, kadangi galime išrinkti n atkarpų, kurios liečiasi paporiui. Tai, pvz., viršūnę A kaip galą turinčios kraštinės ir įstrižainės, kurių kartu yra n-1 ir jas visas kertanti įstrižainė, kuri jungia viršūnei A gretimas viršūnes.
Kad įrodytume, jog užteks n spalvų, padalinkime atkarpas į n grupių, kurių kiekvienoje atkarpos paporiui nesiliečia. Jei n - nelyginis, kiekvieną tokią grupę sudaro bet kuri kraštinė ir jai lygiagrečios įstrižainės. Jei n - lyginis, situacija 1/2 karto paprastesnė :] Yra n/2 grupių, sudarytų iš kažkurių dviejų labiausiai nutolusių kraštinių ir joms lygiagrečių įstrižainių; bei n/2 grupių, kuriose yra įstrižainė, jungianti dvi viršūnes, "tarp" kurių, einant daugiakampio perimetru, yra viena viršūnė ir jai lygiagrečios atkarpos.
Iki tobulo sprendimo trūksta įrodyti, kad ir nelyginio ir lyginio n atveju "išgraibėm" visas atkarpas ir nepagriebėm nė vienos dusyk. Bet tiek jau to šįkart :]

Naujieji uždaviniai:

1. Aštuonkampio visi kampai lygūs, o kraštinių ilgiai - sveikieji skaičiai. Įrodykite, kad kiekvienų dviejų priešingų jo kraštinių ilgiai vienodi.

2. Du kvadratai susikirsdami sudaro aštuonkampį. Vieno kvadrato krašinės - mėlynos, kito - raudonos. Įrodykite, kad mėlynų aštuonkampio kraštinių ilgių suma lygi raudonųjų kraštinių ilgių sumai.

Komentarai (6)

Savaitės uždavinio atsakymas

Įkėlė: Matas Šileikis

2006 gruodžio 27 d., 06:01

Priminsiu praeitą savaitę pateikto uždavinio sąlygą.

Ar yra natūralusis skaičius n toks, kad jo skaitmenų suma (užrašius jį dešimtainiu pavidalu) lygi 1000, o n kvadrato skaitmenų suma - 1000000 (milijonas)?

Pabandome išspręsti uždavinį su mažais skaičiais: ne 1000, o 1, 2, 3, … Lengvai pastebime, kad skaičiaus 1 skaitmenų suma lygi 1, o jo kvadrato 1^2 – lygi 1 = 1^2. Antru atveju tinka 11, nes 121 skaitmenų suma 4; trečiuoju – 111, kurio kvadratas 12321. Įsismaginę su 11…1 pavidalo skaičiais sustojam ties 1'111'111'111, kurio kvadrato vidury skaitmenys taip išauga, kad „išvirsta“ į nulius ir tuo pagadina visą reikalą.

Pamąstom, kaip išretint vienetus, kad keliant kvadratu vienetai nesisumuotų per gausiai vienoje vietoje. Sakykime, mūsų skaičius tokio pavidalo: 100…0100…0100…1 … 1, t. y. sudarytas tik iš vienetų ir nulių. Tuomet jį galima užrašyti kaip sumą 10^k_1 + 10^k_2 + … 10^k_n., čia k_1, k_2, … - skirtingi neneigiami sveikieji skaičiai. Pakelkime šitą skaičių-sumą kvadratu, pritaikydami formulę (a + b)^2 = a^2 + b^2 + 2ab bendresniu atveju, su didesniu skaičiumi narių, o ne vien a ir b:

(10^k_1 + 10^k_2 + … 10^k_n)^2 =

(10^k_1)^2 + (10^2k_2)^2 + … (10^2k_n)^2 + 2*10^k_1*10^k_2 + 2*10^k_1*10^k_3 + … + 2*10^k_1*10^k_n + 2*10^k_2*10^k_3 + … + 2 * 10^k_{n-1}*10^k_n =

10^2k_1 + 10^2k_2 + … 10^2k_n + 2 * 10^(k_1+k_2) + 2 * 10^(k_1+k_3) + … + 2 * 10^(k_1+k_n) + 2 * 10^(k_2+k_3) + … + 2 * 10^(k_ {n-1}+k_n).

Matom, kad galim gaut skaičių, sudarytą iš vienetų, dvejetų ir daug nulių tarpuose. Tam tereikia užtikrinti, kad su bet kokiais visos sumos k_a + k_b būtų skirtingos (pastebėkime, kad jei a = b, k_a + k_b = 2k_a, o tokio pavidalo yra rodikliai dėmenyse, atitinkančiuose vienetus. Kaip parinkti tokius gerus skaičius k_1, k_2, … k_n? Pavyzdžiui tai gali būti dvejeto laipsniai 2^1 = 2, 2^2 = 4, 2^3 = 8… Galite įsitikinti, kad dviejų tokių dvejeto laipsnių suma 2^a + 2^b lygi 2^c + 2^d tik tada, kai a = c ir b = d (arba, suprantama, a = d, b = c). Vadinasi, jei skaičiai k_i bus skirtingi dvejeto laipsniai, kiekvienas dėmuo 10^2k_i atitiks vienetą sukonstruotojo skaičiaus kvadrate, o 2 * 10^(k_i+k_j) atitiks dvejetą.

Nesunku įsitikinti, kad skaičiaus su n vienetų 10^k_1 + 10^k_2 + … 10^k_n kvadratas turi n vienetų ir n(n-1)/2 dvejetų, taigi jo skaitmenų suma n^2.

Gaila, kad nieks iš moksleivių neatsiuntė teisingo sprendimo, jis būtų buvęs paprastesnis. Tikiuosi, pateiksiu supaprastintąjį variantą, nes tikiu, kad baisoka žiūrėt į tai, ką aš čia ką tik parašiau :)

Komentarai (1)

Savaitės matematikos uždavinys

Įkėlė: Matas Šileikis

2006 gruodžio 18 d., 01:47

Pirmas atsiuntęs sprendimą gaus olimpiados.lt unikalią rankų darbo Kalėdinę atvirutę :]

Daugiau... Komentuoti

Galvosūkis

Įkėlė: Laima Servaitė

2006 gruodžio 13 d., 22:51

Sveiki, matematikai!

Šiltais žiemos vakarais siūlome Jums apsilankyti čia ir išbandyti savo jėgas! Jei turi įdomių užduočių, galvosūkių ir nori jais pasidalinti, rašyk į El. paštas yra apsaugotas nuo paieškos robotų, šiai peržiūrai reikia aktyvuoti Javascript

Pirmąjį galvosūkį galite parsisiųsti čia:

Komentarai (13)

Tylus atidarymas

Įkėlė: Matas Šileikis

2006 gruodžio 5 d., 02:42

Sveiki, matematikos olimpiadų žinovai, sprendėjai, veteranai, jų mokytojai, ir visokio kitokio plauko entuziastininkai!{mosimage}

Tie, kurie jau buvote nusivylę olimpiados.lt matematikos srities apmirimu, galite suklusti, pakarpyti ausimis ir apsilankyti čia dažniau, nes aš, Matas, pats ir būsimų pagalbininkų padedamas stengsiuos čia išrėžti naujienas ir patiekti naudingas žinias.

Iš Jūsų, šviesieji puslapio lankytojai, aš laukiu įvairiausių atsiliepimų, pvz.: (ką dabar pat sugalvojau)

- kokios informacijos trūksta

- kas puslapyje neteisinga

- atsiliepimas, reiškiantis „Aš noriu prisidėti prie olimpiados.lt!“

- pasiūlymų, kaip pakelti matematikos ūkį mūsų Lietuvoje (visų pirma, matyt, olimpiadinės matematikos, ar ne?)

- klausimų apie matematiką, netgi tokio smulkumo kaip „kuo negeras mano 3 uždavinio sprendimas 2006-ųjų Lietuvos komandinėje olimpiadoje?"

Lauksiu aktyvių jūsų nuomonių forume.

Kaip rašo anglai,
Nuoširdžiai Jūsų, Matas

Komentuoti