Fórum: Grafi-logikai feladványok

Kedves Zormac!

Köszi a tájékoztatót. Alább mellékelem a javított és nagy valószínűséggel végleges változatot. Egy kicsit átrendeztem, hogy kisebb helyre elférjen.

Érdekes feladat lehet ezek minél kisebb helyre történő összepakolása is úgy, hogy semelyik két elem sem érintkezhet, ez 18/28-as téglalapba van berakva. Biztos, hogy alaposan javítható. Aki igényli, annak .DXF állományban lementve el tudom küldeni.

Az elemek ismeretében talán kidolgozható egy eljárás, mellyel az eljárás szerinti összes elem képezhető. Így ezt manuálisan vagy számítógéppel lefuttatva kisebb elemszámosság mellett gyakorlatilag megtalálható az összes lehetőség. Másrészről, ha valaki valahol valamikor találna egy újat, az úgyis büszén jelezné. Ha sokideje nincs jelzés, így nagy valószínűséggel nem található már újabb. Persze ezek még nem bizonyítások.

HK

Ez már a 101. hozzászólás, de talán még nem késő megemlékezni a topic centenáriumáról ;-)

A 27. feladat különösen tetszett - ha én gyártottam volna, tökéletes monogram-intarzia lett volna :-)

A 29. feladat megoldásai: 1-3-3-1 illetve 3-1-3-1-3.

Kedves Lórántfik!

Villámgyorsak voltatok, ilyen tempóban nem tudok újabb feladatokat gyártani :o)

HK

27. 28. feladat megoldása:

A doksi, amit a hexaminókról találtam egy kis kutakodás után, 35 hexaminót adott meg és azt állította, hogy annyi van. Hogy nincs több, azt nem láttam bizonyítva sehol.

Így elsőre egy darabot látok, ami a Te gyűjteményedből (amelyhez és a türelmedhez így is csak gratulálni tudok) hiányzik - 2x2-eshez hozzáragasztasz egy-egy négyzetet a jobb felső mező fölé is és mellé is. Vagyis... asszem megvan a másik is: megfogod az ábrádon a jobb felső hexaminót és annak felső négyzetét eggyel jobbratolod.

A Google-t használtam keresésre a hexamino avagy hexaminoes kulcsszavakkal és csak az első oldalon levő találatokba néztem bele, megvolt minden infó.

Kedves Károly!

Gratulálok a hexaminó gyüjteményhez! Ez tényleg nagy meló volt! Én csak a zöldeket kerestem meg, úgy, hogy egy helyben álló kockát vagdostam szét és terítettem ki az alaplap síkjába, kiszűrve az egybevágó mintákat.

Megvan 27. és 28. feladat megoldása, de még nem teszem fel, hátha van más fórumos is aki elszórakozna vele. (1-5 nehézségi skálán nálam 27: 1, 28: 3-as minősítést kapott!)

29. feladat - "Komplementer dominó"

Milyen féldominó elemekből állhat az alábbi két sziluet?

HK

28. feladat: "Ossza szét"

Osszátok szét az alábbi ábrát 4 db egybevágó idomra.

HK

27. feladat: "Ossza szét"

Osszátok szét az alábbi ábrát 3 db egybevágó idomra.

HK

Kedves Csimby,

az NP helyesen a "nemdeterminisztikus polinomidejű" feladatok osztályát jelenti. Egy probléma akkor tartozik ide, ha megoldása polinomidőben ellenőrizhető egy (nemdeterminisztikus) Turing-géppel (idealizált párhuzamos számítógéppel).

Egy NP-beli probléma megoldása tehát nagyon nehéz lehet, de ha valahonnan már tudjuk a megoldást (pl. egy mágustól), akkor a megoldás HELYESSÉGÉNEK ellenőrzése már polinomidőben végrehajtható.

A P-beli problémák (tehát azok, amelyek megoldási ideje a bemenet hosszának polinomjával becsülhető felülről) pl. mind NP-beliek.

Üdv, Lajos

Kedves Csimby!

A NemPolinominális tájékoztatódat köszi, így összeáll a kép bizonyos feladatok "le nem reagálására" :o)

Elkészítettem a hexaminó gyűjteményt, ha valamit kihagytam, (vagy hibáztam) szóljatok, felveszem a listára. Ennyit talán még át(tér)láthatunk, a kódolása magáért beszél. Olyan ez, mint egy mexikói szőttes, s talán nem véletlen, de ez más érdekes vizekre evez.

HK

