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]    [162]    [163]    [164]    [165]    [166]    [167]    [168]    [169]    [170]    [171]    [172]    [173]    [174]    [175]    [176]    [177]    [178]    [179]    [180]    [181]    [182]    [183]    [184]    [185]    [186]    [187]    [188]    [189]    [190]    [191]    [192]    [193]    [194]    [195]    [196]    [197]    [198]    [199]    [200]    [201]    [202]    [203]    [204]    [205]    [206]    [207]    [208]    [209]    [210]    [211]    [212]    [213]    [214]    [215]    [216]    [217]    [218]    [219]    [220]    [221]    [222]    [223]    [224]    [225]    [226]    [227]    [228]    [229]    [230]    [231]    [232]    [233]    [234]    [235]    [236]    [237]    [238]    [239]    [240]    [241]    [242]    [243]    [244]    [245]    [246]    [247]    [248]    [249]    [250]    [251]    [252]    [253]    [254]    [255]    [256]    [257]    [258]    [259]    [260]    [261]    [262]    [263]    [264]    [265]    [266]    [267]    [268]    [269]    [270]    [271]    [272]    [273]    [274]    [275]    [276]    [277]    [278]    [279]    [280]    [281]    [282]    [283]    [284]    [285]    [286]    [287]    [288]    [289]    [290]    [291]    [292]    [293]    [294]    [295]    [296]    [297]    [298]    [299]    [300]    [301]    [302]    [303]    [304]    [305]    [306]    [307]    [308]    [309]    [310]    [311]    [312]    [313]    [314]    [315]    [316]    [317]    [318]    [319]    [320]    [321]    [322]    [323]    [324]    [325]    [326]    [327]    [328]    [329]    [330]    [331]    [332]    [333]    [334]    [335]    [336]    [337]    [338]    [339]    [340]    [341]    [342]    [343]    [344]    [345]    [346]    [347]    [348]    [349]    [350]    [351]    [352]    [353]    [354]    [355]    [356]    [357]    [358]    [359]    [360]    [361]    [362]    [363]    [364]    [365]    [366]    [367]    [368]    [369]    [370]    [371]    [372]    [373]    [374]    [375]    [376]    [377]    [378]    [379]    [380]    [381]    [382]    [383]    [384]    [385]    [386]    [387]    [388]    [389]    [390]    [391]    [392]    [393]    [394]    [395]    [396]    [397]    [398]    [399]    [400]    [401]    [402]  

Szeretnél hozzászólni? Jelentkezz be.
[2653] Lajosz2008-05-19 16:15:27

Köszönöm Sirpi!

A lenti számháromszög két utolsó sora a 12 és 13 esetét írja le, azok már nem fértek el egy sorba...

Értelemszerűen az előző sorok számainak összegei (felfelé haladva) 3 - nak 11, 10, 9,...1, 0 hatványai.

Ez emlékeztet a permutációk fixpontjaira! Az ismétléses variáció fixpontjaira van valahol irodalom?

A bal oldali oszlop:1 2 4 8 16...mint a permutációknál: a nulla fixpontok darabszámát jelentené. majd jobbra haladva az egy, kettő, stb fixpontok darabszámát!

Egyáltalán van ilyen fogalom? Ha van milyen néven keressem?

Mert ez, ha általánosítjuk, "m" alapú hatvánnyal leírható minden ismétléses variációra igaz!

m=3

1

2, 1

4, 4, 1

8, 12, 6, 1

16, 32, 24, 8, 1

32, 80, 80, 40, 10, 1

64, 192, 240, 160, 60, 12, 1

128, 448, 672, 560, 280, 84, 14, 1

512, 2304, 4608, 5376, 4032, 2016, 672, 144, 18, 1

1024, 5120, 11520, 15360, 13440, 8064, 3360, 960, 180, 20, 1

2048, 11264, 28160, 42240, 42240, 29568, 14784, 5280, 1320, 220, 22,1

