Tävlingsprogrammering/Uppgifter/Hoppleken

Hoppleken

Barnen i Bullerbyn gillar att leka lekar. Deras favoritlek är hoppleken som går till så här: Man ritar upp en 1-dimensionell bana med N st rutor. Det är ett känt antal barn B som leker. Antalet barn får inte vara fler än antalet rutor. Det börjar med att barnen fördelar sig slumpmässigt över rutorna (de får inte ställa sig på samma ruta). Sedan börjar hoppandet. Vid varje hopp kommer samtliga barn att hoppa ett skutt till en ruta bredvid sin egen ruta (de får ej stå stilla). Om några barn hamnar på samma ruta är dessa ute ur leken och lämnar banan. Efter varje hopp kommer man också att ta bort rutan längst till höger så att banan minskar i storlek. Barnen hoppar aldrig utanför banan eller till den ruta som kommer tas bort efter hoppet, men i övrigt hoppar de slumpmässigt åt ena eller andra hållet. Leken är slut efter N − 2 hopp, då endast två rutor återstår. De barn som eventuellt då finns kvar i leken vinner. Det kan alltså finnas 0, 1 eller 2 vinnare.

Britta som är överintelligent för sin ålder tycker leken är fånig och vill inte vara med. Hon bestämmer sig istället för att räkna ut det genomsnittliga vinnarantalet. Givet antalet rutor och antalet deltagare, hjälp Britta att besvara hur många vinnare som kommer att finnas i genomsnitt. Tänk på att barnen från början kan ställa sig på alla möjliga sätt.

Programmet ska fråga efter antalet rutor N, samt antalet barn B, där 3≤N≤20 och 2≤B≤N. Programmet ska skriva ut det genomsnittliga antalet vinnare, alltså ett flyttal. Svaret ska anges med minst 4 decimaler.

Körningsexempel 1:

Antal rutor ? 7
Antal barn ? 4

Svar: 0.91429

Körningsexempel 2:

Antal rutor ? 4
Antal barn ? 2

Svar: 1.33333

Lösning

Den här uppgiften föll utanför mönstret för PO-uppgifter genom att den kräver visst matematikbevis-tänkande men sedan är mycket lättare än den verkar. Dessutom innehåller den mer information än man egentligen behöver (det spelar ingen roll att de hoppar slumpmässigt). Vi har fått många kommentarer om att det därför var en dålig programmeringsuppgift. Men faktum är att denna typ av uppgift är ganska vanlig på de internationella tävlingarna, och vi ville ta med en sådan i kvalet för att visa att det ibland är bättre att tänka mer och koda mindre.

Nyckeln är att inse att, givet en utgångsposition, slutpositionen är entydigt bestämd, alltså oberoende av hur barnen hoppar (inte undra på att Britta i Norrgården tyckte det var fånigt). För att inse detta kan det underlätta att färga rutorna, varannan vit och varannan svart. Leken slutar alltså när det är en vit och en svart ruta kvar. I varje hoppomgång byter varje barn från en svart till en vit ruta eller tvärtom, så man kan dela upp barnen i två grupper, med B_v respektive B_s barn, beroende på deras färg på utgångsrutan. Barn från olika grupper kommer aldrig att hamna på samma ruta och grupperna kan därför hanteras separat. Vidare vet vi att barnen försvinner i par (när de krockar) och dessutom att det endast kan finnas 0 eller 1 barn i varje grupp kvar på slutet, eftersom det bara finns en ruta av varje färg. Om antalet barn i en grupp är udda måste alltså ett av dem bli kvar på slutet medan om antalet är jämnt måste alla försvinna. Sålunda finns det totalt (B_v mod 2) + (B_s mod 2) vinnare i leken.

Här kan man fortsätta och göra en helt matematisk lösning, men vi har faktiskt råd att generera alla utgångsställningar (max 184756 stycken) och helt enkelt räkna ut B_v och B_s för varje ställning. Genereringen av ställningar kan t.ex. göras med en rekursiv funktion som, för ett givet antal utplacerade barn, testar att sätta nästa barn på någon av de kvarvarande rutorna och sedan rekurserar (se lösningen nedan).

#include <stdio.h>

int N,B,nconf,sum;

void MLX(int nr, int now, int odd, int even) {
  int p;
  if(nr==B) {
    nconf++;
    sum+=(odd%2)+(even%2);
  }
  else 
   for(p=now;p+(B-nr)<=N;p++) 
      MLX(nr+1,p+1,odd+(p%2),even+((p+1)%2));
}
    
