A programozó otthona

Beszélgettünk Dávid kollégával, és megint előkerültek a geek lét előnyei. Mert annyira büszke a vízmértékes esetre (joggal, mindjárt kivesézem). Én meg ezúttal azzal vágtam vissza, hogy miért mit gondol, nálam tán nem 17 csipesszel van feltéve a függöny?

A vízmérték

Dávid vásárolt egy TESCO gazdaságos vízmértéket, amiről csak később derült ki, hogy gyárilag hibás, ugyanis hiába tette vízszintes felületre a cuccot: a buborék nem volt középen.

A vízmérték ugyebár egy nagy, fából készült téglatest, benne azzal a kis csővel, amiben a víz meg a buborék van. A cső a téglatesthez két csavarral van hozzáerősítve. Ezek szerencsére pont olyanok, hogy a csőnek a téglatesthez képesti szöge bizonyos határok között szabadon állítható. Ha tehát elég ügyesek lennénk, be tudnánk úgy állítani a dolgot, hogy a buborék pont középre kerüljön.

Ehhez azonban kellene egy vízszintes referenciafelület, ami a tyúk meg a tojás problémájának egyfajta asztalosi környezetbe emelt újraértelmezését adja. De szerencsére ez csak látszólag igaz. Ugyanis a vízmértéknek megvan az a kellemes tulajdonsága, hogy ha már tudod milyen egyenesre szeretnéd tenni, nem kell gondolkodni, hogy hogyan forgasd, mert mind a kétféleképpen ráteheted: a buboréknak mindkét esetben pont ugyanannyi eltérést kell mutatni a középső állapottól. Ez azonban akkor és csak akkor igaz, ha egyébként a dolog jól van beállítva. Magyarán ha ezt valahogy garantáljuk a csavarok tekergetésével, akkor egy jól behangolt vízmértéket kapunk.

A csipeszek

Függönyt ugye úgy könnyű feltenni, hogy fogod a két szélső csipeszt, felteszed rá a függöny két végét, aztán a középső csipeszre odacsípteted a függöny közepét. Utána lesz két részfeladatod, amit megint jó lenne a “közepét megkeresem, felcsíptetem a középső csipeszre” módon megoldani, majd így tovább a csipeszek elfogytáig, de gyakorta előfordul, hogy egy ponton valahogy páros sok csipesz marad! Ekkor ügyesen meg kell tippelni, hogy a függöny tökéletes felrakása után mekkora távolságra lennének egymástól a csipeszek, és innentől számolva kb. fél óra múlva már elégedetten hátra is dőlhetünk a kanapéban az addigra már tényleg csak egy kicsit csálé függönyt bámulva.

Na ezt így nem

Építsünk inkább egy an sorozatot – akkor is ha fáj -, aminek minden eleme azzal a roppant kellemes tulajdonsággal bír, hogy annyi csipesszel könnyű feltenni a függönyt.

a0 := 2 csipesz jó.

Ha most a két csipesz közé teszünk egy harmadikat, akkor arra az egy új csipeszre elég a függöny közepét felcsíptetni.

a1 := 3 csipesz jó.

Ha most megint minden két szomszédos csipesz közé beteszünk egy újabbat, akkor azokra ugyanígy a megfelelő darab közepének megkeresésével fel tudjuk tenni a függönyt.

a2 := 5 csipesz jó.

És így tovább, ha an csipeszt szerettünk, akkor an+1 = an + an -1 = 2 * an – 1 csipeszt megint szeretni fogunk.

De mennyi az az an?

Mivel a0 = 2 = 20 +1 , a1 = 3 = 21+1, az a sejtésünk támadhat, hogy a sorozat n-edik eleme an = 2n+1.

Nézzük teljes indukcióval.

Az n=0 ill. 1 eseteket már be is láttuk.

Tegyük fel, hogy valamilyen n-re az indukciós feltevés már igaz, akkor an+1 = 2 * an – 1 = 2 * (2n+1) – 1 = 2n+1+2-1 = 2n+1+1, és milyen meglepő: pontosan ezt akartuk igazolni. ∎

Imádom az ilyen megsejtjük, aztán majdcsak lesz valami jellegű bizonyításokat. Az ég világon semmit nem árulnak el a mögötte levő gondolatokról. De azért sikerült belátnuk az alábbi tételt.

Függönyökről szóló tétel: tetszőleges n nem negatív egész szám esetén an = 2n+1 számú csipeszre könnyű a függönyt felcsíptetni. (Speciálisan nálam 9 illetve 17 csipesszel vannak feltéve itthon.)