4096, 24576, 67584, 112640, 126720, 101376, 59136, 25344, 7920, 1760, 264, 24, 1

8192, 53248, 159744, 292864, 366080, 329472, 219648, 109824, 41184, 11440, 2288, 312, 26, 1

lásuk m=4 esetén!

1

3, 1

9, 6, 1

27, 27, 9, 1

81, 108, 54, 12, 1

243, 405, 270, 90, 15, 1

729, 1458, 1215, 540, 135, 18, 1

2187, 5103, 5103, 2835, 945, 189, 21, 1

Maple kóddal:

** :a hatvány jele.

for i from 0 to 13 do seq(binomial(i, j)*3**(i-j), j = 0 .. i) od;#

3**(i-j) > itt a 3 egyenlő m=4 minusz egy, etc...

Előzmény: [2652] Sirpi, 2008-05-19 10:47:20
[2652] Sirpi2008-05-19 10:47:20

A rendes 13-as totón a pontosan k találat darabszáma:

\binom {13}k \cdot 2^{13-k}

Hiszen kiválasztjuk azt a k meccset, amit eltalálunk, azok kitöltése egyértelmű, a többinél pedig mindenhol 2 lehetőségünk van, hogy oda rosszat írjunk. Ha fix meccsek is vannak, akkor a képletben mindkét 13-ast cseréld ki tetszőleges kisebb számra (mondjuk az nem teljesen világos, hogy a fix találatokat miért nem számolod a találatok közé, mert azt írod, hogy 12-ből maximum 12 találatod lehet, de mivel így szeretnéd értelmezni, ennek megfelelően adtam meg a képletet).

Előzmény: [2651] Lajosz, 2008-05-19 10:40:06
[2651] Lajosz2008-05-19 10:40:06

Ismétléses variáció:

A totón, ha minden esetet megjátszunk, (3 a 13-on ), mennyi 0, 1, 2,...11, 12, 13. találatunk lesz, hogyan kell kiszámítani?

Ugyanezt hogyan számítjuk, ha 1 fix mérkőzés mellett (3 a 12-en) eredményt megjátszunk, mennyi 0, 1, 2,...11, 12. találatunk lesz?

etc...

[2650] Róbert Gida2008-05-16 12:57:13

Ez lényegében meg Lajos eredeti konstrukciója, csak tekergetések nélül megoldva, de az is 2/3-os megvalósítás.

Előzmény: [2649] Sirpi, 2008-05-16 01:37:44
[2648] Sirpi2008-05-16 02:27:20

És hogy ez miért optimális:

A közlekedőutat tekintsük egy gráfnak (a csúcsok az üres mezők, az élek az élszomszédos mezőket kötik össze). Erről a gráfról kell belátni, hogy ha nem is mindig összefüggő, de néhány autó átpakolásával mindig azzá tehető. Hiszen ha van út, ami nincs összeköttetésben a bal felső sarokkal (az ábrán a sárga tartomány), akkor az annyit jelent, hogy egy vagy több autó blokkolja az utat a bal felső sarokig. Vegyünk egy ilyen autót (piros), és toljunk rajta egyet, rá a belső útra (kék helyzet). Az autó az új helyzetében nem blokkolhat másik autót, hiszen az autók hiába hajtanak a belső útra, onnan nem tudnak kijutni, csak ha az eredeti helyükre visszamennek, tehát a kék mező érintése nélkül is ki tudnak jutni, ha eddig ki tudtak. A kék autó pedig szintén kijut (egyet előremegy, és onnan már a feltételezésünk szerint kijut). Ezzel a tolással a belső út hossza 1-gyel csökkent, így ilyen lépések véges sorozatával felszámolható az összes belső út (jelen esetben a kék autót még 1-gyel lejjebb tolva a belső út összekapcsolódik a "fő" úthálózattal, vagyis több lépésre nincs is szükség).