A 26.A feladat egy úgynevezett NemPolinominális idejű feladat (NP), tehát ha nem 6-ra hanem mondjuk 100-ra kérdeznéd akkor valószínűleg senki sem tudná megmondani a választ még számítógép segítségével sem. Ezért gondolom, hogy nincsen egyszerű összeszámolási módszer (pl. képlet), mert ha 6-ra lenne, akkor többre is lehetne csinálni (gondolom). Mi csináltunk suliban fa számlálást (hány n csúcsú fa van?), de ha az izomorfakat kizárjuk, úgy tudom ez is megoldatlan (ezt csak azért írom mert hasonló probléma). Azért sok sikert.

Kedves Zormac!

További rendezetlen gondolatok a 26. feladathoz:

- Én a - nem a legelegánsabb, de talán célravezető "próbáljuk meg lerajzolni az összes változatot" nevezetű - nehéztüzérséget bevetve 33 alakzatot találtam, melyből 11 alakzatból lehet kockát hajtogatni. Rövidesen beteszem a kritika részére :o) Remélem nem tévedtem nagyot.

- Gyanítom, hogy a gráfok vizsgálatával fel lehet állítani egy képletet, mi kiadja a pontos végeredményt, de ebben a műfajban nem vagyok otthon. (Hasonló módon lehetne megoldani szerintem paratoto önálló témában feltett kérdését ill. az "Érdekes matekfeladatok" témában feltett egyik feladatomat [180]/40. is.)

- A kerületeket vizsgálva 1 db 10 egység, 6 db 12 egység és 26 db 14 egység kerületű idomra leltem, mely utóbbiban vannak a kockára hajtogathatók, így ez a feltétel a P-pentaminó és 2×2-tetraminó kizárásokat helyettesíti.

- A különböző pentaminók be nem helyezhetőségét én is vizsgáltam, de úgy tűnik csak szükséges, de nem elégséges feltételt adnak. Most azt vizsgálom, hogy az összeilleszkedő élek milyen viszonyban vannak egymással.

- Miután lerágtuk e feladatról a csontot, érdekelne a hálón e témában találtad kapcsolatok is.

HK

Gondolatok a 26. feladathoz (újfent elnézést, megint gondolkodás közben írok):

az egyértelműség kedvéért: tetra-, pento- és hexaminóknak fogom hívni a rendre 4, 5 és 6 négyzetből összerakott alakzatokat

C részhez: biztos, hogy a hexaminók nem tartalmazhatnak bizonyos tetra- és pentominókat saját részükként.

Például semelyiknek nem lehet 2x2-es rész-tetraminója, mert abból garantáltan nem lesz kocka. A pentominók közül pedig az U-, az I-, a P- és az (egyenlő szárú) V-betűkre hasonlítók használata - a hajtogatás során ezek valamely két mezeje összeérne, tehát megintcsak nem ad kockát (a P betűről mondott feltétel persze feleslegessé teszi a 2x2-es rész külön említését).

De ez még nem elégséges feltétel, mert az a hexamino, amelyben egy 4 hosszú lánc két végéhez azonos oldalon csatlakozik két mező, kilóg... meg talán még 1 ellenpélda van.

A részhez: A számolást könnyítendő, egy lehetséges karakterizáció az összefüggőségi szám, vagy másképp szólva, a kerület. Könnyű meggondolni, hogy a 2x3-as hexamino kerülete 10 (és a gráfjában két független kör van), néhány továbbié, amelynek van 2x2-es része, 12 (ezekben 1 kör van), a 2x2-es részt nem tartalmazóké pedig 14 (ezek gráfjai fák). A 12-kerületűeket még elég könnyű leszámlálni aszerint, hogy a 2x2-es részhez hogyan "hegesztesz" hozzá még két négyzetet - szerintem ilyenből 7 darab van. A 14-kerületűeket leszámlálni kissé nehezebb. Talán ott a dimenziók szerint érdemes karakterizálni - 1 darab 6 magas, 4 darab 5 magas... aztán itt megint jönnek a nehézségek.

Nem tudom, van-e elegáns, trükkös leszámlálás egyáltalán...

(most pedig interneten rákerestem és szinte minden kérdésre megtaláltam a választ, de indokolni, leszámlálással alátámasztani ettől még sajnos nem tudom)

Szia Zormac,

Nem jársz messze. :-) A két feladat tényleg azon múlt, hogy az egyik oldalhoz -ször akkora magasság tartozik.

A teljesen általános feltétel bonyolultabb, de azt most ne tárgyaljuk meg, jó lesz a pontversenybe.

Bizonyosan messze járok még a megoldástól :-) de szerintem a 23. feladatban erősen kihasználtuk azt, hogy a 3 hosszúságú oldalához tartozó magasságvonala -szorosa az ugyanezen oldalhoz tartozó középvonalnak, vagyis hosszúságú. Ezt nem számoltam ki, csak afféle megérzés :-) de abból az ábrából, amelyben László háromszögrácsba helyezte ezt a háromszöget, napnál világosabb.

