| [3385] Fálesz Mihály | 2010-12-07 12:48:40 |
 516. feladat (Valamikor réges-régen, egy nem annyira távoli galaxisban, olimpiai előkészítőn volt.)
Bergengóciában olyan az úthálózat, hogy a városok közötti utak nem ágaznak el, minden út két várost köt össze. Az úthálózat összefüggő, vagyis az utakon bármelyik városból bármelyik városba el lehetett jutni --- legalábbis a múlt hétig. A világgazdasági válság miatt ugyanis a bergengóc kormány változatos megszorításokra kényszerült. Az Utazásról Leszoktató Minisztérium például a következőket rendelte el:
56789/2010. Min. rendelet a helyváltoztatás szabadságának megőrzéséről és védelméről
1.§ (a) Az ország mindegyik útját egyirányúsítani kell.
(b) Az utak irányítását olyan módon kell megválasztani, hogy ne lehessen körbe utazni több város között.
Az intézkedés bevezetése ellen hevesen tiltakoztak a kukutyiniak, mert hozzájuk minden út befelé vezetett, és emiatt sehova nem tudtak utazni. A demonstráció vezérszónoka Mariska néni volt, aki az unokahúga nagybátya sógorának a régi kollégiumi szobatárását szerette volna meglátogatni Alsómocsoládon. A tiltakozások eredményeként a minisztérium a következővel egészítette ki a rendeletet:
2.§ (a) Minden héten, ha van olyan város, ahonnan csak kifelé vezet út, akkor ezek közül ki kell választani az egyiket, és az innen kifelé vezető utak irányítását meg kell fordítani.
(b) Az (a) pont rendelkezéseiben előírtaktól eltekintve, a többi út irányítása nem változik.
Eljuthat-e Mariska néni Kukutyinból Alsómocsoládra?
|
|
| [3386] Sirpi | 2010-12-07 13:20:04 |
 Nagyon jó a megfogalmazás :-)
Csak lehet, hogy valamit félreértek, mert túl könnyűnek tűnik ellenpéldát gyártani:
Legyen 3 város, A, B és C, és a kezdeti kétirányú (összefüggő) úthálózat álljon az AB és BC utakból (Mariska néni A-ban lakik, C-be akar eljutni). A kezdeti irányítás legyen C->B->A, ez Mariska néninek nyilván nem fog tetszeni. Erre CB-t megfordítják: C<-B->A, de ekkor B lesz forrás, így CB-t megint megfordítják: C->B->A s.í.t., Mariska néni pedig hoppon marad (persze ha másodszor nem CB-t, hanem BA-t fordítjuk meg, akkor meg is van a kívánt út, szóval meg lehet oldani, hogy eljusson, de azt is, hogy ne).
Ja, és ez nem csak 3 városra ellenpélda, mert nyilván ha B-be becsatlakozik még egy csomó másik út, mondjuk mind B-ből kifelé, akkor is ugyanezt el lehet mondani).
|
| Előzmény: [3385] Fálesz Mihály, 2010-12-07 12:48:40 |
|
|
|
| [3389] Tóbi | 2010-12-07 22:25:50 |
 Először is egy átfordítás nem hozhat létre kört, és amíg nincs kör, mindig lesz átfordítható csúcs. Tehát a folyamat végtelen sokáig fog tartani. Azt kellene igazolni, hogy minden csúcs végtelen sokszor átfordul. Ekkor Mariska néni eljuthat K-ból A-ba: kinéz egy tetszőleges irányítatlan K-A utat, és átmegy az egyes éleken, mikor azok a megfelelő irányba fordulnak. Tekintsünk egy minimális csúcsszámú gráfot, ahol az állítás nem igaz. Tegyük fel, hogy P olyan csúcs, ami csak véges sokszor fordul át. Ekkor egy idő után P már nem forog, és a P-ből kimenő élek száma monoton nő. Egy idő után ez is megáll. Hasonló igaz a P-ből elérhető pontokra, majd az azokból elérhetőekre is stb. Az elérhető csúcsok halmaza legyen S. Ha V(G)=S akkor egy idő után nem lenne több átfordulás, ez kizárt. Tehát néhány pont kimarad, egy idő után ezek közt zajlana minden átfordulás, mégpedig az S-el nem szomszédosak közt. Tekintsük most a V(G)\S csúcsai által adott részgráfot, és legyen ebben P' egy S-sel szomszédos pont (ilyen létezik az összefüggőség miatt). Ez egy kisebb ellenpélda lenne az állításra.
|
| Előzmény: [3385] Fálesz Mihály, 2010-12-07 12:48:40 |
|
| [3390] apci | 2010-12-09 21:22:52 |
 Sziasztok! Ezzel a feladattal nem boldogulok:
|
 |
|
|
|
| [3393] jonas | 2010-12-10 19:27:40 |
 Az 511-re lényegében jó a válaszod, de csak akkor ez a képlet, ha m+n páros, különben hm,n=0.
Az 512-re jó a válaszod, a tanulság pedig az, hogy ha csak az 511-re adott képletet látnád, akkor sokkal nehezebb lenne megkapni a determinánst, mint így.
Az 513-ra vagy nem egészen jó a megoldásod, vagy a feladatot adtam fel rosszul, mert nem csupa nullák vannak a szorzatban.
|
| Előzmény: [3392] stray dog, 2010-12-10 13:13:34 |
|
|
