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.

[2483] jonas

2007-12-06 19:22:38

Lefuttattam rá egy kimerítő keresést. Nem volt nehéz, mivel csak 14 csúcs van, és minden csúcsból csak legfeljebb három irányba lehet továbbmenni.

Ha helyes a programom, akkor nincs benne Hamilton-út.

Ha megengedjük, hogy egy csúcsot kihagyjunk, akkor pl. a következő útvonal jó: ACHMNLKIJFGBD.

Előzmény: [2467] Csimby, 2007-12-04 01:26:25

[2482] jonas	2007-12-06 18:44:00
Ja értem, te is azt mondtad.
Előzmény: [2475] jonas, 2007-12-05 07:51:54

[2481] Csimby	2007-12-05 21:07:30
Köszi a megoldást. Amúgy 2004-es Péter Rózsa versenyfeladat tanárképző főiskolásoknak.
Előzmény: [2480] Enkidu, 2007-12-05 13:41:13

[2480] Enkidu

2007-12-05 13:41:13

A bizonyítás:

Nyolc ember között van olyan, aki legalább négy másikat elvert. Ő lesz a győztesünk. Vizsgáljuk azt a négy embert, akiket megvert. Ezen négyesben van olyan ember, aki a másik három ember közül kettőt elvert, ő lesz a "második". Az a két ember, akiket ez az utóbbi elvert eldöntik egymás között, ki a harmadik és a negyedik. Ezzel kész.

Ha hét emberre vizsgálnánk, akkor már nem feltétlenül teljesül; ha pl (megszámozva a versenyzőket) mindenki elveri a nála 1,2 és 4-gyel nagyobb sorszámút (modulo 7 gondolkozva - ennyi pontatlanság talán belefér:)), akkor az egy ellenpélda.

Előzmény: [2466] Csimby, 2007-12-04 01:19:45

[2479] Enkidu	2007-12-05 13:31:00
Egy ezzel a példával kapcsolatos aranyos (bár elég egyszerű) példa a következő: Sherlock Holmes ősi ellenfele Mortimer ellopta a Mona Lisát a párizsi Louvre-ból. Holmes éppen Péterváron volt és rögtön repülőre ült, hogy elkapja a gazfickót. (Európa repülőtereit a lenti ábra mutatja; egy lépésben csak egy szomszédos repülőtérre repülhetünk, azaz pl Pétervárról közvetlenül csak Moszkva, Vilnius és Stockholm érhető el.) Miután Holmes lépett egyet Mortimernek is lépnie kell (ha túl sokáig maradna egy helyen elkapnák a rendőrök). Vagyis a két játékos felváltva lép. Ha Holmesnak sikerül ugyanabba a városba repülnie, ahol éppen akkor Mortimer tartózkodik, akkor elkapja és vége a játéknak. Ha Mortimer 15 lépés után is szabad, végleg megmenekült. El lehet-e fogni Mortimert? Ha igen, hogyan?

Előzmény: [2468] rizsesz, 2007-12-04 08:45:58

[2478] HoA	2007-12-05 11:44:06
Igaz, a felismert tulajdonságból következik a páros oldalszám.
Előzmény: [2477] rizsesz, 2007-12-05 11:16:16

[2477] rizsesz	2007-12-05 11:16:16
Nem tudom, hogy arra a megoldásra jöttél-e rá, amire én is gondolok, de abban sokat segít a négyszög dolog. Háromszögekkel pl. nem működne. :)
Előzmény: [2476] HoA, 2007-12-05 11:11:43

[2476] HoA	2007-12-05 11:11:43
Nem is tudom, most örüljek-e, hogy sikerült rájönni egy megoldásra, amihez valóban elég egy 8 éves tudása. Az ebben a megoldásban felhasznált tulajdonság felismeréséhez nem a 10 négyszög léte, hanem az segít, ami hiányzik az ábráról :-)
Előzmény: [2474] rizsesz, 2007-12-04 14:05:10

[2475] jonas	2007-12-05 07:51:54
Hamilton-út (egy kicsit még nehezebb). Ez a gráf viszont elég kicsi ahhoz, hogy végig lehet nézni.
Előzmény: [2470] Hajba Károly, 2007-12-04 12:38:43

[2474] rizsesz	2007-12-04 14:05:10
Ez egy nagyon fontos észrevétel, hogy 10 darab négyszög jön létre. Egy ez alapján megsejthető tulajdonság következménye a megoldás.
Előzmény: [2473] Hajba Károly, 2007-12-04 14:01:11

Már regisztráltál?
Új vendég vagy?