[2648] Sirpi | 2008-05-16 02:27:20 |
És hogy ez miért optimális:
A közlekedőutat tekintsük egy gráfnak (a csúcsok az üres mezők, az élek az élszomszédos mezőket kötik össze). Erről a gráfról kell belátni, hogy ha nem is mindig összefüggő, de néhány autó átpakolásával mindig azzá tehető. Hiszen ha van út, ami nincs összeköttetésben a bal felső sarokkal (az ábrán a sárga tartomány), akkor az annyit jelent, hogy egy vagy több autó blokkolja az utat a bal felső sarokig. Vegyünk egy ilyen autót (piros), és toljunk rajta egyet, rá a belső útra (kék helyzet). Az autó az új helyzetében nem blokkolhat másik autót, hiszen az autók hiába hajtanak a belső útra, onnan nem tudnak kijutni, csak ha az eredeti helyükre visszamennek, tehát a kék mező érintése nélkül is ki tudnak jutni, ha eddig ki tudtak. A kék autó pedig szintén kijut (egyet előremegy, és onnan már a feltételezésünk szerint kijut). Ezzel a tolással a belső út hossza 1-gyel csökkent, így ilyen lépések véges sorozatával felszámolható az összes belső út (jelen esetben a kék autót még 1-gyel lejjebb tolva a belső út összekapcsolódik a "fő" úthálózattal, vagyis több lépésre nincs is szükség).
Így a továbbiakban feltehető, hogy a közlekedőutak hálózata összefüggő, álljon k mezőből. Ekkor legalább k-1 belső kapcsolódása van (az összefüggő gráfnak legalább k-1 éle van). Minden belső kapcsolódás 2-vel csökkenti a közlekedőhálózat kerületét, tehát az összkerület legfeljebb 4k-2(k-1)=2k+2. Minden él a kerületen egy autónak ad lehetőséget, hogy felhajtson az úthálózatra, és így eljusson a bal felső sarokba (egy autó több élen át is megteheti ezt). Sőt, a bal felső mező két sarokéle nem segít egy autónak sem, vagyis legfeljebb 2k autó lehetséges k mezőből álló úthálózat esetén. Tehát a mezők számának legfeljebb 2/3-án lehetnek autók, és ez az arány aszimptotikusan (az előző hsz. ábrája alapján) el is érhető.
Megj.: Sőt, az út "meglátogatja" a másik 3 sarkot is, hiszen egy sarok és két szomszédja közül nem állhat mind a 3-on autó, vagyis k mezőből álló úthálózat esetén legfeljebb 2k-3 autó lehetséges (hiszen minden határélnél vesztünk egy autót) - feltéve, hogy a parkoló mindkét oldalának hossza legalább 4, mert ilyenkor a sarkokkal szomszédos mezők nem eshetnek egybe.
|
|
Előzmény: [2649] Sirpi, 2008-05-16 01:37:44 |
|
|
|
[2646] Róbert Gida | 2008-05-15 23:35:28 |
Szerintem nem adható rá explicit képlet tetszőleges n-re. Programozási versenyen volt egy hasonló példa axb-es téglalapra, de úgy, hogy alul és felül is ki lehet jutni, gyakorlatilag végignézték az összes esetet a megoldásoknál.
Ha az első ábrában a hatodik sor első pozicióján nem autó van, és ilyen 7x7-es blokkokat rakunk egymásra, akkor tetszőleges autó fel tud jutni a legfelső sorba. Ha a nagy négyzet felső sorából töröljük az autókat, így már mindenki kijut, ez (7k)x(7k)-asra müködik, ha n nem ilyen alakú, akkor legyen k=floor(n/7). Az autók száma aszimptotikusan .
Felső becslés pedig: egy autónak van van legalább egy nem autó szomszédja, hogy esélye legyen kijutni (kivéve, ha n=1 és 1 autó van az ábrán), továbbá egy nem autó hely maximum 3 autónak lehet szomszédja, ami kijutásra használja, ellenben minden szomszéd autó, de akkor nem tudna kijutni, ha odamenne. Így #autó<=3*#nemautó, azaz
#auto<=3*(n2-#auto), innen teljesül, ha n>1.
|
Előzmény: [2643] Lóczi Lajos, 2008-05-15 21:51:46 |
|
[2645] Sirpi | 2008-05-15 22:39:14 |
Szerintem ezt a négyzetfelosztást mindig meg lehet csinálni akkor is, ha a két kis négyzet (egész) oldalhosszát előírjuk (a és b). Hiszen ekkor egy ab(a2+b2) oldalhosszú négyzet biztos kitölthető, méghozzá úgy, hogy a felső részében vannak az a oldalhosszú kis négyzetek (b(a2+b2)×a db.), alatta pedig a b oldalúak (a(a2+b2)×b db.). Sőt, gyakran kevesebb is elég lehet, pl. ha a és b nem relatív prím. Viszont azt nem tudom, hogy ennél kevésbé rendezett megoldások is vannak-e kisebb elemszámmal.
|
Előzmény: [2643] Lóczi Lajos, 2008-05-15 21:51:46 |
|
[2644] jonas | 2008-05-15 22:23:31 |
A négyzetes nem nehéz.
Egyszerűen választunk egy (s,a,x) számhármast, amelyre 1<s,x és 0<x<a2, és a2-x=s2x. Ezután egy nagy négyzetet felosztunk a2 közepes négyzetre, majd x darab közepes négyzetet egyenként s2 darab kis négyzetre.
Több megfelelő számhármas is van, az ábra a (2,5,5)-nek megfelelő megoldást mutatja, de jó például a (2,10,20),(3,10,10),(7,10,2),(2,15,45),(4,17,17),(2,20,80),(3,20,40),... is.
Ha 4s2x, akkor megtehetjük azt is, hogy egy (vagu több) közepes négyzetet kis négyzetek közé fáziseltolással csempészünk be, ahogy a második ábra mutatja.
|
|
Előzmény: [2643] Lóczi Lajos, 2008-05-15 21:51:46 |
|
[2643] Lóczi Lajos | 2008-05-15 21:51:46 |
Hát akkor tűzzük ki :) Az is érdekes kérdés, hogy határértékben mi a fekete/fehér kockák aránya, az optimális esetben, ha a négyzetrács mérete végtelenhez tart. Amúgy ezt a feladatot idén adták fel orosz 6.-osoknak, egy olimpiai előkészítőn. A közölt megoldás is 28-at ad meg (egyébként Python ábráján a jobb szélsőt), persze nem bizonyítja az optimalitást. (A feladat pontozása érdekes: aki 25 autót rak be, 1 pontot kap, ezen felül viszont minden újabb autó plusz 2 pontot ér :-)
A másik, hasonlóan érdekes feladat: osszunk fel egy négyzetet kétféle méretű négyzetre, úgy, hogy a két fajtából egyforma számú darab szerepel. Kíváncsi vagyok, hogy van-e lényegében másfajta elrendezés, mint amit közöltek.
(A többi 4 feladat triviális volt ezekhez képest.)
|
Előzmény: [2642] Python, 2008-05-15 19:55:25 |
|
[2642] Python | 2008-05-15 19:55:25 |
A 28 nálam is megvan és szerintem nincs ennél jobb, mivel elég sokat szórakoztam, és 28-at többfélét találtam, de annál jobbat nem (3 példányt felteszek ábrában). Érdekes lenne a feladatot általánosabban is kitűzn, tehát n×n-es parkolóra.
|
|
Előzmény: [2640] Káli gúla, 2008-05-15 14:50:44 |
|
[2641] Róbert Gida | 2008-05-15 16:48:03 |
Jók a számok. Lehet találni egy formulát, ami ilyen számokat állít elő, feltéve, hogy néhány szám prím a formulában. Ez hasonló a Carmichael számokat gyártó képlethez, ami persze nem véletlen, hiszen ahogy írtad ezek mind azok. Ha egy ikerprím sejtéshez hasonló sejtés igaz, akkor máris végtelen sok ilyen szám van.
|
Előzmény: [2638] Enkidu, 2008-05-15 12:41:43 |
|
|