Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Érdekes matekfeladatok

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]    [89]    [90]    [91]    [92]    [93]    [94]    [95]    [96]    [97]    [98]    [99]    [100]    [101]    [102]    [103]    [104]    [105]    [106]    [107]    [108]    [109]    [110]    [111]    [112]    [113]    [114]    [115]    [116]    [117]    [118]    [119]    [120]    [121]    [122]    [123]    [124]    [125]    [126]    [127]    [128]    [129]    [130]    [131]    [132]    [133]    [134]    [135]    [136]    [137]    [138]    [139]    [140]    [141]    [142]    [143]    [144]    [145]    [146]    [147]    [148]    [149]    [150]    [151]    [152]    [153]    [154]    [155]    [156]    [157]    [158]    [159]    [160]    [161]  

Szeretnél hozzászólni? Jelentkezz be.
[3121] jonas2009-12-22 12:09:17

A (b) kérdésre. Ha minden idomban elhelyezhető egy r sugarú kör, de az egész elrendezést magába foglalja egy R sugarú kör, ahol R/r konstans, akkor nyilván konstans sok idom van, mert több kis kör nem fér el a nagy körben. Így aztán az eredeti kérdést pontosítanod kéne.

Azt kell először eldönteni, hogy ilyen feltétellel konstans sok idommal lehet-e tetszőlegesen nagy minimális lépésszámot elérni. Ha nem szükséges, hogy az idomok összefüggőek legyenek, akkor szerintem lehet.

Előzmény: [3118] Csimby, 2009-12-22 00:59:19
[3120] jonas2009-12-22 12:00:23

Azt, hogy “a legkisebb síkidomban elhelyezhető egy r sugarú kör”, úgy érted, hogy minden síkidomban elhelyezhető egy ilyen kör? Mert a legkisebb nem egész egyértelmű.

Előzmény: [3118] Csimby, 2009-12-22 00:59:19
[3119] Sirpi2009-12-22 10:26:57

Pontosan mit értesz mozgatáson? Ha két síkidomom van, az egyik egy egységnégyzet, a másik pedig egy egységnégyzetekből kirakott labirintus (a négyzetek alkotják a falakat), és berakom a kisnégyzetet valahova a labirintus belsejébe, akkor ezt a konfigurációt 1, vagy csak nagyon sok mozgatással tudom szétszedni? Tehát a mozgatás történhet tetszőleges pályán vagy csak egyenesen? Lehet-e forgatni szétszedés közben?

Amúgy valami ilyesmivel biztos el lehet érni exponenciális hosszt.

Előzmény: [3118] Csimby, 2009-12-22 00:59:19
[3118] Csimby2009-12-22 00:59:19

504.feladat Helyezzünk el n db síkidomot a síkon. Legyen S(n), hogy hány db mozgatással tudjuk őket "szétszedni" (akkor mondjuk, hogy szét vannak szedve, ha 1 eltolással bármely 2 egymástól bármilyen messzire elvihető). Van-e olyan elhelyezés alkalmas síkidomokra, hogy:

a. S(n) n polinomja, de annak eldöntése, hogy szétszedhető-e NP-teljes

b. S(n) nagyságrendje en. Továbbá a legkisebb síkidomban elhelyezhető egy r sugarú kör, az elhelyezést magában foglalja egy R sugarú kör és R/r konstans (nem függ n-től)

c. n=3, K tetszőleges poz. egész és S(n)>K

[3117] Lóczi Lajos2009-12-20 00:57:06

A legkisebb olyan kezdőérték, amelyből indulva kettes ciklusba kerülünk, az n=40. (Itt elég 11 lépés.)

Előzmény: [3116] jonas, 2009-12-19 17:38:07
[3116] jonas2009-12-19 17:38:07

Van egyáltalán kettes ciklus? A fórumon szerintem még nem szerepelt.

Előzmény: [3114] Lóczi Lajos, 2009-12-19 12:22:37
[3115] Róbert Gida2009-12-19 14:28:38

