Fórum: "ujjgyakorlatok"

Tegyük fel, hogy a sztringnek csak a "10"-zel kezdődő hétjegyű számokat kell tartalmaznia legalább egyszer. Rendezzük ezeket növekvő sorrendbe. A 32 db második helyiértékes 0 különböző helyre fog kerülni a sztringben, mert a mögöttük álló 5 bites számok különbözők. Az első 16 szám harmadik helyiértékes nullája is mind különböző lesz, mert a mögöttük álló 4 bites számok különbözők, ugyanígy az első 8 negyedik, az első 4 ötödik, az első 2 hatodik, az első 1 hetedik helyiértékes 0 is mind más. (Különböző helyiértékű 0-k is különbözők, mert balra különböző számú 0 valasztja el a kezdő 1-estől.) Ez összesen 32+16+...+1=63 darab nulla, tehát nincs 127-nél rövidebb sztring.

Hadd folytassam a tegnapi gondolatomat. Mar megallapitottuk, hogy ha pontosan 64 egyessel sikerul a feladat, akkor minden egyessel kezdodo 7-jegyu szam pontosan egyszer szerepel. Ez azt jelenti, hogy ha egy ilyen bitsorozatot abrazolunk a grafon, akkor a kapott vonalban minden olyan el pontosan egyszer szerepel, ami egy olyan csucsbol indul, ami 1-essel kezdodik. Sporolni csak azokon az eleken lehetne, amik a 0-assal kezdodo elekbol indulnak. Ezek az elek azonban az egyetlen (000000,000000) elen kivul fat alkotnak, ezert nem lehet elhagyni beloluk azon a bizonyos egy elen kivul. Ha ugyanis az egesz grafbol kivonjuk a vonalat, akkor csak a fa elei maradhatnak meg (de azok elvileg akarmilyen elojellel, hiszen lehetne, hogy egy 0-val indulo elen tobbszor megyunk at), de egy fan ez csak ugy lehetseges, ha minden el 0-szor van benne. Tehat legalabb 63 nullasra valoban szukseg van. (Ezt ennel biztos egyszerubben is be lehet latni.)

Meg egy megjegyzes. A grafos megkozelitesbol lehet sejteni, hogy valojaban nagyon sok ilyen de Bruijn kor van. Ez tenyleg igy igaz: a A016031 sorozat megadja ezek szamat.

Ebbol az is kovetkezik, hogy nagyon konnyu de Bruijn kort eloallitani: egyszeruen ki kell indulni a 0000000 sorozatbol, es utana irni veletlen biteket arra vigyazva, hogy ne vegyuk egyik 7 bites szamot sem tobbszor. Ekkor persze elofordulhat, hogy levagjuk a graf egy reszet, ezert nem tudjuk befejezni a kort, de ilyenkor egyszeruen ujra probalkozhatunk, es hamar sikerulni fog. Az elobb ezzel az egyszeru veletlen modszerrel allitottam elo a szamokat. Itt van a kod, ha valakit erdekel.

Kedves Jónás!

Nagyon szép a bizonyítás! Igazi "vezérlő dinamika". De nézzük meg mit is láttunk be ezzel. n=7 esetén a számjegyek 6 jegyűek és 2⁶=64 db van belőlük, tehát a gráfnak 128 éle van. Indulunk az egyik csúcsból és bejárjuk az Euler kört. Az első szám 6 jegyű és minden élen való áthaladás egyel növeli a szám hosszát. Tehát 6+2*64=134 jegyű számot állítottunk elő, mely tartalmazza az összes 7 hosszúságú bitsorozatot, de 67 db 1-es számjegyet tartalmaz.

Példa képpen mutatom az n=4 jegyű esetet.

Akkor lelövöm a "vezérlő dinamikát". Nem akartam rögtön elmondani, mert ismertem (Simonyi tanár úr gyakorlatán volt feladat); hadd gondolkodjanak a "fiatalok". Azt viszont nem tudom megmondani, hogy kevesebb nullával le lehet-e írni az 1000000...1111111 számokat. (Azért elgondolkozom még rajta, most hogy a bizonyítást átgondoltam, lehet, hogy könnyű lesz.) Ha viszont megengedünk 64-nél több egyest, akkor azt hiszem hogy összesen 127-nél kevesebb számjeggyel is le lehet írni őket, de nem tudom, hány számjegy kell.

