Matte 5 Lucky Luke, grafteori?
Skulle verkligen behöv hjälp med att lösa följande problem:
Joe Dalton har rånat banken i Tombstone, men Lucky Luke är honom hack i häl. För att undkomma beger sig Joe till ett grottsystem där han tror att han kan gömma sig och till slut trötta ut Lucky Luke. Grottsystemet består av 16 separata grottor i en rad. Joe hinner precis gömma sig i en grotta innan Lucky Luke kommer fram. För att hitta Joe börjar Lucky Luke leta i grottorna samtidigt som Joe flyttar sig för att undkomma. Följande gäller:
Varje dag letar Lucky Luke igenom en (vilken som helst) av de 16 grottorna. Om Joe är där är han fångad.
På natten vågar inte Lucky Luke leta utan han slår läger utanför. Samtidigt flyttar Joe en grotta i sidled, han är aldrig kvar i samma!
Nästa dag letar Lucky Luke igenom en grotta (vilken som helst). På natten flyttar Joe som ovan. Så håller det på tills Joe är fångad.
Hur ska Lucky Luke bete sig för att säkert fånga Joe, och hur många dagar kommer det att ta som mest?
Hur har du börjat?
Hej! Vi funderar på om det har något med grafteori att göra ev kombinatorik. Har tänkt att om Joe gömmer sig i X grotta första dagen måste han ju vara i X+1 eller X-1 nästa dag. Vet ju även att om han är på en "udda" grotta så kommer han att vara på en "jämn" grotta dagen efter.
Om vi tar ett mindre grottsystem, t.ex. fyra stycken. Dalton gömmer sig i grotta 3 (kan vi säga) och Lucky Luke kollar grotta 1. Vad händer sen?
Mejmej skrev:Hej! Vi funderar på om det har något med grafteori att göra ev kombinatorik. Har tänkt att om Joe gömmer sig i X grotta första dagen måste han ju vara i X+1 eller X-1 nästa dag. Vet ju även att om han är på en "udda" grotta så kommer han att vara på en "jämn" grotta dagen efter.
Om vi låtsas om att vi vet att Joe gömmer sig i en udda grotta första dagen; kan du då tänka ut en taktik som garanterar fångst av honom?
Hmm då tänker vi att det räcker med att Luke kollar grotta för grotta alltså grotta 2 dag 2, grotta 3 dag 3 osv och då kommer Dalton att åka fast, det är oundvikligt. Men om Dalton däremot börjar på ett jämnt tal, säg att han börjar i grotta 2, då kommer inte Luke kunna ta fast honom genom att gå grotta för grotta. Men när han väl inser det då även grotta 4 är tom kan han förutse att Dalton måste gömma sig i en jämn grotta dag 5 och om Luke då börjar i grotta 4 och jobbar sig tillbaka till grotta 1 kommer han att ta fast honom. Stämmer det?
Ja så om Luke skulle veta att Joe gömmer sig i en udda grotta första dagen behöver han bara börja leta i en udda grotta och därefter kolla alla grottor successivt för det garanterar att han "pushar" Joe framför sig, Joe kan inte gå förbi honom om de båda startar på en udda grotta!
Detta är en taktik som bör fånga honom, ja.
Sedan kan man göra en del mindre optimeringar; förutsätter vi att han startade i en udda grotta så kan man börja i grotta nummer 15, sedan 14, 13 osv. på samma sätt som du har beskrivit fast från andra hållet, fast med fördelen att man slipper söka igenom grotta 16. Om antagandet var fel så är det ändå en grotta mindre som man aldrig behövde söka igenom. Sedan är det då man når grotta nummer 2 som man logiskt inser att det ursprungliga antagandet om start i udda grotta var felaktigt, och man kan börja om genom att söka igenom grotta nummer 2 dagen därpå igen innan man går till grotta 3, grotta 4 osv. På det viset borde det i värsta fall bli 28 dagars letande, eftersom då man väl letar i grotta nummer 15 igen befinner han sig garanterat i en udda grotta varför grotta nummer 16 aldrig behövs sökas igenom.
Det kanske finns en bättre taktik.
Edit: Hoppsan, jag trodde att du svarade på både mitt och Lagunas inlägg i ett svep.
Ja tack så mycket för hjälpen! Om någon annan kommer på en bättre lösning så posta det gärna. Även förslag på hur jag kan presentera detta matematiskt skulle uppskattas, för egentligen har jag ju bara prövat och resonerat
Undrar om 28 gånger räcker.
