ematematikas
Kategorijos +Nauja tema Prisijungti        

Matematikos olimpiadinis uždavinys Nr. 14.1****

Olimpiados Peržiūrų skaičius (5885)

Sąlyga.

Ant vienos kubo viršūnės sėdi zuikis. Trys medžiotojai nemato, kur jis yra. Jie vienu metu šauna į
tris pasirinktas viršūnes (kiekvienas po vieną šūvį). Jei jie nepataiko, zuikis perbėga į kaimyninę
viršūnę (viršūnės yra kaimyninės, jei jos turi bendrą briauną). Kaip medžiotojai turi šaudyti, kad į
zuikį pataikytų padarę po 4 šūvius.


Šį uždavinį mūsų skilčiai pasiūlė forumo narys verbunai.
Ačiū Jam už šaunų uždavinį!

[spoiler]

Sprendimas.

Vaizduokime kubą taip (taškai žymi viršūnes, o brūkšniukai - briaunas):

. ------- .
| \      / |
|  . - .  |
|  |  |  |
|  . - .  |
| /      \ |
. -------- .

Tegul pirmu šūviu medžiotojai šauna į žvaigždute (*) pažymėtas viršūnes.

. --------- .
| \      / |  Pirmas šūvis: medžiotojai šauna į * pažymėtas viršūnes.
|  * - .  |  Jei kiškis nušaunamas, baigta. Tarkime, kad kiškis nenušaunamas.
|  |  |  |  Po šūvio jis tikrai nebus raide O pažymėtoje viršūnėje (nes
|  O-*  |  visos jai gretimos viršūnės pažymėtos * ir kiškio jose prieš šūvį
| /      \ |  nebuvo)
*--------- .

Prieš antrą šūvį kiškis nebus raide X pažymėtoje viršūnėje (anksčiai šią viršūnę žymėjo raidė O). Tegul antru šūviu medžiotojai šauna į * pažymėtas viršūnes.

* ------- O
| \      / |  Antras šūvis: medžiotojai šauna į * pažymėtas viršūnes. Tarkime, kad
|  O-*  |    kiškis nenušaunamas (taigi jo nebuvo * pažymėtoje viršūnėje). Kadangi
|  |  |  |  kiškio nebuvo ir X pažymėtoje viršūnėje, po šūvio jis nebus nei vienoje raide
|  X-O  |  O pažymėtoje viršūnėje (nes tokioms viršūnėms gretimos viršūnės yra visos
| /      \ |  pažymėtos * arba X)
O -------- *

Prieš trečią šūvį kiškio nebus raide X pažymėtose viršūnėse. Tegul trečiu šūviu medžiotojai šauna į * pažymėtas viršūnes.

O --------- X
|  \      /  |    Trečias šūvis. Tarkime, kad kiškis nenušaunamas. Po šūvio jo nebus raide O pažymėtose
|  X -O*  |    viršūnėse.
|    |  |    |
|  O*-XO  |
|  /      \  |
X --------- O*

Prieš ketvirtą šūvį kiškio nebus raide X pažymėtose viršūnėse. Tegul ketvirtu šūviu medžiotojai šauna į * pažymėtas viršūnes. Kadangi daugiau viršūnių nėra, kiškis privalo būti vienoje iš viršūnių, į kurias šauna medžiotojai. Taigi šiuo šūviu kiškis bus nušautas.

X -------- *
| \      / |    Ketvirtas šūvis: po jo kiškis bus nušautas.
|  * -X  |
|  |  |  |
|  X-X  |
| /      \ |
* -------- X

Šį sprendimą mums pasiūlė mūsų forumo narys AncientMariner.
Ačiū ir Jam!

[/spoiler]

Paskutinį kartą atnaujinta 2012-05-15

0

Vaizduokime kubą taip (taškai žymi viršūnes, o brūkšniukai - briaunas):

. ------- .
| \      / |
|  . - .  |
|  |  |  |
|  . - .  |
| /      \ |
. -------- .

Tegul pirmu šūviu medžiotojai šauna į žvaigždute (*) pažymėtas viršūnes.

. --------- .
| \      / |  Pirmas šūvis: medžiotojai šauna į * pažymėtas viršūnes.
|  * - .  |  Jei kiškis nušaunamas, baigta. Tarkime, kad kiškis nenušaunamas.
|  |  |  |  Po šūvio jis tikrai nebus raide O pažymėtoje viršūnėje (nes
|  O-*  |  visos jai gretimos viršūnės pažymėtos * ir kiškio jose prieš šūvį
| /      \ |  nebuvo)
*--------- .

Prieš antrą šūvį kiškis nebus raide X pažymėtoje viršūnėje (anksčiai šią viršūnę žymėjo raidė O). Tegul antru šūviu medžiotojai šauna į * pažymėtas viršūnes.

