Леший Posted April 23, 2015 Report Share Posted April 23, 2015 Nu ja jau aizgaja mode uz uzdevumiem, tad viens no manis. Ir atrodams internetos, bet labāk tomēr padomājiet paši. Risinājumus kā vienmēr publicējam zem spoiler tegiem. Tu atrodies cietumā, vienā kamerā ar savu draugu. Tad tevi aizved uz citu istabu, kur ir sargs un šaha dēlis. Sargs saliek uz dēļa 64 vienādas monētas random veidā, dažās ar aversu uz augšu, dažās ar reversu (var būt arī visas ar aversu vai otrādi). Pēc tam sargs parāda uz monētu A (randomā). Tad tev ir iespēja apgriezt otrādi tikai vienu monētu (jebkuru, var to pašu A monētu, var arī neapgriezt nevienu). Tad tev ir jāiet trešajā istabā, bet tavu draugu ielaiž otrajā istabā, un viņam ir jāatrod monētu A. Pirms tas viss notiks, jūs abi zināt, kāds būs uzdevums, tāpēc pirms tevi ielaiž istabā ar monētām, jums ar draugu ir iespēja izdomāt stratēģiju. Uzdevums ir atrast tādu stratēģiju. Uzdevumam ir 100% risinājums, bet es to nezinu. Nebija laika pieķerties šim uzdevumam, bet plānoju to izdarīt tuvākajā laikā. Quote Link to comment Share on other sites More sharing options...
jurchiks Posted April 23, 2015 Report Share Posted April 23, 2015 Nu kā, ja abi zin, kāds būs uzdevums, tad vienkārši sarunā, ka apgriezīs monētu kreisajā apakšējā stūrī no ieejas durvju puses skatoties, piemēram. Quote Link to comment Share on other sites More sharing options...
Kavacky Posted April 23, 2015 Report Share Posted April 23, 2015 Iemācies lasīt. Quote Link to comment Share on other sites More sharing options...
jurchiks Posted April 23, 2015 Report Share Posted April 23, 2015 (edited) >jūs abi zināt, kāds būs uzdevums Ko vēl tev vajag? Un kur ir tava atbilde? Edited April 23, 2015 by jurchiks Quote Link to comment Share on other sites More sharing options...
Леший Posted April 23, 2015 Author Report Share Posted April 23, 2015 (edited) Spešalli for jurchiks sargs parāda uz monētu A (randomā) Uzdevums nav triviāls, un risinājums nav viegli atrodams. Edited April 23, 2015 by Леший Quote Link to comment Share on other sites More sharing options...
jurchiks Posted April 23, 2015 Report Share Posted April 23, 2015 Ok, my bad. Quote Link to comment Share on other sites More sharing options...
codez Posted April 23, 2015 Report Share Posted April 23, 2015 (edited) Vispārējs risinājums: Sākuma sagrupējat visus 64 bitu skaitļus 64 grupās tā, lai katrā grupā ir skaitļi tā, lai samainot kādu no 63 bitiem, iegūst skaitli citā grupā. Izveidot no monētām 64 bitu skaitli. Tu no sarga uzliktā stāvokļa izrēķini šo 64 bitu skaitli, tad sargs parāda uz šo monētu. Tu izdomā, kuru bitu jāmaina, lai no sarga uzliktā 64 bitu skaitļa, iegūtu skaitli grupā, kurai atbilst monēta uz kuru sargs norādīja. Kad ienāk tavs draugs, viņš nosaka jauno 64 bitu skaitli un pēc grupas, kurai šis skaitlis pieder, nosaka, kuru monētu sargs norādīja. Pilnīgam risinājumam jāizdomā, kā vienkārši sagrupēt visus šos 64 bitu skaitļus 64 grupās. Ā, izdomāju. Paņem katram bitam ar vērtību "1" kārtas numurus un sasummē tos, piemēram, skaitlis 10011 dos 5 + 2 + 1 =8 Tad izrēķini atlikumu dalot ar 64, iegūsi 0 - 63. Tad izmainot vienu no 64 bitiem var iegūt jebkuru atlikumu no 0 - 63. Šis atlikums arī norādīs uz monētu uz kuru sargs norādīja. Edit: Tomēr, šis sadalījums laikam nav pareizi. Šis nav pareiz, tāpēc, ka mainot x-to bitu no 0 uz 1, pie atlikuma iegūst +x, bet no 1 uz 0, 64-x, kas mums sliktākajā gadījumā, izmainot vienu bitu, garantē iegūt tikai 32 dažādus atlikumus. Jāpadomā vēl. Edited April 23, 2015 by codez Quote Link to comment Share on other sites More sharing options...
codez Posted April 23, 2015 Report Share Posted April 23, 2015 (edited) Šeit ir pāris risinājumi, kuri visi pēc būtības ir vienādi: http://datagenetics.com/blog/december12014/index.html http://www.libragold.com/blog/2014/03/communicating-information-through-randomness/ https://ocfnash.wordpress.com/2009/10/31/yet-another-prisoner-puzzle/ Edited April 23, 2015 by codez Quote Link to comment Share on other sites More sharing options...
Леший Posted April 23, 2015 Author Report Share Posted April 23, 2015 (edited) Nepietika pacietības vai kā? Būtu labi tos linkus arī zem spoiler iemest. Kam vajadzēs, saguglēs. Edited April 23, 2015 by Леший Quote Link to comment Share on other sites More sharing options...
codez Posted April 23, 2015 Report Share Posted April 23, 2015 Pietika, būtībā mans vispārīgais risinājums jau ir pareizs. Vienīgais, lai cilvēkam būtu saprotams, vajag izdomāt kā vienkārši sagrupēt tos 64 bitu skaitļus. Linkos jau arī ir kompleksa grupēšana ar xor-iem no xor-iem. Vispārīgā gadījumā var uzbūvēt pilnu grafu, kur virsotnes ir kombinācijas, bet šķautnes 1 bita pārveidojumi un sagrupēt. Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.