Aki tehát gondolkozni akar a 64 számjegy bizonyításán, az ne olvasson tovább.

Azt fogom belátni, hogy bármely n-re létezik ún de Bruijn-ciklus, vagyis hogy fel lehet írni egy kört 2ⁿ bitből úgy, hogy a körből n szomszédos bitet összeolvasva minden n hosszú bitsorozatot pontosan egyszer kapunk meg. Ha már tudjuk, hogy van n=7-re de Bruijn-ciklus, akkor ezt felvágva a 0000000 előfordulásának utolsó számjegyénél, egy megfelelő 127 hosszú bitsorozatot kapunk. (Azt könnyű látni, hogy pontosan 64 egyes van benne.)

Ehhez pedig vegyünk egy irányított gráfot, amelynek csúcsai az n-1 hosszú bitsorozatok, az (u,v) pedig akkor és csak akkor él, ha u utolsó n-2 bitje megegyezik v első n-2 bitjével. Ebben a gráfban van Euler-kör, mert összefüggő, és minden csúcsának megegyezik a ki- és a befoka, ugyanis mindkettő 2. Ha nézzük a gráf egy (u,v) élét, ezt jellemezhetjük egy n bites számmal, amit úgy kapunk, hogy u és v bitjeit egymásra helyezzük úgy, hogy fedjék egymást. Két szomszédos élhez két olyan szám tartozik, hogy az első él utolsó n-1 bitje éppen a második él első n bitje, ez tudniillik a közös csúcs. Ebből következik, hogy egy Euler-kör éppen egy de Bruijn körnek felel meg.

(A Konkrét Matematika egyébként egy helyen megemlíti a de Bruijn köröket, noha ahhoz a bizonyításhoz, ahol használja, valójában nincs szükség rájuk. Bizonyítást nem ad a körök létezésére, csak hivatkozik a Programozás Művészetére.)

Kedves Jónás és Levi!

Örülök, hogy "rákattantatok" a problémára! Bevallom nektek, hogy én is csak n=4-jegyűig írtam fel, mint Levi és ebből gondoltam, hogy nagyobb n-ekre is igaz.

Külön gratula Jónásnak, hogy volt türelme hozzá!

Bár ez már nem ujjgyakorlat, de jó lenne, ha valaki rámutatna a "vezérlő dinamikára", szóval, hogy miért lehet ezt minden n-re megtenni!

Jó kérdés a 0-k számának csökkentése is!

Az előzőben értelemszerűen 64 egyes számjeggyel értendő.

Nyilvánvaló, hogy legalább 64 egyes szükséges is, mert minden szám egyessel kezdődik. A kérdés tehát a következő: le lehet-e írni 64 egyessel, de 63-nál kevesebb nullával az összes pontosan 7-jegyű bináris számot, és ha igen, akkor hány nulla kell ehhez?

Nos, 64 számjeggyel fel lehet írni őket:

1001000010101011001011011010000011001110011000011101010011110010\ 011011111110100101000110101111011000100010111011100011111000000

Azonban ez 127 számjegy, ezért nem valószínű, hogy egy fiú egy sorba fel tudja írni őket (ha több sorba írja, akkor már meg kell ismételni legalább egy 1-est). Itt a fórumon sem fért el egy sorban, ezért meg kellett törnöm. Én tehát arra szavazok, hogy Jancsi ugrat minket, valójában Juliska írta a számsort.

Lehet, hogy ennél kevesebb számjeggyel is meg lehet csinálni, nem tudom.

