Máme "šachovnicu" so 78 poliami zobrazenú na obrázku. Je ju možné úplne pokryťa) 39 dvojpolíčkovými obdĺžnikmi ?
b) 26 trojpolíčkovými obdĺžnikmi ?
c) 26 trojpolíčkovými L-kami ?
Poznámka 7.11.: časti a) aj b) už máme vyriešené (pozri komentáre). Pre úlohu c) ešte nemáme v komentároch riešenie, ale aspoň ja som už konečne riešenie našiel :-) keď povoľujeme
9 komentárov:
komentarom ma byt riesenie? tak sa o nejake pokusim. :-) tato uloha ma rozculovala uz dva dni, takze sa asi musim pochvalit s tym, na co som prisla. odpoved a) je nie. to bolo celkom lahke: bielych policiek je na sachovnici 40, kym ciernych len 38 a kedze kazda kocka domina musi pokryvat jedno biele a jedno cierne policko, je zrejme, ze pokrytie nemoze ani teoreticky existovat, lebo dve biele policka nam ostavaju 'visiet vo vzduchu'.
prist na odpoved po b), alebo aspon nieco, co povazujem za odpoved, mi dalo viac prace.:-) ale hovorim, ze v tomto pripade tiez nie je mozne sachovnicu pokryt: 'pozdlzne' tromina mozu byt dvoch typov: bud pokryvaju policka 'biele-cierne-biele'(BCB) alebo 'cierne-biele-cierne'(CBC). ak tych prvych bude v pokryti x a tych druhych y, tak sa z podmienok, ze vsetkych bielych policok je 40 a vsetkych ciernych 38, da zistit, ze ak tromina maju sachovnicu pokryvat, musi ich byt 14 typu BCB a 12 typu CBC. no a teraz klucova vec: ak si to clovek dobre rozmysli (dufam, ze som si to rozmyslela naozaj dobre :-) ), cez vsetky policka trominami vyplenenej sachovnice by sa malo dat po trominach(t.j. iba horizontalnymi, resp. vertikalnymi pohybmi) poprechadzat. prechadzka po tromine vyzera tak, ze z jedneho jeho konca prejdeme na druhy a tam pokracujeme na susedne policko, ktore je krajnym polickom dalsieho tromina. navyse, zda sa mi, ze by mala existovat cesta, na ktorej sa tromina budu striedat: BCB(zaciname v lavom hornom rohu), CBC, BCB,... to vsak pri pocte 14 BCB a len 12 CBC tromin nie je mozne dosiahnut.
viem, ze som tu pouzila vela nematematickych 'zda sa mi', ale vie to niekto zdovodnit sofistikovanejsie, ako len 'it's easy to see' ( a tentokrat doslova)?
o odpoved c) sa uz v tejto nocnej dobe nepokusam, aj ked by som si tipla, ze to bude zas 'nie'.
Ahoj gurama. Tvoje riešenie a) je správne a najjednoduchšie možné.
V riešení časti b) je väčšina krokov správna a jasná; celkovo je to zaujímavý prístup, avšak zdôvodnenie existencie Tvojej prechádzky po trominách (nazval by som ju "Hamiltonovskou"), je veľmi vágne. Nakoniec, existujú "šachovnice" (napríklad 2x4 s chýbajúcimi kockami na dvoch opačných rohoch) a príslušné pokrytia, kde taká prechádzka neexistuje. Prečo by akurát hypotetické pokrytie šachovnice zo zadania nemalo byť tohoto typu?
Prezradím však, že časť b), podobne ako a), má aj jedno veľmi jednoduché a presvedčivé riešenie (keď už ho človek pozná, samozrejme).
Zeby b) bolo zakerne? Vysvetlim.
Ked si vsetky policka oznacime po diagonalach cislami 1, 2, 3, 1, 2, 3, ... tak, ze lavy horny roh bude 1, dve policka dole a doprava 2, dalsie tri 3, dalsie styri 1 atd., tak mame podobnu situaciu, ako pri a). Kazdy polozeny trojpolickovy obdlznik zasahuje prave na jednu 1, jednu 2 a jednu 3. Lenze mam rozny pocet 1, 2 a 3 - postupne 25, 26 a 27. Takze to nejde.
Zakerne to je preto, ze sachovnica nabada na dve farby a brani vidiet, ze sa to da tromi farbami / znakmi. Asi by to bolo lahsie, keby sachovnica nebola sachovnicova. :-)
Výborne, Lev. Tvoje riešenie b) je zrejme najjednoduchšie možné. Čo sa týka tej zákernosti, nebol to môj zámer, ale uznávam, že klasické ofarbenie šachovnice môže byť trochu zavádzajúce :)
Zda sa, ze farbenie / cislovanie je popularna metoda. Nad c) sa zamyslim...
c) ano
mám ale jen řešení obrázkem(o:
Tak tady je jedno pokrytí
http://img371.imageshack.us/img371/6300/rohygs5.jpg
a pak mám ještě poznámku, eLka jsou vlastně jen rohy, takže když se povolí rotace, tak už není potřeba zrkadlo. Nebo ne?
Tychi: Veľmi dobre! Myslím, že preto sa tu dlho neobjavilo riešenie časti c), lebo väčšina ľudí očakáva, že ani pre tie L-ká to nejde. (Ja som to tiež najprv čakal a aj som našiel "dôkaz", že sa to nedá. Potom som si v ňom našiel chybu.) Fajn, takže máme riešenie tohoto príkladu uzavreté.
S tými preklopeniami máš samozrejme prevdu; tú poslednú polvetu v hlavnom článku preškrtnem, lebo je mätúca.
Musím se usmát.(o: Já nic neočekávala, jen jsem si stáhla obrázek do wordu, nasekala moc kopií šipek a naskládala je tam. Na důkazy nějak nejsem. Na hraní si ano(o:
Zverejnenie komentára