Tudom: menjek a picsába. Szeretnék.

  1. Ezekután muszáj lesz megkeresnem, hogy hogyan is lehet analitikai módszerekkel vizsgálni ilyesmi, rekurzívan definiált sorozatokat, mert az mégiscsak geekebb, ha “magától kijön” a zárt alak :)

  2. Eeegen, de sajnos ez pont egy nem-homogén probléma, azt meg sokkal problémásabb felgöngyölíteni. Ráadásul túl triviális a dolog, és semmi szépség nem lett volna benne, ha a “rendes módszerrel” viszem végig. Csak sokkal hosszabb lett volna tőle a bejegyzés.

  3. Igen, sajnos en is erre jutottam, hogy egy egyszeru eltolas sem jarhato… viszont ha most nem aludni akarnek inkabb, akkor lehet hogy elgondolkodnek azon, hogy nem lehet-e eloszoris ket, szinten rekurziv sorozat kulonbsegere felbontani…

  4. Na most lesz itt az ideje újraolvasni a Konkrét matematika első fejezetét a generátorfüggvényekről. :-)

    Az an = 2an-1 – 1 sorozatot homogénné alakítva (vonjuk ki egymásból két egymás utáni tagját) az an = 3an-1 – 2an-2 alakot kapjuk. Ezután ha tudnánk mik azok a generátorfüggvények, biztos kapásból kijönne a zárt alak, de nélkülük is elég annyit tippelni, hogy an talán felírható xn alakban (függetlenül attól, hogy ez nem igaz), és behelyettesítve megoldani x-re:

    xn = 3xn-1 – 2xn-2

    ⇒ x2 = 3x – 2

    ⇒ x ∈ {(3 ± sqrt(9-8)) / 2}

    ⇒ x ∈ {1, 2}

    Két külön megoldásunk van, úgyhogy ezek hatványainak lineáris kombinációjából kapjuk az igazi megfejtés alakját:

    an = u * (x1)n + v * (x2)n = u * 2n + v * 1n,

    azaz

    an = u * 2n + v, ahol u, v konstans értékek.

    Az eredeti alakból behelyettesítéssel kijön, hogy v=1, de u-ra tetszőleges számot választhatunk. (Például u=0-val az an = 1 konstans sorozat is megfelel a rekurzív képletnek.) Ha figyelembe vesszük az a0 = 2 kezdeti feltételt, akkor persze kiesik, hogy u=1.

    Mondjuk könnyebb, ha a megfejtést helyből kitalálja az ember.

  5. Wikipedia for the win.

    http://en.wikipedia.org/wiki/Examples_of_generating_functions#Worked_example_B:_Fibonacci_numbers

    Legyen

    f(x) := Σn(an * xn)

    ekkor a homogén alakból (an = 3an-1 – 2an-2) kijön, hogy

    f(x) majdnem egyenlő (3x – 2x2) * f(x), csak az első néhány tag különbözik. Ezekről is gondoskodva már

    f(x) = (3x – 2x2) * f(x) – 3a0 * x + a0 + a1 * x

    f(x) = (3x – 2x2) * f(x) – 6x + 2 + 3x

    f(x) = (3x – 2x2) * f(x) – 3x + 2

    f(x) = (-3x + 2) / (2x2 – 3x + 1)

    A fenti törtet felbontva (legyen ez otthoni házi feladat)

    f(x) = 1 / (1 – x) – 1 / (1 – 2x),

    vegyük észre(!), hogy f két geometriai sor összege, azaz a sor együtthatói másképp is kifejezhetők:

    f(x) = Σn(xn) + Σn(2n * xn) = Σn((2n + 1) * xn),

    amiből már leolvasható, hogy

    an = 2n + 1.

    Cool.

  6. Jól tolod! (De ezzel ellőttétek a manuális latex->html konverziós krediteteket erre a hónapra.)

  7. Mondjuk, hogy a két széle fel van csíptetve a függönynek.

    Induljunk el a posztban vázolt intervallumfelezéses eljárással. Vegyük észre, hogy minden körben megduplázzuk az intervallumok számát, és így a következő körben szükséges csipeszek számát is. Tehát 1, 2, 4, 8, stb. csipeszre lesz szükségünk, összesen ez ugye jól ismert, hogy 2n-1.

    Ehhez kell még hozzáadni a két szélső csipeszt. QED.

  8. OK, tehát ezzel gyűjtöttünk 400 EXP-t, de a következő szint eléréséhez azt is ki kellene találni, hogy mi a helyzet akkor, ha felezés mellett a harmadolást is megengedjük. (Harmadolni is viszonylag jól lehet szemmértéket használva.)

    Ha n csipesz jó, akkor tehát 2n – 1 és 3n – 2 csipesz is ugyanolyan jó lesz. Most vajon van-e zárt képlet?

  9. Lőry kommentjéhez csak annyit szeretnék hozzátenni, hogy én pl. nem tudok szemmértékkel harmadolni. :-)

  10. Naszóval, ha harmadolni is ér, akkor 2^a*3^b + 1 alakban felírt számok lesznek jók és csak azok.

    Tekintsük ugyanis az egyes lépések után az (egyébként egyenlő hosszú) intervallumok számát, innen persze csipeszek száma = intervallumok száma + 1. Felezés duplázza, harmadolás háromszorozza a számukat. Vegyük észre, hogy a dolog kommutatív: mindegy, hogy először harmadolunk és utána felezünk vagy fordítva, mindkét esetben 6-szor annyi intervallumunk lesz. Tehát a sorrend nem számít. Ha a-szor felezünk és b-szer harmadolunk, akkor épp a fenti képlet jön ki.

    Namost eddig szép és jó és egyszerű, de ha (szigorúan) monoton növő sorba szeretnénk rendezni a képletnek megfelelő számokat, akkor nehéz problémába ütközünk. Sejtésem szerint nemhogy explicit de még rekurzív alak sem adható. Valahogy a prímszámok felsorolásával egyenértékű problémának látszik, aki nem hiszi járjon utána. És mesélje el, hogy mire jutott.

    Ja és ha valakinek gyakorlati alkalmazásra kell, akkor szívesen átküldöm azt az excel fájlt, amiben az összes gyakorlati szempontból érdekes* fenti tulajdonságú szám sorba van rendezve.

    * Kb 10^100-on nagyságrendig**, ha valaki esetleg az ismert univerzum összes részecskéjét óhajtja csipesznek használni valamilyen kozmikus függönyhöz…

    ** Helyesen: 100-as nagyságrendig.