Sejtés a 67.b feladatra: Ha veszünk egy n számjegyű számot (csupa 0-ból és 1-ből, akkor a keresett "láncban" mindig 2^n-1 darab 1-es lesz (és ekkor 2^n-1-1 db 0).

n=2 esetén variációk: 11,10 a lánc:110 és 2^n-1=2, azaz itt müködik

n=3 esetén variációk: 111, 110, 101, 100 a lánc: 1110100 és 2^n-1=4, azaz itt is működik

n=4-re is megnéztem, azt most nem írom le, tehát ha a sejtés igaz, akkor n=7 esetén 2^n-1=64 lesz. Azaz elvileg Jancsi igazat mondott.

Arra gondoltam csavarként, hogy írhatja folyamatosan egymás után a számjegyeket és bármely egymás után következő hét számjegy lehet egy új 7-jegyű szám, ha 1-es áll az elején.

67.b feladat: Jancsi azt állítja, hogy sikerült felírnia az összes 7 jegyű 1 és 0 számjegyből álló számot 64 db 1-es felhasználásával? Igaza van-e Jancsinak?

Szép egyszerű és jó a megoldás. Nincsen semmi csel, ez egy "ujjgyakorlat" volt :-)

Az első számjegy csak 1-es lehet a további 6 helyiértéken pedig 0 vagy 1, tehát kétféle számjegy állhat. Így 2⁶=64 db ilyen szám van. Írjuk egymás alá ezeket a számokat. Az első oszlopban 64 db 1-es van a többi oszlopban pedig a számjegyek fele 1-es fele 0. Így 64+6*32=256-szor kellett Jancsinak leírnia az 1-es számjegyet.( Feltéve persze, hogy nincs valami trükk a felírásban, ami Csimbytől azért elvárható! )

67.feladat Jancsi felírta az összes olyan hétjegyű egész számot, amely csak 0 és 1 számjegyeket tartalmaz. Hányszor írta le az 1-es számjegyet?

Hello Fiúk!

Kösz a megoldásokat! Valóban a nagy Fermat spec. esete és könnyen belátható. Joci tanulj TeX-et, megéri. Ha már megvan a lehetőség szép képletek írására, használjuk ki!

Ha a-1,a,a+1 köbeit vesszük és rendezzük, elegánsabban kijön. Átalakítások után azt kapjuk, hogy a2(a-6)=2. (az a után a 2 a négyzetet jelölné, csak még lusta voltam a TeX-et megtanulni :) A szorzat mindét tagja egész, mert 'a' is az. Az egyes eseteket gyorsan végig lehet futni.

Suhanc egyenletét és a kongruencia szabályait felhasználva:

Ha a 0 maradékot ad 4-gyel osztva, akkor a bal oldal osztható 4-gyel, a jobb oldal 3 maradékot ad 4-gyel osztva.

Ha a 1 maradékot ad 4-gyel osztva, akkor a bal oldal 1 maradékot, a jobb oldal 3 maradékot ad 4-gyel osztva.

Ha a 2 maradékot ad 4-gyel osztva, akkor a bal oldal osztható 4-gyel, a jobb oldal 1 maradékot ad 4-gyel osztva.

Ha a 3 maradékot ad 4-gyel osztva, akkor a bal oldal 3 maradékot, a jobb oldal 1 maradékot ad 4-gyel osztva.

Mind a 4 esetben ellentmondásra jutottunk, tehát nincsen olyan a amely eleget tenne a feltételeknek.

Kedves László és Suhanc!

Nem tudom, hogy mennyire elegáns vagy nem, de a nagy Fermat sejtés (illetve ma már tétel) nem elég erre? Azaz az xⁿ+yⁿ=zⁿ-nek n>2 esetén nincs megoldása.

Kedves László!

Egy nem túl elegáns megodásom lenne a feladatodra:

Legyen a három egymást követő köbszám a³,(a+1)³és(a+2)³ ! Adjunk felső korlátot a értékére, majd a maradék eseteket megvizsgáljuk a végén. A feladat állítása szerint (rendezve az egyenletet):

a³=3a²+9a+7

Bonsuk a³-t három egyenlő részre, mert a jobb oldalon három tag van. Nyilván, ha

