Asszem így rendben van (kicsit rajzolgattam közbe).
Szerentem fölöslegesen bonyolítja, kutak számával 1-ig lemenni: n-1 kúttal az indukciós feltétel szerint körbe lehet menni, a konstrukcióból következik hogy n-nel is.
Gondolkodtam valami rekurzív eljáráson a megoldás alapján, még semmi...
"Amit ennél a megoldásnál nem látok, az az, 1, hogyan lehet meghatározni a körutat" Sehogy, mert nem az volt a kérdés.
"2, az világos, hogy az n-kutas problémából előállít egy n-1-kutasat, ami az indukciós feltevés miatt bejárható egy körúttal. Hogyan következik ebből, hogy az n-kutas is bejárható?"
Akkor mégegyszer, részletesebben:
Van az n - kutas problémánk. Tudjuk, hogy a körút hossza benzinben mérve b. Tudjuk, hogy b mennyiségű benzin van az n kútban összesen.
Válasszunk egy bejárási irányt. Mondjuk az óramutató járásával egyirányban.
Ha egyetlen kútban sem lenne annyi benzin, hogy eljussunk belőle a rákövetkező kútba, akkor abból következne, hogy összesen kevesebb benzin van a kutakban, mint b. Tehát létezik olyan K nevű kút, amelyben tankolva eljuthatunk a következő L kútig. Vegyük észre, hogy bárhonnan indulunk is, biztos, hogy a K kút utáni útszakaszon nem fogunk leállni; a K út utáni útszakasz nem problémás. Bárhonnan indulunk is, garantáltan az fog történni, hogy eljutunk K-ba, tankolunk, elautózzuk a K kút útáni szakasz bk benzinét, és eljutunk az L kútig. Változna-e a fogyasztásunk, ha az L kutat odavinnénk a K kút mellé, a köztük lévő útszakaszt pedig egy feltekert versenypályán tenénk meg? És ha meg sem tennénk, csak lecsapolnánk a megfelelő mennyiségű benzint? Nem. Vegyük úgy tehát, hogy az összevont KL-ba érve betankolunk K-ból, lecsapolunk bk benzint és betankolunk a L-ből is. Ha így ebben az n-1 kutas feladatban bárhonnan indulva körbeérünk, akkor az eredeti feladatban is körbeérünk. Mivel ebben az n-1 kutas feladatban is garantáltan elegendő a benzinmennyiség az új teljes úthoz. (b-bk), ezért ezt a redukciót továbbcsinálhatjuk egészen 1-ig.
Ennél jobban nem tudom elmagyarázni. Valójában ez egy nagyon egyszerű bizonyítás, ami ha beugrik, akkor egy pillanat alatt ugrik be, legfeljebb így leírva nem olyan egyszerű.
Szerintem topikfannak igaza van, a Matematika feladat (http://forum.index.hu/Article/showArticle?t=9092903) topikba beírtam egy olyan megoldást, amiből ez látszik (n szám közül a legkisebb megkeresése O(n) idő, konstans hely).
Amit ennél a megoldásnál nem látok, az az,
1, hogyan lehet meghatározni a körutat, valamint
2, az világos, hogy az n-kutas problémából előállít egy n-1-kutasat, ami az indukciós feltevés miatt bejárható egy körúttal. Hogyan következik ebből, hogy az n-kutas is bejárható?
Azért még bővebben körbe kellene járni azt a feltételt, hogy összesen van annyi benzin, amennyi egy köruthoz elég. Pl: van k kút ami 0 liter benzint tartalmaz.
Akkor nem értetted meg a bizonyítást. Ő nem azt mondta, hogy, ha a szomszédos kútig eljutsz, akkor körbe is érsz, hanem csak visszavezeti a feladatot eggyel kevesebb kútra. Végül eljut oda, amikor egy kútig, ami triviális.
Azt nem írta, de fontos, hogy a redukció elején, amikor n kút van még, akkor ki kell választani egy irányt, például az óramutató járása szerintit és az összes redukciónál is ezt kell nézni és a végén kapott megoldás is az óramutató járása szerint lesz.
Amikor összevonsz két kutat, akkor már nem választhatsz ki új kiindulási pontot, onnan kell továbbmenned, ahová elértél.
Nem. Ha jobban megnézed, én nem konstruktív, hanem egzisztenciális bizonyítást adtam. (Tehát egyáltalán nem biztos, hogy majd onnan kell elindulni, amit először találtam.) Én csak beláttam, hogy minden elegendő benzines n-kutas feladat visszavezethető egy n-1 kutas elegendőbenzines feladatra, és az 1 kutas elegendőbenzines feladat megoldható: tehát minden n-re is megoldható. (Ez olyasmi, mint a teljes indukció; egy bizonyítási forma, nem pedig egy konkrét konstruktív algoritmus.)
Az nem elégséges kiindulási feltétel, hogy a szomszéd kútig elérj. Az is kell, hogy minden további elindulásnál legyen elegendő üzemanyagod a következő kútig. Amikor összevonsz két kutat, akkor már nem választhatsz ki új kiindulási pontot, onnan kell továbbmenned, ahová elértél.
Igen, mindig van olyan benzinkút, ahonnan megtehető, (méghozzá mindkét irányban van ilyen benzinkút.)
Bizonyítás:
Mivel a teljes út megtételéhez elegendő az össsz benzin, ezért az nem lehetséges, hogy bárhonnan indulok is el, még a következő állomásig sem érek el.
Vagyis van olyan állomás, ahonnan egy útszakaszt megtehetek.
Namost ezt a kezdeti benzinkutat és a rákövetkezőt összevonom, és azt mondom, hogy annyi benzin van benne, mint az eredeti kettőben összesen, mínusz a megszüntetett útszakaszra jutó benzin.
Látható, hogy az új feladat, ugyanolyan mint az előző (az összbenzinmennyiség elegendő), eggyel kevesebb kutat tartalmaz, és akkor és csak akkor oldható meg, amikor az eredeti feladat(, hiszen a megszüntetett úton úgysem csinálnánk mást, mint hogy elfogyasztanánk a levont benzinmennyiséget, akárhonnan indulunk is.)
...
A végén eljutunk a 2 kútig, ahol már triviálisan látszik, hogy megoldható a körbemenetel.
Igaz,de nincs kedvem bebizonyítani. Egyébként O(n) időben és O(1) memóriával meg is található a benzinkút, ahonnan érdemes elindulni. Itt egy programozási feladat, ami lényegében ugyanez: http://acm.uva.es/p/v110/11093.html
Feltéve, hogy n>k azaz p=int(n/k) nagyobb nullánál. akkor a lehetséges k-val osztható elemszámú részhalmazok száma (s): s = (n alatt k) + (n alatt 2k) + ... + (n alatt p)
ott le van rajzolva a "vonal" amrol irsz, de a szamokat osszekoto nyilak egy resze fekete, egy resze meg piros, es ha kovetet a vonalat, akkor ilyen szinu nyilakat latsz: fekete, fekete, piros, fekete, fekete, piros, fekete, fekete, fekete, piros,...
es en a ket piros nyil kozotti fekete nyilak altal meghatarozott "vonal"-akrol beszelek.
Ha a linket hasznalod, vigyazz, hogy ott a halmazban benne van a nulla, nalad meg nincs!)
Az elso "vonalon" 1/1 van.
(a "vonalon" egy szam van, es a szamlalo es nevezo osszege 2)
A masodikon 1/2 es 2/1,
(a "vonalon" ket szam van, es a szamlalo es nevezo osszege 3)
A harmadikon 1/3, 2/2 es 3/1...
(most kicsit megvaltoztattam a Te sorrendedet, Te felvaltva kezdessz
1/m-el illetve m/1-el, de a leiras szempontjabol egyszerubb, ha fixaljuk hogy
melyikkel kezdjuk)
(a "vonalon" harom szam van, es a szamlalo es nevezo osszege 4)
A negyediken: 1/4, 2/3, 3/2, 4/1...
(..???...)
A k-adik vonal ugy fog kinezni, hogy:
1/k, 2/(k-1),..,k/1, vagy ugyanez forditva.
Oke. Erdemes ugy folytatni, hogyha az algoritmus megkapja az n szamot,
akkor eloszor azt kene eldonteni, hogy a hozza tartozo racionalis szam hanyadik vonalon van.
itt egy kis aprosag, hogy az ilyen modon elkeszitett listan minden pozitiv racionalis szam vegtelen sokszor szerepel majd, pl az 1 mint:
1/1, 2/2, 3/3,... emiatt az a szohasznalat hogy "egy racionalis szam melyik vonalon" van, igazabol pontatlan, remelem ez a megjegyzes nem art tobbet, mint hasznal :)
Tegyuk fel, hogy a k-adik vonalon van, kerdes: ez honnan latszik?
Onnan, hogy az elso, masodik, ...(k-1) -edik vonalon levo szamok osszesen
kevesebben vannak mint n,
de ha ehez meg hozzavesszuk a k-ik vonalat, akkor a rajtuk levo szamok mar osszesen legalabb annyian vannak, mint n.
Pl, talaljuk ki, hogy a 23 melyik vonalon lesz?
Lehet a 6-ik vonalon?
Az elso ot vonalon osszesen 15 szam van (1+2+3+4+5),
ez kisebb mint 23, eddig jo.
De az elso hat vonalon osszesen meg mindig csak 21 szam lesz
ami kisebb 23-nal, tehat ez a szam nincs a hatodik vonalon.
A szamolast elvegezve lathatod, hogy a 7-ik vonalon mar tenyleg rajta lesz.
Altalanosabban:
Az elso (k-1) vonalon osszesen hany szam van?
1+2+3+...+(k-1)=(k-1)*k/2)
Az elso k-vonalon pedig k*(k+1)/2 szam lesz.
Szoval, az n sorszamu racionalis szam pontosan akkor van a k-ik vonalon, ha:
(k-1)*k/2 < n =< k*(k+1)/2.
(itt a * szorzast mig a "=<" kisebb vagy egyenlot jelent)
Jo, mostantol tegyuk fel, hogy tudjuk hogy az n a k-ik vonalon van.
Ekkor az n-nek megfelelo racionalis szam
az 1/k, 2/(k-1), 3/(k-2),...,k/1, valameyike lesz, de melyik?
Ez a 23-as konkret peldajan egyszerubb lesz:
Mar tudjuk hogy a szam a hetedik vonalon van, tehat vagy 1/7, vagy 2/6, vagy ... 7/1.
Vedd eszre, hogy az elso hat vonal mar "lefoglalt" 21 darab szamot, tehat mikor elkezdjuk a sorszamokat az 1/7-re, 2/6-ra, satobbi aggatni, akkor
22-vel kezdunk, 23 -al folytatjuk, es igy rogton megvan, hogy a 23-nak
a 2/6 felelt meg.
Vegyuk meg az altalad irt 25-ot,
a modszer eloszor eldonti, hogy ez is a hetedik vonalon van,
mivel
21=(1+2+..+6) < 25 =< (1+2+3+..+7)=28.
Tehat a hozza tartozo racionalis szam a hetedik vonalon van.
Az elso hat vonalon osszesen 21 szam van, a 25 ennel 4-el nagyobb,
szoval a 25-odik elem a negyedik elem lesz ebben a sorozatban:
Sziasztok! Az én matek problémám (:S) : Racionális számok sorbarendezhetőségét (és így azt, h megszámlálhatóan végtelen a számosságuk) szokták úgy megmagyarázni látványosan, hogy táblázatszerűen felírják, és ott egy meghatározott módon húzott vonallal összekötik az elemeket (lehet, h ezt kicsit hülyén írtam le, én nem vagyok matekos, de aki tanulta annak talán rémlik...valahogy igy nez ki:)
1/1 1/2 1/3 1/4 1/5 1/6 ...
2/1 2/2 2/3 2/4 2/5 2/6...
3/1 3/2 3/3 3/4 3/5 3/6 ...
4/1 4/2 ...
5/1 ...
...
A vonal pedig így rendezi sorba őket: 1/1 1/2 2/1 3/1 2/2 1/3 1/4 2/3 3/2 4/1 5/1 4/2 3/3 2/4 1/5 1/6 2/5 ... stbstb a végtelenségig...
Azt szeretném kérdezni, hogy szerintetek van e valamilyen szabály, algoritmus, ami leírja nekem, hogy a vonal által meghatározott sorozatban melyik tört fog az n. helyen állni?
Egy progit kéne írnia az ismerősömnek, ahol ha beírod pl h 25, akkor a 25 elemét írja ki a sorozatnak (4/4), és kíváncsi vagyok, hogy létezik-e szép elegáns megoldás ahol az n. elemhez vmilyen szabály szerint lehet a törtet rendelni, vagy más felé keresgéljünk. Ha valaki tudna segíteni, annak előre is köszi :)