Így a továbbiakban feltehető, hogy a közlekedőutak hálózata összefüggő, álljon k mezőből. Ekkor legalább k-1 belső kapcsolódása van (az összefüggő gráfnak legalább k-1 éle van). Minden belső kapcsolódás 2-vel csökkenti a közlekedőhálózat kerületét, tehát az összkerület legfeljebb 4k-2(k-1)=2k+2. Minden él a kerületen egy autónak ad lehetőséget, hogy felhajtson az úthálózatra, és így eljusson a bal felső sarokba (egy autó több élen át is megteheti ezt). Sőt, a bal felső mező két sarokéle nem segít egy autónak sem, vagyis legfeljebb 2k autó lehetséges k mezőből álló úthálózat esetén. Tehát a mezők számának legfeljebb 2/3-án lehetnek autók, és ez az arány aszimptotikusan (az előző hsz. ábrája alapján) el is érhető.

Megj.: Sőt, az út "meglátogatja" a másik 3 sarkot is, hiszen egy sarok és két szomszédja közül nem állhat mind a 3-on autó, vagyis k mezőből álló úthálózat esetén legfeljebb 2k-3 autó lehetséges (hiszen minden határélnél vesztünk egy autót) - feltéve, hogy a parkoló mindkét oldalának hossza legalább 4, mert ilyenkor a sarkokkal szomszédos mezők nem eshetnek egybe.

Előzmény: [2649] Sirpi, 2008-05-16 01:37:44
[2649] Sirpi2008-05-16 01:37:44

Ez a konstrukció pedig 2/3-os (66,67%) határértéket ad, ráadásul elég egyszerű is, nem kell mozaikba pakolni (bár épp azt is lehet).

Előzmény: [2647] Sirpi, 2008-05-16 01:18:30
[2647] Sirpi2008-05-16 01:18:30

Nem kell azt az egy autót se kitörölni, kis átszervezéssel elérhető a 28/49\approx57,143%. Viszont 6×6-asra tudtam egy kicsit jobbat is csinálni, csak a bal felső (pirosra festett) autót kell kiszedni. De egyetlen autó kivétele nem befolyásolja a határértéket, ami jelen esetben 21/36\approx58,333%.

Ja, és a határszám megtalálásához nem kell feltétlenül négyzet alakú területeket használni, ha esetleg egy téglalap jobb eredményt ad.

Előzmény: [2646] Róbert Gida, 2008-05-15 23:35:28
[2646] Róbert Gida2008-05-15 23:35:28

Szerintem nem adható rá explicit képlet tetszőleges n-re. Programozási versenyen volt egy hasonló példa axb-es téglalapra, de úgy, hogy alul és felül is ki lehet jutni, gyakorlatilag végignézték az összes esetet a megoldásoknál.

Ha az első ábrában a hatodik sor első pozicióján nem autó van, és ilyen 7x7-es blokkokat rakunk egymásra, akkor tetszőleges autó fel tud jutni a legfelső sorba. Ha a nagy négyzet felső sorából töröljük az autókat, így már mindenki kijut, ez (7k)x(7k)-asra müködik, ha n nem ilyen alakú, akkor legyen k=floor(n/7). Az autók száma aszimptotikusan \frac{28-1}{49}n^2=\frac{27}{49}n^2.

Felső becslés pedig: egy autónak van van legalább egy nem autó szomszédja, hogy esélye legyen kijutni (kivéve, ha n=1 és 1 autó van az ábrán), továbbá egy nem autó hely maximum 3 autónak lehet szomszédja, ami kijutásra használja, ellenben minden szomszéd autó, de akkor nem tudna kijutni, ha odamenne. Így #autó<=3*#nemautó, azaz

#auto<=3*(n2-#auto), innen \frac{#auto}{n^2}\leq \frac 34 teljesül, ha n>1.

Előzmény: [2643] Lóczi Lajos, 2008-05-15 21:51:46
[2645] Sirpi2008-05-15 22:39:14

Szerintem ezt a négyzetfelosztást mindig meg lehet csinálni akkor is, ha a két kis négyzet (egész) oldalhosszát előírjuk (a és b). Hiszen ekkor egy ab(a2+b2) oldalhosszú négyzet biztos kitölthető, méghozzá úgy, hogy a felső részében vannak az a oldalhosszú kis négyzetek (b(a2+b2a db.), alatta pedig a b oldalúak (a(a2+b2b db.). Sőt, gyakran kevesebb is elég lehet, pl. ha a és b nem relatív prím. Viszont azt nem tudom, hogy ennél kevésbé rendezett megoldások is vannak-e kisebb elemszámmal.

Előzmény: [2643] Lóczi Lajos, 2008-05-15 21:51:46
[2644] jonas2008-05-15 22:23:31

A négyzetes nem nehéz.

Egyszerűen választunk egy (s,a,x) számhármast, amelyre 1<s,x és 0<x<a2, és a2-x=s2x. Ezután egy nagy négyzetet felosztunk a2 közepes négyzetre, majd x darab közepes négyzetet egyenként s2 darab kis négyzetre.

Több megfelelő számhármas is van, az ábra a (2,5,5)-nek megfelelő megoldást mutatja, de jó például a (2,10,20),(3,10,10),(7,10,2),(2,15,45),(4,17,17),(2,20,80),(3,20,40),... is.

Ha 4s2\lex, akkor megtehetjük azt is, hogy egy (vagu több) közepes négyzetet kis négyzetek közé fáziseltolással csempészünk be, ahogy a második ábra mutatja.

Előzmény: [2643] Lóczi Lajos, 2008-05-15 21:51:46

  [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]    [162]    [163]    [164]    [165]    [166]    [167]    [168]    [169]    [170]    [171]    [172]    [173]    [174]    [175]    [176]    [177]    [178]    [179]    [180]    [181]    [182]    [183]    [184]    [185]    [186]    [187]    [188]    [189]    [190]    [191]    [192]    [193]    [194]    [195]    [196]    [197]    [198]    [199]    [200]    [201]    [202]    [203]    [204]    [205]    [206]    [207]    [208]    [209]    [210]    [211]    [212]    [213]    [214]    [215]    [216]    [217]    [218]    [219]    [220]    [221]    [222]    [223]    [224]    [225]    [226]    [227]    [228]    [229]    [230]    [231]    [232]    [233]    [234]    [235]    [236]    [237]    [238]    [239]    [240]    [241]    [242]    [243]    [244]    [245]    [246]    [247]    [248]    [249]    [250]    [251]    [252]    [253]    [254]    [255]    [256]    [257]    [258]    [259]    [260]    [261]    [262]    [263]    [264]    [265]    [266]    [267]    [268]    [269]    [270]    [271]    [272]    [273]    [274]    [275]    [276]    [277]    [278]    [279]    [280]    [281]    [282]    [283]    [284]    [285]    [286]    [287]    [288]    [289]    [290]    [291]    [292]    [293]    [294]    [295]    [296]    [297]    [298]    [299]    [300]    [301]    [302]    [303]    [304]    [305]    [306]    [307]    [308]    [309]    [310]    [311]    [312]    [313]    [314]    [315]    [316]    [317]    [318]    [319]    [320]    [321]    [322]    [323]    [324]    [325]    [326]    [327]    [328]    [329]    [330]    [331]    [332]    [333]    [334]    [335]    [336]    [337]    [338]    [339]    [340]    [341]    [342]    [343]    [344]    [345]    [346]    [347]    [348]    [349]    [350]    [351]    [352]    [353]    [354]    [355]    [356]    [357]    [358]    [359]    [360]    [361]    [362]    [363]    [364]    [365]    [366]    [367]    [368]    [369]    [370]    [371]    [372]    [373]    [374]    [375]    [376]    [377]    [378]    [379]    [380]    [381]    [382]    [383]    [384]    [385]    [386]    [387]    [388]    [389]    [390]    [391]    [392]    [393]    [394]    [395]    [396]    [397]    [398]    [399]    [400]    [401]    [402]