* ------- O
| \      / |  Antras šūvis: medžiotojai šauna į * pažymėtas viršūnes. Tarkime, kad
|  O-*  |    kiškis nenušaunamas (taigi jo nebuvo * pažymėtoje viršūnėje). Kadangi
|  |  |  |  kiškio nebuvo ir X pažymėtoje viršūnėje, po šūvio jis nebus nei vienoje raide
|  X-O  |  O pažymėtoje viršūnėje (nes tokioms viršūnėms gretimos viršūnės yra visos
| /      \ |  pažymėtos * arba X)
O -------- *

Prieš trečią šūvį kiškio nebus raide X pažymėtose viršūnėse. Tegul trečiu šūviu medžiotojai šauna į * pažymėtas viršūnes.

O --------- X
|  \      /  |    Trečias šūvis. Tarkime, kad kiškis nenušaunamas. Po šūvio jo nebus raide O pažymėtose
|  X -O*  |    viršūnėse.
|    |  |    |
|  O*-XO  |
|  /      \  |
X --------- O*

Prieš ketvirtą šūvį kiškio nebus raide X pažymėtose viršūnėse. Tegul ketvirtu šūviu medžiotojai šauna į * pažymėtas viršūnes. Kadangi daugiau viršūnių nėra, kiškis privalo būti vienoje iš viršūnių, į kurias šauna medžiotojai. Taigi šiuo šūviu kiškis bus nušautas.

X -------- *
| \      / |    Ketvirtas šūvis: po jo kiškis bus nušautas.
|  * -X  |
|  |  |  |
|  X-X  |
| /      \ |
* -------- X

0

AncientMarinerVaizduokime kubą taip (taškai žymi viršūnes, o brūkšniukai - briaunas):

pažymėk kubo viršūnes, kaip įprasta : 000,001,010,100,011,101,110,111, kur dvi viršūnės yra gretimos,
jei jo pavadinimas skiriasi vienu simboliu. Pvz, 101 turi kaimynus 111,001,100. Taip lengviau bus užrašyti, kur
šaudė.

0

verbunai
AncientMarinerVaizduokime kubą taip (taškai žymi viršūnes, o brūkšniukai - briaunas):

pažymėk kubo viršūnes, kaip įprasta : 000,001,010,100,011,101,110,111, kur dvi viršūnės yra gretimos,
jei jo pavadinimas skiriasi vienu simboliu. Pvz, 101 turi kaimynus 111,001,100. Taip lengviau bus užrašyti, kur
šaudė.


Aišku, žymėjimas yra daugiausia stiliaus ir skonio klausimas, bet šiuo atveju drįsčiau prieštarauti. Vizualus žymėjimas yra tiesiog vaizdesnis... Nebent neįmanoma įžiūrėti, kas mano schemose pažymėta. Tuomet galiu ir užrašyti.

0

AncientMariner
verbunai
AncientMarinerVaizduokime kubą taip (taškai žymi viršūnes, o brūkšniukai - briaunas):

pažymėk kubo viršūnes, kaip įprasta : 000,001,010,100,011,101,110,111, kur dvi viršūnės yra gretimos,
jei jo pavadinimas skiriasi vienu simboliu. Pvz, 101 turi kaimynus 111,001,100. Taip lengviau bus užrašyti, kur
šaudė.


Aišku, žymėjimas yra daugiausia stiliaus ir skonio klausimas, bet šiuo atveju drįsčiau prieštarauti. Vizualus žymėjimas yra tiesiog vaizdesnis... Nebent neįmanoma įžiūrėti, kas mano schemose pažymėta. Tuomet galiu ir užrašyti.


Na tavo sprendimas yra visiškai teisingas, bet nėra labai gražus, nes panašus į spėjimą. Yra labai logiškas paaiškinimas, kodėl būtent taip šaudei. Gal tu jį ir žinai, bet nesimato to iš sprendimo. Daug uždavinių išsprendžiama tuo būdu.

0

Esminė kubo savybė, dėl kurios galima elementariai išspręsti uždavinį, yra jo dvidališkumas. Tiksliau sakant, trimatis kubas yra G_4, kur G_n yra dvidalis (n-1)-reguliarus grafas, kurio abi dalys turi po n viršūnių. Bendru atveju, jei kiškis slėptųsi grafe G_n ir būtų n-1 medžiotojas, užtektų 4 šūvių. Jei grafo dalys yra A = {a_1, ..., a_n} ir B={b_1, ..., b_n} (trūkstamos briaunos yra a_i b_i, i = 1, ..., n), tai galima šaudyti taip:

1 šūvis - a_1, ..., a_{n-1}
2 šūvis - b_1, ..., b_{n-1}
3 šūvis - b_1, ..., b_{n-1}
4 šūvis - a_1, ..., a_{n-1}

ir kiškis nušautas.

Va, pabandžiau nuspėti, koks sprendimas atitiktų tamstos skonį :) Iš karto turiu save sukritikuoti. Nesu patenkintas rezultatu - čia labai pretenzingai aprašoma strategija "šaudome taip, kad kiškiui liktų kuo mažiau laisvų viršūnių" (kas yra greičiausiai sprendimą randanti strategija). O dar ir neįrodžiau, kad sprendimas teisingas - reiktų daugiau rašyti.

