Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
Ahoj.
Setkala jsem se s úlohou:
Ze čtvercové mříže 4 krát 4 (postavené z 40 dřívek) ostraň devět dřívek tak, aby v obrazci nezůstal čtverec.
Zajímalo by mě, jestli v tom lze najít nějakou pravidelnost. Ráda bych například dostala posloupnost, kde n-tý člen je nejmenší počet dřívek nutných odebrat z mříže n krát n, aby nezůstal žádný čtverec.
Díky za rady.
Offline
Ahoj ↑ Andrejka3:,
Dam ti jedno riesenie co som nasiel.
Nekreslim ale popisem.
Ak vlozis tvoj stvorec do ortonormalneho reperu, tak vyberes drievka (cize usecky) suradnic
(0,1)-(1,1)
(0,3)-(1,3)
(1,1)-( 2,1)
(1,2)-(2,2)
(2,3)-(2,4)
(0,2)-(0,3)
(2,2)-(2,3)
(3,1)-(4,1)
(3,3)-(4,3)
Dufam, ze som to bez chyby odkopiroval z mojho vykresu.
Ine riesenia su isometricke s tymto. ( vyuzi 4 symetrie stvorca ...a rotacie-posunutia)
Nasla si tieto riesenia ako ja,
Offline
↑ vanok:
Pozdravujem. Nezustal Vam tam ctverec (2,0)-(2,1)-(3,1)-(3,0) ?
Zrejme jste prohodil souradnice u 6. a 7. radku, tzn melo to byt
(0,1)-(1,1)
(0,3)-(1,3)
(1,1)-(2,1)
(1,2)-(2,2)
(2,3)-(2,4)
(2,0)-(3,0)
(2,2)-(3,2)
(3,1)-(4,1)
(3,3)-(4,3)
↑ Andrejka3:
Mozna by slo reseni hledat tak, ze (v tomto konkretnim pripade) vytvoris bipartitini graf na 40+30 vrcholech, kde prvnich 40 vrcholu reprezentuje 40 drivek a zbylych 30 vrcholu vsech 16+9+4+1=30 ctvercu. Mezi vrcholy grafu je hrana, pokud drivko tvori stranu (nebo jeji cast) ctverce. A pak pouzit nejaky grafovy algoritmus (zatim me nenapadl jaky), ktery najde 30 hran spojujicich 9 (tj. minimalni pocet) vrcholu (z tech 40) se vsemi 30 vrcholy reprezentujicimi ctverce.
Jako dolni odhad minimalniho poctu drivek, ktere se musi odstranit bych videl cislo
Offline
↑ vanok:
Ahoj.
Ano, toto řešení (opravené od ↑ laszky:) jsem našla (otočené).
Nevím, jak využít zmíněných symetrií. Ani nevím, proč je až na izometrii jediné řešení. Taky bych měla problém dokázat, že je to minimální počet, ovšem tady je to zrovna , tak bych tomu ochotně věřila :)
↑ laszky:
Ahoj.
ten minimální odhad máš od nejmenších čtverců, že? Díky za převedení na problém grafů.
Offline
↑ OndraD:
Možná se ti povedlo najít způsob, jak odstranit čtverce, ale není minimální. Pro čtverec 4 krát odstraníš 10 zápalek. Jestli se pletu, napiš pdrobně návod.
Vybíráš si půlku dřívek, tj. , z nich odebíráš půlku, takže celkem odebereš právě
dřívek (což je pro n=4 moc).
Pěkný algoritmus. Právě jsem si ověřila, že to funguje.
Offline
Cau ↑ laszky:,
Dakujem za opravu preklepov.
Offline
↑ Andrejka3:
Nepleteš, tenhle algoritmus odstraní čtverce, ale ne minimálním počtem.
Offline
↑ Andrejka3:
V pravidelném intervalu to úhlopříčně odstraňuje jednu stranu čtverce. Je to takové obrazové přemýšlení nahlas. Není to řešení, spíš zkoumání.
Offline
Tak jo, asi se to už dál nepohne. Díky za nápady.
Zkusím závěr.
Označíme-li a_n minimální počet dřívek, které je nutné odstranit z čtvercové mříže n krát n, aby v ní nezbyl čtverec, pak
Dolní odhad vyplyne z odstranění jednotkových čtverců a toho největšího. Horní pak z postupu naznačeného v ↑ OndraD:.
Lze to převést na problém z bipartitních grafů, ale neznám algoritmus, který by to řešil.
Kdo by chtěl něco rozepsat, ať se ozve.
Offline
Stránky: 1