A másik háromszög esetében pedig az 1 hosszú oldalhoz tartozik hosszúságú magasságvonal (bizonyítást lásd szintén László ábrájában), ami ugyanezen aránynak felel meg.

(bocs, real-time gondolkozom és írok, ezért ilyen összeszedetlen :-) - remélem, legalább súlyos elírást nem hagyok benne)

Tehát összefoglalva: gyanítom, hogy ha a háromszögnek van olyan a oldala, hogy a hozzá tartozó magasságvonalra , akkor jó eséllyel lehet belőle szabályos tetraédert hajtogatni a már látott (s László és Károly által csodásan megrajzolt) módon.

Illetve... és ez a 25. feladat esetében bekavarhat... ha az (említett tulajdonságú) a oldalon nyugvó valamelyik szög nagyobb, mint 120 fok, akkor a hajtogatás legalábbis megváltozik, de lehet, hogy ellehetetlenül... ezt még nem tudom.

Kedves Károly és László,

A feltétel egy könnyen ellenőrizhető geometriai tulajdonsága a háromszögnek.

26.feladat:

A - Hányféleképpen lehet 6 db egységnégyzetet egymás mellé illeszteni úgy, hogy az illeszkedés során minden négyzet egyik éle valamely más négyzet egyik és csakis egyik élével azonos legyen; továbbá a keletkező idomok sem tükrözéssel, sem forgatással egymásba nem mozgathatók?

B - Az "A" pontbeli idomok közül melyekből lehet kockát hajtogatni!

C - Keressünk olyan feltételcsoportokat (kritériumokat), melyek segítségével egyértelműen el lehet dönteni, melyekből lehet kockát hajtogatni!

Hajba Károly

Kedves Géza!

>Általában milyen háromszögekkel működik ez a feladat...?

Ha jól sejtem azokra az idomokra lehet ilyen feladatot alkotni, melyre találunk olyan szabásmintát, melyet a síkba kiterítve a következő feltételeknek megfelel:

- két szabásminta egymás mellé rakva úgy érintkezhet, hogy az érintkező pontoknak az eredeti idom azonos pontjának kell megfelelnie;

- az előbbi feltételt betartva a tervezett síkmintát (teljes síkot?) hiánytalanul és átfedésmentesen le lehet túlnyúlóan takarni.

Ezen feltételeknek egyes szabályos háromszög oldalú idomok mindenképpen megfelelnek.

HK

A rácsba rajzolhatóság nem szükséges. Csupán annak lett mellékterméke, hogy megpróbáltam viszonylag szép háromszögoldalakat kitalálni.

Inkább azt érdemes megnézni, hogy a 23. feladatban a háromszögnek melyik tulajdonságát használtuk fel.

Kedves Érdeklődők!

Itt az előző a rácsban. Úgy látom az sem kell, hogy a területe 4 -nyi legyen. Itt a tetraéder oldala a=1,5 egység. A területe 9 szab. -nyi. a²-al leosztva persze kijön a 4, de "a"-oldalú háromszögrácsba nem tudok felvenni az eredetihez hasonló -t.

Kedves Géza és Grafi-logi Böngészők!

A zárójelben feltett kérdés érdekesebb mint a feladat. Nekem is eszembe jutott az előző háromszög felosztásakor. Egyenlőre arra jutottam, hogy elegendő feltétel lehet, hogy a szabályos -rácsba írható legyen a és területe 4 szabályos nagyságú legyen.

A 25. feladat háromszögéhez a tetraéder oldala a=0,5 lenne, így megnöveltem kétszeresére az oldalakat.

Kedves Zormac és Fórumosok!

Teljesen logikus a megoldás, 7 mezőt felül az összefüggőség miatt be kell feketíteni, ebből már látszik a kp.szimmetria és a maradék 3 fekete mező.

Kedves László és Károly,

Ügyesek voltatok. :-)

Ha még nem unjátok, akkor még egy ugyanarra a kaptafára (megígérem, hogy ez lesz az utolsó :-)):

25. feladat. Hajtogassunk szabályos tetraédert ebből a háromszögből. (Általában milyen háromszögekkel működik ez a feladat...?)

24. feladat

Ez már csak afféle ujjgyakorlatnak tekinthető a hajtogatások után (amik nagyon szépek voltak :-)

Színezzünk további 10 mezőt feketére úgy, hogy a fekete és fehér részek egybefüggő és egybevágó részt alkossanak.