Csak annyi a lényeges, hogy C(x)=n, (nem érdekes, hogy fixpontnál x=n). Mert akkor n csak nagyon kevés féle szám lehet, konkrétan binomial(d+9,9), ha n legfeljebb d jegyű. Ez d=21-re is csak 14307150 (ha x az hosszabb, mint 21 jegy,akkor C(x)<x, így nem lehet fixpont), ez pedig egy perc alatt végignézhető. Egy gráf is építhető, élnek egy (x,C(x)) felel meg. Hosszabb ciklusok keresése is ugyanígy mehet, tulajdonképpen az összes kört is megkereshetnénk, diszjunkt irányított körök (esetleg kettő hosszúak) és hurokélek uniójára esik szét a gráf, hiszen minden kifok 1 a gráfban. (minden 21-nél hosszabb szám elég sok iteráció után 21-nél rövidebbre esik, így itt is elég ezeket nézni).

Előzmény: [3114] Lóczi Lajos, 2009-12-19 12:22:37
[3114] Lóczi Lajos2009-12-19 12:22:37

Kíváncsi lennék, hogy a fixpontokat milyen egyszerűsítési feltevésekkel/esetszétválasztásokkal/algoritmussal állítottad elő konkrétan.

Találtál esetleg menet közben 2-nél hosszabb ciklust? (Én eddig csak ilyenre bukkantam rá.)

Előzmény: [3112] Róbert Gida, 2009-12-19 00:26:20
[3113] Róbert Gida2009-12-19 00:40:19

Hopp, csak úgy rákerestem egy tagra a google-al, és az első találat Sloane online adatbázisában levő A047841 sorozat volt. Aszerint is 109 fixpont van.

Előzmény: [3112] Róbert Gida, 2009-12-19 00:26:20
[3112] Róbert Gida2009-12-19 00:26:20

10-es számrendszerben összesen 109 fixpont van, éspedig:

22,10213223,10311233,10313314,10313315,10313316,10313317,10313318,10313319,21322314, 21322315,21322316,21322317,21322318,21322319,31123314,31123315,31123316,31123317,31123318, 31123319,31331415,31331416,31331417,31331418,31331419,31331516,31331517,31331518,31331519, 31331617,31331618,31331619,31331718,31331719,31331819,1031223314,1031223315,1031223316, 1031223317,1031223318,1031223319,3122331415,3122331416,3122331417,3122331418,3122331419, 3122331516,3122331517,3122331518,3122331519,3122331617,3122331618,3122331619,3122331718, 3122331719,3122331819,10413223241516,10413223241517,10413223241518,10413223241519, 10413223241617,10413223241618,10413223241619,10413223241718,10413223241719,10413223241819, 41322324151617,41322324151618,41322324151619,41322324151718,41322324151719,41322324151819, 41322324161718,41322324161719,41322324161819,41322324171819,1051322314251617, 1051322314251618,1051322314251619,1051322314251718,1051322314251719,1051322314251819, 1051322325161718,1051322325161719,1051322325161819,1051322325171819,5132231425161718, 5132231425161719,5132231425161819,5132231425171819,5132232516171819,106132231415261718, 106132231415261719,106132231415261819,106132231426171819,106132231526171819, 613223141526171819,1011112131415161718,1011112131415161719,1011112131415161819, 1011112131415171819,1011112131416171819,1011112131516171819,1011112141516171819, 1011113141516171819,1111213141516171819,10713223141516271819,101112213141516171819

Előzmény: [3110] Sirpi, 2009-12-17 12:00:10
[3111] Lóczi Lajos2009-12-18 00:22:57

Ezzel kapcsolatban érdekes volt megfigyelni azt, hogy a legkisebb fixpontok minden számrendszerben csupa egyforma számjegyből állnak. (Vajon ezt a tényt külön be lehetne/lehetett volna látni a konkrét értékek ismerete nélkül?)

Előzmény: [3110] Sirpi, 2009-12-17 12:00:10
[3110] Sirpi2009-12-17 12:00:10

Kicsit átírtam a progit, hogy más számrendszerekkel is menjen. Ezeket találtam a kül. számrendszerekre:

2-es: 111, 1101001

3-as: 22, 10111, 11112, 100101, 2021102, 1011122, 10010122

4-es: 22, 1011112, 1011113, 1111213, 10213223, 10311233, 101112213

5-ös: 22, 10213223, 10311233, 10313314, 21322314, 31123314, 101111x1y (1<x<y), 10111221314

Elvileg ezekre nincs is más megoldás.

10-esre ezek a legfeljebb 8-jegyű megoldások, itt is csak pár sorozat van (3<x<y): 22, 10213223, 10311233, 1031331x, 2132231x, 3112331x, 31331x1y

És ugye igaz, hogy ha van olyan megoldás, ahol minden darabszám egyjegyű, akkor az minden magasabb számrendszerben is megoldás lesz.