int main() {
  printf("Antal rutor ? ");
  scanf("%d", &N);
  printf("Antal barn ? ");
  scanf("%d", &B);
  nconf=sum=0;
  MLX(0,0,0,0);
  printf("Svar: %f\n", (double)sum/(double)nconf);
  return 0;
}

Är man snäppet coolare än alla andra på skolan, så kör man Haskell.

-- Hoppleken
module Main where
import IO

main = do {
	putStr "Antalet rutor ? ";
	rutor <- getLine;
	n <- return $ read rutor;
	
	putStr "Antalet barn ? ";
	barn <- getLine;
	b <- return $ read barn;
	
	putStrLn $ "Svar: " ++ (show $ (fromIntegral $ jump n b 0 0 0) / (fromIntegral $ product [n-b+1..n] `div` product [1..b]))
}

jump n b od ev i = if b==0 then mod od 2 + mod ev 2 else sum $ map (\x -> jump n (b-1) (od + mod x 2) (ev + mod (x+1) 2) (x+1)) [i..n-b]

Matematisk Lösning

Vill man lösa uppgiften matematiskt kan man göra såhär. Dela upp rutorna i vita och svarta. Låt de vita rutorna vara de med jämnt index (0,2,4..) och de svarta rutorna de med udda index (1,3,5..). Antalet barn kvar i slutändan är som tidigare nämnt "antalet barn i de vita rutorna" mod 2 + "antalet barn i de svarta rutorna" mod 2.

Givet att vi har B barn, V vita rutor och S svarta rutor. Då är frågan, på hur många sätt kan jag placera 0 barn i de vita rutorna och B barn i de svarta rutorna, samt 1 barn i de vita rutorna och B-1 barn i de svarta rutorna, etc. Svaret fås genom Binomialkoefficienten vilken kan besvara frågor som "på hur många sätt kan jag välja k element bland n".

Antalet sätt jag kan placera 3 barn i de vita rutorna (förutsatt att V≥3) och B-3 barn i de svarta rutorna (förutsatt att S≥B-3) på blir således:

${V \choose 3}\cdot {S \choose B-3}$

Och antalet barn som kommer att bli kvar med denna uppsättning är 3 mod 2 + (B-3) mod 2. Således blir antalet barn som kommer att bli kvar totalt givet uppställningen 3 barn i vita rutor och B-3 barn i svarta rutor:

${V \choose 3}\cdot {S \choose B-3}\cdot (3\mod 2+(B-3)\mod 2)$

Detta kan givetvis göras analogt för varje antal K barn i vita där K≤V och B-K≤S. Vi får således följande formel för det totala antalet barn som kommer att bli kvar:

$\sum _{k=B-min(S,B)}^{min(V,B)}{V \choose k}\cdot {S \choose B-k}\cdot (k\mod 2+(B-k)\mod 2)$

B - min(S,B) är det minsta antalet barn vi kan placera i de vita rutorna, medan min(V,B) är det största antalet barn vi kan placera i de vita rutorna.

Svaret blir då ovanstående summa delat på antalet sätt man kan placera B barn på N rutor, d.v.s:

${\frac {\sum _{k=B-min(S,B)}^{min(V,B)}{V \choose k}\cdot {S \choose B-k}\cdot (k\mod 2+(B-k)\mod 2)}{N \choose B}}$

(Någon kan nu anmärka på att vi i vårt resonemang inte tagit hänsyn till att barnen faktiskt är unika och har olika namn. Vårt resonemang tar inte hänsyn till om det är Bosse eller Olle som står på ruta 1, utan bara att det är ett barn som faktiskt står där. Men faktum är att det inte spelar någon roll, eftersom det kommer att påverka antalet ställningar man kan börja på och antalet barn som blir kvar med samma faktor (vilken är $B!$), och kvoten blir således densamma.)

En lösning i Haskell kan se ut såhär.

-- Hoppleken
module Main where
import Control.Monad

main = putStr "Antalet rutor ? " >>
	fmap read getLine >>= \n ->
	
	putStr "Antalet barn ? " >>
	fmap read getLine >>= \b ->
	
	let v = div n 2 + mod n 2 in
	let s = div n 2 in
	let nr = sum [bin v k * bin s (b-k) * (mod k 2 + mod (b-k) 2) | k <- [b - min s b..min v b]] in
	
	putStrLn.("Svar: " ++).show $ fromIntegral nr / (fromIntegral $ bin n b)

bin n k = product [n-k+1..n] `div` product [1..k]