Medan ni väntar på tomten

Paul Erdös (Foto: Wikipedia)

PAUL ERDÖS VAR en ungersk matematiker som föddes i Budapest 1913 och dog i  Warszawa 1996. Han var oerhört produktiv och levde ett bohemiskt och närmast bisarrt liv. Han publicerade omkring 1500 matematiska uppsatser (”papers”) under sitt liv och menade att matematik borde vara en social aktivitet.

En stor del av sitt liv levde han en kringflackande tillvaro med alla sina ägodelar i en resväska och en plastkasse. Han bjöd in sig att bo hos kolleger, var hyperaktiv och sov endast ett fåtal timmar per natt. Klockan fem på morgonen kunde han börja skramla med kaffekokaren och väcka sin kollegas familj med att han just kommit på något intressant som måste redas ut. Han sågs ibland flyga upp och vifta med armarna och ibland rusa rakt mot en vägg, men stanna plötsligt några centimeter framför den.

I hans språkbruk betydde E (epsilon) barn. Boss betydde hustru. Slav betydde make och SF betydde Supreme Fascist (d v s Gud).

Bokomslag

Han ställde upp många ”talproblem” som han inbjöd sina kollegor att hjälpa honom att lösa. Han må ha varit svår att umgås eller leva med, men matematiskt var han mycket ”social”, delade med sig av sitt arbete och inbjöd alla intresserade och kvalificerade att arbeta med honom. Flera biografier har skrivits. The Man Who Loved Only Numbers av Paul Hoffman är en. Och My Brain is Open: The Mathematical Journeys of Paul Erdös av Bruce Schechter är en annan.

Låt mig presentera ett av hans problem, ett”Ramseyproblem”. Frank Ramsey var en brittisk matematiker och ateist, som dog 26 år gammal. Hans bror Michael, däremot, blev ärkebiskop i Canterbury. Mera konkret kan vi kalla det ett ”party problem”.

I en grupp människor är det ju så att folk antingen känner varandra eller är varandra främmande. I följande problem antas det att om A känner B, så känner också B A. Att ”känna” någon är ömsesidigt. Frågan är: Hur stor måste en grupp (ett party) vara för att man kan vara säker på att finna minst tre personer som känner varandra eller tre personer som inte känner varandra? Börja med en grupp på tre personer. Det kan ju hända att alla tre känner varandra eller att ingen känner någon. Men det kan ju också hända att två av dem känner varandra och den tredje är en främling. En grupp på tre är alltså för liten. Samma sak med fyra. Låt dem bilda två par, där personerna känner varandra inbördes men inte känner någon i det andra paret. Då finns där alltså varken tre personer som känner varandra eller tre pers som inte känner varandra.

En grupp på fem  då? Ställ dem i en ring där var och en håller sina två grannar i hand. Tag fallet där varje person känner sina två grannar men ingen av de två övriga personerna. Men de två övriga håller ju hand och känner alltså varandra. Således kan man inte finna tre personer, där ingen känner de andra två. Samma sak med motsatsen. Varje person känner de två närmaste till höger och vänster, men dessa två känner ju inte varandra.

Vi går vidare och prövar med en grupp på sex personer. Bingo! Om man här inte kan hitta tre personer som känner varandra, så måste det finnas tre personer som inte känner varandra och vice versa. Denna sanning får ni själva övertyga er om.

Hur stor måste då en grupp vara för att man ska vara säker på att i denna grupp hitta fyra personer som alla känner varandra eller fyra pers där ingen känner de övriga tre? Svaret är 18, men fråga mig inte varför. Höj nu antalet till fem! Svaret ligger mellan 43 och 49. Så mycket hade man luskat ut för 20 år sedan. Antalet kombinationer av ”känner/känner inte” i så stora grupper är ett cirka 200-siffrigt tal. Sex personer? Svaret ligger (eller låg) mellan 102 och 165. Enligt Paul Erdös skulle världens datorer behöva hålla på att råräkna till domedagen för att få fram det exakta svaret.

Det roliga med problemet ovan är att det faktiskt är begripligt (men olöst!), inte bara för matematiker utan för var och en som anstränger sig lite.

... är läst 449 gånger!

Kommentera

Denna webbplats använder Akismet för att minska skräppost. Lär dig hur din kommentardata bearbetas.