Matematické Fórum

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

 

#1 20. 08. 2018 11:52

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Geometrie se zápalkami. Z mříže odstraň zápalky, aby nezůstal čtverec

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.

What does a drowning number theorist say?
'log log log log ...'

Offline

 

#2 20. 08. 2018 21:44 — Editoval vanok (20. 08. 2018 22:45)

vanok
Příspěvky: 14452
Reputace:   741 
 

Re: Geometrie se zápalkami. Z mříže odstraň zápalky, aby nezůstal čtverec

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,

Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT

Offline

 

#3 21. 08. 2018 00:43 — Editoval laszky (21. 08. 2018 04:58)

laszky
Příspěvky: 2361
Škola: MFF UK, FJFI CVUT
Reputace:   195 
 

Re: Geometrie se zápalkami. Z mříže odstraň zápalky, aby nezůstal čtverec

↑ 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 $1+\mathrm{floor}(n^2/2)$

Offline

 

#4 21. 08. 2018 14:07

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Geometrie se zápalkami. Z mříže odstraň zápalky, aby nezůstal čtverec

↑ 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 $1+\mathrm{floor}(n^2/2)$, 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ů.

What does a drowning number theorist say?
'log log log log ...'

Offline

 

#5 22. 08. 2018 01:08

OndraD
Příspěvky: 59
Reputace:   -3 
 

Re: Geometrie se zápalkami. Z mříže odstraň zápalky, aby nezůstal čtverec

Ahoj, ještě tam zůstal ten velký čtverec okolo. Jestli jsem někde neudělal chybu.

(0,1)-(1,1) zachovat a místo ní vzít (0,0)-(0,1)


//forum.matweb.cz/upload3/img/2018-08/92832_ctv.jpg

Offline

 

#6 22. 08. 2018 01:32

OndraD
Příspěvky: 59
Reputace:   -3 
 

Re: Geometrie se zápalkami. Z mříže odstraň zápalky, aby nezůstal čtverec

Začít od kraje směrem ke středu. U 8x8 mi vyšel tenhle vzor 8+7+6+5+4+3+2+1, jestli to platí obecně jsem nezjišťoval.

//forum.matweb.cz/upload3/img/2018-08/94179_sirky.jpg

Offline

 

#7 22. 08. 2018 10:10 — Editoval Andrejka3 (22. 08. 2018 11:26)

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Geometrie se zápalkami. Z mříže odstraň zápalky, aby nezůstal čtverec

↑ 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. $n\cdot (n+1)$, z nich odebíráš půlku, takže celkem odebereš právě
$\frac{n\cdot(n+1)}{2}$ dřívek (což je pro n=4 moc).

Pěkný algoritmus. Právě jsem si ověřila, že to funguje.

What does a drowning number theorist say?
'log log log log ...'

Offline

 

#8 22. 08. 2018 10:51

vanok
Příspěvky: 14452
Reputace:   741 
 

Re: Geometrie se zápalkami. Z mříže odstraň zápalky, aby nezůstal čtverec

Cau ↑ laszky:,
Dakujem za opravu preklepov.

Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT

Offline

 

#9 22. 08. 2018 11:05

OndraD
Příspěvky: 59
Reputace:   -3 
 

Re: Geometrie se zápalkami. Z mříže odstraň zápalky, aby nezůstal čtverec

↑ Andrejka3:

Nepleteš, tenhle algoritmus odstraní čtverce, ale ne minimálním počtem.

Offline

 

#10 22. 08. 2018 11:27 — Editoval Andrejka3 (22. 08. 2018 11:47)

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Geometrie se zápalkami. Z mříže odstraň zápalky, aby nezůstal čtverec

↑ OndraD:
Máš pravdu.
edit: neco se tu zkopirovalo navic...

What does a drowning number theorist say?
'log log log log ...'

Offline

 

#11 22. 08. 2018 11:47

OndraD
Příspěvky: 59
Reputace:   -3 
 

Re: Geometrie se zápalkami. Z mříže odstraň zápalky, aby nezůstal čtverec

↑ 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

 

#12 24. 08. 2018 21:59 — Editoval Andrejka3 (24. 08. 2018 21:59)

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Geometrie se zápalkami. Z mříže odstraň zápalky, aby nezůstal čtverec

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
$\left\lfloor\frac{n^2}{2}\right\rfloor +1 \leq a_n\leq \frac{n^2+n}{2}$
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.

What does a drowning number theorist say?
'log log log log ...'

Offline

 

 

Stránky: 1

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson