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.
[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
[2643] Lóczi Lajos2008-05-15 21:51:46

Hát akkor tűzzük ki :) Az is érdekes kérdés, hogy határértékben mi a fekete/fehér kockák aránya, az optimális esetben, ha a négyzetrács mérete végtelenhez tart. Amúgy ezt a feladatot idén adták fel orosz 6.-osoknak, egy olimpiai előkészítőn. A közölt megoldás is 28-at ad meg (egyébként Python ábráján a jobb szélsőt), persze nem bizonyítja az optimalitást. (A feladat pontozása érdekes: aki 25 autót rak be, 1 pontot kap, ezen felül viszont minden újabb autó plusz 2 pontot ér :-)

A másik, hasonlóan érdekes feladat: osszunk fel egy négyzetet kétféle méretű négyzetre, úgy, hogy a két fajtából egyforma számú darab szerepel. Kíváncsi vagyok, hogy van-e lényegében másfajta elrendezés, mint amit közöltek.

(A többi 4 feladat triviális volt ezekhez képest.)

Előzmény: [2642] Python, 2008-05-15 19:55:25
[2642] Python2008-05-15 19:55:25

A 28 nálam is megvan és szerintem nincs ennél jobb, mivel elég sokat szórakoztam, és 28-at többfélét találtam, de annál jobbat nem (3 példányt felteszek ábrában). Érdekes lenne a feladatot általánosabban is kitűzn, tehát n×n-es parkolóra.

Előzmény: [2640] Káli gúla, 2008-05-15 14:50:44
[2641] Róbert Gida2008-05-15 16:48:03

Jók a számok. Lehet találni egy formulát, ami ilyen számokat állít elő, feltéve, hogy néhány szám prím a formulában. Ez hasonló a Carmichael számokat gyártó képlethez, ami persze nem véletlen, hiszen ahogy írtad ezek mind azok. Ha egy ikerprím sejtéshez hasonló sejtés igaz, akkor máris végtelen sok ilyen szám van.

Előzmény: [2638] Enkidu, 2008-05-15 12:41:43
[2640] Káli gúla2008-05-15 14:50:44

1-et tudtam javítani (27 -> 28), nem tudom, lehet-e jobbat csinálni.

Előzmény: [2639] Sirpi, 2008-05-15 13:06:23
[2639] Sirpi2008-05-15 13:06:23

A példaábrához képest (ami elsőre optimálisnak tűnt számomra) 3-at tudtam javítani (24 -> 27), nem tudom, lehet-e jobbat csinálni.

Előzmény: [2637] Lóczi Lajos, 2008-05-13 12:14:17

  [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]