Fórum: Érdekes matekfeladatok

Az összefüggőséget tényleg meg lehet oldani, valahogy így. Ez akkor feltehetően a (c) kérdésedre lenne a válasz, kivéve, hogy nem lehet mind a három darabot szétszedni.

A (b) kérdésre feltehetően valami olyasmit lehet csinálni, mint a kínai karikáknak a címer alakú fadarabokból álló változata. A plusz feltételeidet talán úgy lehetne megoldani, hogy mindig újabb, bonyolultabb példányt helyezünk el a régi rejtvény mellé egyre kisebb méretben.

Nem megy ez ma. Szóval, az elrendezés foglalható be egy konstans sugarú körbe. És mondjuk legyen még egy feltétel, hogy az n+1 elemű elrendezés egy alakzat hozzávételével keletkezik az n eleműből (a többi változatlan helyen és méretben marad).

Valóban

Sziasztok!

Éreztem, hogy nem vagyok elég pontos :-(

Sirpi: 1 mozgatás := 1 eltolás (tetszőleges hosszú vektorral) vagy 1 forgatás (tetszőleges középpont körül tetszőleges szöggel) De amúgy ugyanaz a válasz mindhárom kérdésre akkor is ha forgatást nem engedünk meg, csak eltolást.

Jonas: Ügyes példa! És meglehet csinálni összefüggő darabokkal is (a többinél is ugyanaz a válasz, akkor is ha feltesszük, hogy összefüggőek a darabok).

A b. példában valami olyasmit akartam megfogalmazni (nem sikerült), hogy ne azért legyen nagy a lépésszám, mert "nagyok a távolságok" az elrendezésben. Pl. Jonas példájában sok lépés kell, de ehhez kellett egy nagyon hosszú alakzat (a zöld). Valahogy az alakzatok egymáshoz viszonyított arányát akartam megfogni (A "legkisebb alakzat" helyett persze azt kellett volna írnom, hogy "mindegyik alakzat" de így is hülyeség).

b. még egyszer, másképp:

- S(n) exp.

- Mindegyik alakzat egy < 100 oldalú sokszög.

- Az alakzat belefoglalható egy 100 sugarú körbe.

Ez mondjuk így nem működik, mert nem lehet minden darabot szétszedni.

A képen látható szerkezet három darabból áll, és ha elég hosszúra csináljuk, csak nagyon sok lépésben lehet a piros darabot kiszedni. Ha még hozzáveszünk mindhárom darabhoz egy nagy kört úgy, hogy ne akadályozza a darabok mozgatását, de azért nagyon távol se legyen, akkor meg lehet oldani az átmérős feltételt is.

A (b) kérdésre. Ha minden idomban elhelyezhető egy r sugarú kör, de az egész elrendezést magába foglalja egy R sugarú kör, ahol R/r konstans, akkor nyilván konstans sok idom van, mert több kis kör nem fér el a nagy körben. Így aztán az eredeti kérdést pontosítanod kéne.

Azt kell először eldönteni, hogy ilyen feltétellel konstans sok idommal lehet-e tetszőlegesen nagy minimális lépésszámot elérni. Ha nem szükséges, hogy az idomok összefüggőek legyenek, akkor szerintem lehet.

Azt, hogy “a legkisebb síkidomban elhelyezhető egy r sugarú kör”, úgy érted, hogy minden síkidomban elhelyezhető egy ilyen kör? Mert a legkisebb nem egész egyértelmű.

Pontosan mit értesz mozgatáson? Ha két síkidomom van, az egyik egy egységnégyzet, a másik pedig egy egységnégyzetekből kirakott labirintus (a négyzetek alkotják a falakat), és berakom a kisnégyzetet valahova a labirintus belsejébe, akkor ezt a konfigurációt 1, vagy csak nagyon sok mozgatással tudom szétszedni? Tehát a mozgatás történhet tetszőleges pályán vagy csak egyenesen? Lehet-e forgatni szétszedés közben?

Amúgy valami ilyesmivel biztos el lehet érni exponenciális hosszt.

504.feladat Helyezzünk el n db síkidomot a síkon. Legyen S(n), hogy hány db mozgatással tudjuk őket "szétszedni" (akkor mondjuk, hogy szét vannak szedve, ha 1 eltolással bármely 2 egymástól bármilyen messzire elvihető). Van-e olyan elhelyezés alkalmas síkidomokra, hogy:

a. S(n) n polinomja, de annak eldöntése, hogy szétszedhető-e NP-teljes

b. S(n) nagyságrendje eⁿ. Továbbá a legkisebb síkidomban elhelyezhető egy r sugarú kör, az elhelyezést magában foglalja egy R sugarú kör és R/r konstans (nem függ n-től)

c. n=3, K tetszőleges poz. egész és S(n)>K