[3109] Sirpi2009-12-14 13:09:39

Nem írtam át a progit a 2-es számrendszer kezelésére (amúgy is csak otthon van meg, ezt meg a villamoson agyaltam reggel fejben). De akkor kicsit kipofozom majd.

Előzmény: [3108] jonas, 2009-12-14 11:33:27
[3108] jonas2009-12-14 11:33:27

Érdekes, azt gondoltam, hogy a kettes számrendszerbeli kis megoldásokat számítógéppel könnyen megtalálod. Van pontosan egy kisebb is a 1101001-nél.

Előzmény: [3107] Sirpi, 2009-12-14 09:17:31
[3107] Sirpi2009-12-14 09:17:31

Ez a C függvény más számrendszerek esetén is érdekes lehet. Pl. 2-es számrendszernél szenvedtem egy kicsit, mire összehoztam a 1101001 számot (tudtok még?). Itt ugyanis nem megy a 22, mint legkisebb megoldás, ami minden más számrendszernél működik.

Előzmény: [3096] Lóczi Lajos, 2009-12-12 11:16:37
[3106] Lóczi Lajos2009-12-13 20:41:35

Igen, pont erre én is rátaláltam véletlenül, és 5 perc kísérletezés után sem találtam nagyobbat :)

Előzmény: [3105] jonas, 2009-12-13 15:34:43
[3105] jonas2009-12-13 15:34:43

Egy nagy fixpont például a 101112213141516171819. Azt nem mondom, hogy nincs ennél is nagyobb.

Előzmény: [3103] Lóczi Lajos, 2009-12-13 01:15:16
[3104] jonas2009-12-13 14:36:06

A C függvényről szóló 6. feladat nem nehéz. Könnyű látni, hogy ha n legfeljebb 10n jegyből áll, akkor C(n) legfeljebb 10(n+1) jegyből. Így aztán 30 jegyűnél hosszabb fixpont nem létezhet, tehát kell lennie legnagyobb fixpontnak. Ugyanez részben megoldja az 5. feladatot is, ugyanis azt bizonyítja, hogy minden számból indulva előbb-utóbb olyan ciklusba esünk, amiben minden elem legfeljebb 101030, így a ciklus is legfeljebb ilyen hosszú. Hasonlóan viszont azt is könnyű látni, hogy van tetszőlegesen hosszú átmeneti szakasz, mert ha n legalább 10.10n jegyű, akkor C(n) legalább 1+n jegyű (vagy valami hasonló egyenlőtlenség igaz).

A 3. és 4. feladatot feltehetően kimerítő kereséssel meg lehet válaszolni, kivéve ha valamiért nincsen 2-es ciklus, vagy a legkisebb is nagyon nagy.

Előzmény: [3103] Lóczi Lajos, 2009-12-13 01:15:16
[3103] Lóczi Lajos2009-12-13 01:15:16

Következzen végül néhány újabb kérdés és sejtés a C függvény kapcsán, amelyek természetes módon felmerülnek és amelyek között szerintem nehezebbek is vannak. (A saját tippjeimet egyelőre nem írom ide, hogy ne befolyásoljak senkit.)

Egy n szám 2-es ciklus, ha C(n)\nen, de C(C(n))=n. Hasonlóan definálhatók a k-hosszú ciklusok is.

3. feladat. Melyik az a legkisebb n, amely (a C leképezés iterációja során) előbb-utóbb 2-es ciklust eredményez?

4. feladat. Melyik az a legkisebb n, amely rögtön egy 2-es ciklus egyik tagja?

5. feladat. Igaz-e, hogy minden kezdőértékre a C iteráltjaiból alkotott sorozat előbb-utóbb ciklikussá válik? Ha igen, van-e tetszőlegesen hosszú "átmeneti szakasz", mielőtt a sorozat ciklizálni kezd? Van-e maximális ciklushossz, vagy pedig tetszőlegesen hosszú ciklusok előfordulhatnak?

6. feladat. Igaz-e, hogy C-nek van legnagyobb fixpontja? Ha igen, konkrétan melyik szám az?

A fenti C leképezést egyébként a Conway-féle "look and say" sorozat mintájára gyártottam, csak annál egyszerűbb. A Conway-féle sorozat sok érdekes tulajdonsággal bír, különösen meghökkentő a rá vonatkozó "cosmological theorem".

Előzmény: [3096] Lóczi Lajos, 2009-12-12 11:16:37
[3102] Radián2009-12-12 19:41:48

Ha vesszük a hatjegyűeket, ott 3 db különböző számjegy kell szerepeljen. A szám mindegy jegye kisebb az 5-nél. Ha a számok C(n) alakját akarom felírni az alábbi esetek állhatnak fenn:

1.) 4db x 1db y 1db z (a 4-es és 2 db 1-es sorrendje persze más is lehet, 1,4,1 1,1,4.) Tehát a számban biztosan fog szerepelni az 1,4,q számjegyek. 1-esből biztosan kell legyen legalább 2 db a C(n) felírás alapján, így a számban csak 4 db 1-es fordulhat elő, de ekkor nem az 1. ponti lenne a C(n) alak.

2.) 2db x 2db y 2db z Az 1. ponthoz hasonlóan n kellene tartalmazzon 3 db 2-est ,azaz C(n) alakjába kellene legyen egy 3db q alakú rész. Tehát ez az eset sem állhat elő.

3.) 1db x 2db y 3db z (Az 1,2,3 sorrendje más is lehet.) A szám eredeti alakjába tehát kell szerepeljen 1-es 2-es és 3-as, ezzel meg van az összes különböző jegy. Mivel x,y,z nem egyenlő egymással, így 1-esből 2-esből és 3-masból is több mint egy jegy fog szerepelni a számban, tehát nem lehet a C(n) alakja a 3. pontbeli.

Előzmény: [3101] Radián, 2009-12-12 19:17:27
[3101] Radián2009-12-12 19:17:27

A négyjegyűeket átfutottam. Egyik se lett jó. Elvileg csak a hatjegyűek között akadhat kisebb, de ezeket nem néztem meg rendesen. 4 jegyűeknél a szám pontosan két különböző számjegyet kell tartalmazzon, ráadásul mindkét jegyből 2-2 db van. E jegyek pedig a 0,1,2 közül kerülhetnek ki. Mivel mindkét jegyből 2-2 db van, ezért a keresett számok csak 2x2x alakúak lehetnek melyek nyilván nem egyenlők a hozzájuk rendelhető C(2x2x)-szel.

Előzmény: [3099] Valezius, 2009-12-12 18:07:21
[3100] Sirpi2009-12-12 18:17:40

5 perc alatt összeütöttem rá egy progit, amiből kiderült, hogy ez-e a 2. legkisebb... Annyit mindenesetre elárulok, hogy legfeljebb 8 jegyű megoldás 36 db van.

Előzmény: [3099] Valezius, 2009-12-12 18:07:21
[3099] Valezius2009-12-12 18:07:21

Ha 8 jegyűt keresünk, akkor 10-val kell kezdődnie, a 3. jegy 0,1,2 lehet, amiből a 0 nem lehet, de az 1 sem, hisz ez a helyiérték az egyesek számát mutatja. 1021x2yz alakú számok maradtak. x legalább 3. És ekkor kijön, amit írtál. Amiről elhiszem, hogy kisebb, mint az enyém :) Tehát ha van kisebb, akkor az 4 vagy 6 jegyű lehet.

Előzmény: [3098] Radián, 2009-12-12 16:12:24
[3098] Radián2009-12-12 16:12:24

A második legkisebb szerintem nem az 10311233. Egyelőre a legjobb amit találtam a 2. részre az 10213223 de szerintem ez is javítható.

Előzmény: [3097] Valezius, 2009-12-12 14:34:11
[3097] Valezius2009-12-12 14:34:11

22 a legkisebb, a második pedig szerintem 10311233.

Előzmény: [3096] Lóczi Lajos, 2009-12-12 11:16:37

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]    [89]    [90]    [91]    [92]    [93]    [94]    [95]    [96]    [97]    [98]    [99]    [100]    [101]    [102]    [103]    [104]    [105]    [106]    [107]    [108]    [109]    [110]    [111]    [112]    [113]    [114]    [115]    [116]    [117]    [118]    [119]    [120]    [121]    [122]    [123]    [124]    [125]    [126]    [127]    [128]    [129]    [130]    [131]    [132]    [133]    [134]    [135]    [136]    [137]    [138]    [139]    [140]    [141]    [142]    [143]    [144]    [145]    [146]    [147]    [148]    [149]    [150]    [151]    [152]    [153]    [154]    [155]    [156]    [157]    [158]    [159]    [160]    [161]