domenica 28 gennaio 2018

Venticinque cavalli

Il quesito richiede di determinare il minimo numero di corse necessarie per stabilire quali sono, tra i 25 cavalli in gara, i tre più veloci, con il vincolo che ogni corsa non può far gareggiare più di cinque cavalli.

(Quesito udito per caso dalla “sala break”.)

Ho sentito anche la soluzione, che è 7.

Credo che non sia banale dimostrare formalmente che questo è davvero il numero minimo; sarebbe interessante farlo e procedere poi con una generalizzazione (dati N cavalli che possono correre solo M alla volta, trovare il numero minimo di corse per determinare i primi L1).

Prendiamo per buono il fatto che la ricerca della soluzione valga anche come dimostrazione: basta verificare che alla sesta corsa ancora non è possibile essere sicuri dei cavalli che occupano il podio.

Le prime sei corse sono facili: facciamo gareggiare tutti i cavalli a gruppi di cinque e infine nella sesta corsa facciamo gareggiare i primi arrivati di ciascuna delle precedenti cinque corse. Il primo della sesta corsa è il cavallo più veloce (sui 25).

Si vede facilmente: in qualunque corsa gareggi, il primo cavallo (sui 25) sarà per forza di cose il primo (sui 5). Gli altri primi (sui 5) nelle altre quattro corse potranno essere al massimo i secondi o i terzi (sui 25), o peggio.

Questo significa che nella sesta corsa il secondo e terzo posto potrebbero essere occupati dal secondo e dal terzo (sui 25), e per saperlo dobbiamo metterli nella settima gara.

Tra gli altri sfidanti della settima corsa non consideriamo gli ultimi e i penultimi delle varie gare: chiaramente il secondo e terzo posto (sui 25) non possono trovarsi al quarto o quinto in nessuna gara da cinque: essendo i più veloci (dopo il primo), si troveranno sempre in una delle prime tre posizioni: il terzo (sui 25) sarà primo (sui 5) se nella sua gara non ci sono né il primo né il secondo (sui 5), sarà secondo (sui 5) se nella sua gara è capitato il secondo (sui 25), ecc.

Schematizzando le possibilità:

    Prime 5 corse         Sesta corsa
    -------------         -----------
 A  1 2 3 * *             1 * * * *
    …
 B  1 2 * * *             1 3 * * *
    3 * * * *
    …
 C  1 3 * * *             1 2 * * *
    2 * * * *
    …
 D  1 * * * *             1 2 * * *
    2 3 * * *
    …
 E  1 * * * *             1 2 3 * *
    2 * * * *
    3 * * * *

Come avevamo già detto, nella sesta gara siamo in grado di capire chi è il primo (dei 25). Si vede anche che l'ultimo e penultimo posto non ci interessano mai; il terzo ci interessa solo in un caso (quando nella stessa gara capitano tutti e tre).

Dallo schema si vede che dobbiamo per forza far gareggiare il 2 e il 3 della gara in cui 1(6)2 (che è anche il primo sui 25) è risultato primo, per tenere conto del caso (A), cioè della possibilità che in una singola gara siano capitati tutti e tre i campioni insieme.

    Settima corsa
    -------------
    2(6) 3(6) 2(=1(6)) 3(=1(6)) ????

Rimane quindi solo un posto per la settima corsa. Choose carefully.

Si vede che il caso D non è coperto perché il secondo classificato nella gara in cui il 2 (sui 25) è primo non lo abbiamo nella settima gara… Risolviamo subito:

    Settima corsa
    -------------
    2(6) 3(6) 2(=1(6)) 3(=1(6)) 2(=2(6))

Il primo e secondo classificato della settima corsa sono rispettivamente il secondo e terzo posto del podio globale.

Con sei corse non potevamo ancora determinare l'ordine globale corretto; con sette abbiamo ottenuto tale ordine; perciò in un certo senso abbiamo dimostrato che 7 è il numero minimo di corse necessarie.

Tanto per gradire, qualche riga di Ruby che esemplifica le corse e la procedura di selezione dei concorrenti della sesta e settima corsa. (Le prime cinque sono “ovvie” e sono fatte in una botta sola nella prima riga di codice.)

  a = [*1..25].shuffle.each_slice(5).to_a.map(&:sort)
  
  c6 = [a[0][0], a[1][0], a[2][0], a[3][0], a[4][0]].sort

  # trova la corsa dove è arrivato primo c6[0], il primo/25
  w1 = a.select{|x| x.include?(c6[0])}[0]
  
  # nel caso D, trova la corsa dove è arrivato primo c6[1];
  # negli altri casi il 3 è già presente tra c6[1], c6[2],
  # w1[1], w1[2]; perciò questo dà un cavallo spurio, come
  # del resto lo sono w1[1] e w1[2] nei casi D ed E...
  w2 = a.select{|x| x.include?(c6[1])}[0]

  c7 = [c6[1], c6[2], w1[1], w1[2], w2[1]].sort

  print c6[0], " ", c7[0], " ", c7[1], "\n"

  1. Una formulazione diversa (da rivedere): dati N numeri e un algoritmo di ordinamento che può essere usato solo su M numeri alla volta, stabilire il numero minimo di passi necessari per garantire che siano ordinati correttamente almeno i primi L.

  2. La notazione 1(6) sta per “il primo posto della sesta gara”. La notazione 2(=1(6)) sta per “il secondo posto della gara dove 1(6) è arrivato primo”.

Nessun commento:

Posta un commento

Sii educato, costruisci con cura le frasi, rifletti prima di pubblicare, evita parolacce e offese dirette, non uscire dal tema, cerca di non omettere la punteggiatura, evita errori ortografici, rileggi quel che hai scritto.