Galbūt galėtum parašyti, kokį gražų sprendimą tu turėjai omenyje? :)

Ai, ir būtų įdomu, jei galėtum daugiau panašių uždavinių pateikti (minėjai, kad yra daug tokių). Man jis pasirodė smagus ir pats nebuvau susidūręs su tokiais.

0

AncientMarinerEsminė kubo savybė, dėl kurios galima elementariai išspręsti uždavinį, yra jo dvidališkumas. Tiksliau sakant, trimatis kubas yra G_4, kur G_n yra dvidalis (n-1)-reguliarus grafas, kurio abi dalys turi po n viršūnių. Bendru atveju, jei kiškis slėptųsi grafe G_n ir būtų n-1 medžiotojas, užtektų 4 šūvių. Jei grafo dalys yra A = {a_1, ..., a_n} ir B={b_1, ..., b_n} (trūkstamos briaunos yra a_i b_i, i = 1, ..., n), tai galima šaudyti taip:

1 šūvis - a_1, ..., a_{n-1}
2 šūvis - b_1, ..., b_{n-1}
3 šūvis - b_1, ..., b_{n-1}
4 šūvis - a_1, ..., a_{n-1}

ir kiškis nušautas.

Va, pabandžiau nuspėti, koks sprendimas atitiktų tamstos skonį :) Iš karto turiu save sukritikuoti. Nesu patenkintas rezultatu - čia labai pretenzingai aprašoma strategija "šaudome taip, kad kiškiui liktų kuo mažiau laisvų viršūnių" (kas yra greičiausiai sprendimą randanti strategija). O dar ir neįrodžiau, kad sprendimas teisingas - reiktų daugiau rašyti.

Galbūt galėtum parašyti, kokį gražų sprendimą tu turėjai omenyje? :)

Ai, ir būtų įdomu, jei galėtum daugiau panašių uždavinių pateikti (minėjai, kad yra daug tokių). Man jis pasirodė smagus ir pats nebuvau susidūręs su tokiais.



Na aš į šį uždavinį žiūrėjau iš panašios pozicijos. Jei fiksuotume vieną viršūnę, tai zuikio atstumas nuo tos viršūnės arba padidėja 1 arba sumažėja vienetu.
Imkime vieną viršūnę A={000}, tada nuo jos per 1 nutolusios viršūnės B={001,010,100}, per 2 viršūnės C={011,101,110} ir per 3 viršūnė D={111}. Tada šaudome iš eilės į B C C B. Tarkime zuikio nenušovė.
Pirmi du šūviai garantuoja, kad zuikis iš pradžių (ir todėl po 2 šūvių) negalėjo būti ant B ir D.
paskutiniai du garantuoja, kad po 2 šūvių zuikis negalėjo būti ant A ir C.

Tavo apibendrinimui šis sprendimas taip pat tinka.

prikibau prie tavo sprendimo, nes pasirodė, kad šaudei taip, kad kuo mažiau viršūnių liktų (pasirodo atspėjau). Šis būdas šį kartą dėl uždavinio "ne optimalumo" tiko, bet bendru atveju netiktų.
Kadangi matėsi, kad mastai, tai bandžiau išpešti daugiau nei tik sprendimą. :)

0

Graži mintis suskaidyti grafą lygmenimis pagal atstumą nuo fiksuotos viršūnės. Visgi šitas uždavinys nebuvo pakankamai gilus, kad reiktų eiti prie to. Galbūt žinai kitų uždavinių šita tema, kuriems tikrai reikėtų šitos idėjos?

0

Na tas suskaidymas yra natūralus dalykas kombinatorikoje. Ant n-mačio kubo tuos lygmenis pagal atstumą vadina kubo sluoksniais. Tas atstumas dar yra vadinamas Hammingo atstumu tarp dviejų grafo viršūnių. Jei grafe nėra kelio iš vienos viršūnės į kitą, tai tas atstumas tampa lygus pagal apibrėžimą +begalybei. Daugiau tokių paprastų uždavinių nelabai žinau taip iškart, nes dauguma uždavinių, kuriuos nagrinėju jau nebe olimpiadiniai ir reikalauja žinoti specialius sprendimo metodus.

Šis uždavinys šiemet buvo pateiktas 6-8 klasių respublikinėje olimpiadoje, bet deja nei vienas aštuntokas (iš maždaug 80ties) nesugalvojo teisingo šaudymo strategijos. Buvo vienas, kuris pradėjo šaudyti kaip tu pirmus tris šūvius, bet paskutinį sumovė.

0

Dėl aštuntoko nesistebiu, nes kad ir ką sakytum, šitą uždavinį spręsti natūralus būdas ir yra pašaudyti kelis kartus bei žiūrėti, kas gausis (dėl jo nedidelės apimties).

O uždavinius, kad ir neolimpiadinius, vis vien norėčiau sužinoti. Kad būtų bent "panašios dvasios".

0

Norėdami rašyti žinutes privalote prisijungti!