feltételek egyszerre teljesülnek, az egyenletnek nem lehet megoldása, hisz a bal oldal határozottan nagyobb. A három egyenlőtlenség közül az első a legenyhébb, ezért a>9 esetén biztosan nincs megoldás.

Maradt tehát 10 esetünk 0-tól 9 ig. Ezeket behelyettesítve az egynletbe nem kapunk kielégítő megoldást, ezzel a feladat állítását bizonyítottuk.

66. feladat: Bbh. három egymást követő természetes szám közül a legnagyobb köbe nem lehet egyenlő a másik kettő köbének összegével.

Szerintem nagyon szép ez a feladat, várjunk a megoldással.

Az 55.Feladat szemmel láthatólag nem hozott lázba senkit...;)

Ha esetleg valaki mégis lenne olyan "elvetemült", egy kis segítség:

Ez egy olyan "közepes" feladat...

Kedves Mindenki!

Ez egy olyan apró gondolat... de szép!:)

65.Feladat:

Igazoljuk, hogy :

Páros n-re is igaz lesz, mert ekkor k>n és n végén k-n db 0 áll.

Ekkor viszont (2^k-1-n) végén k-n db 1-es fog állni előttük (balra) 0 áll. Így +1 hozzáadása (k-n) db 1-esből 1 db 1-est csinál. A változás -(k-n)+1 a számjegyek összegében.

A számjegyek összege: (m-1)+(k-m)-(k-n)+1=n.

Hello Jónás!

Úgy látszik igazad van, mindketten elszámoltuk Csimbivel: n=2004₁₀=11111010100₂

A számjegyek összege: m=7. Mivel 2 db 0-ra végződik k=2006 lesz. Az első részösszegben m-1=6db 1-es marad. 2²⁰⁰⁶-1-n részben k-m=1999 db 1-es van és ..011-re végződik, így a +1 hozzáadása 1-el csökkenti az 1-esek számát: 6+1999-1=2004.

Ami persze nem jelenti azt, hogy minden n-re igaz.

Páratlan n esetén azonban mindig igaz lesz, mert ilyenkor n 1-re végződik. k=n és 2ⁿ-1-n pedig 0-ra végződik, így a +1 a végén 1-el növelei a számjegyek összegét. m-1+k-m+1=k=n.

Erdekes, nekem 2004 jon ki.

2004*(2²004-1)=111110100111111111111111...1111111111100000101100

Az eredmeny osszesen 2015 szamjegybol all, ebbol 11 nullas es 2004 egyes.

Kedves Suhanc!

Örülök, hogy foglalkoztál a témával. Már azt gondoltam feledésbe merül. (Persze azt nem hagytam volna!)

Szóval az első pár számra én is kipróbáltam és működik amit mondtál. De valahol elromlik, mert annyira szerettem volna, hogy 2004-nél a számjegyek összege 2004 legyen, hogy kétszer is átszámoltam és úgyis csak 2003 lett és Csimbinek is ez jött ki. Tehát 2004-nél már nem igaz!

Én maradtam 2-es számrendszerben. Lenyen n számjegyeinek összege m.

n^.(2ⁿ-1)=n^.2ⁿ-n

n^.2ⁿ legalább n db 0-ra végződő szám. Legyen jobbról az első 1-es a k+1-edik helyiértéken.nk Ekkor

n^.2ⁿ-n=(n^.2ⁿ-2^k)+(2^k-n)=(n^.2ⁿ-2^k)+(2^k-1-n)+1

Az összeg első részében a számjegyek összege m-1 és ez független a többitől. 2^k-1 k db 1-esből álló szám. Ha ebből elvesszük n-t, a kivonás m darab 0-t hoz létre, így a számjegyek összege a második részben k-m. Sajnos ez változhat még ha az 1-et a végén hozzáadjuk.

Ha nem változik, mert pl. n 0-ra végződik (k>n) akkor a számjegyek összege: m-1+k-m+1=k.

n=k esetén n pont 1-esre végződik, így az 1-es hozzáadása változtathat a második részösszeg számjegyeinek összegén.

Ha ez idáig jó, akkor nem vagyunk messze a megoldástól!