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"
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.↩
La notazione
1(6)
sta per “il primo posto della sesta gara”. La notazione2(=1(6))
sta per “il secondo posto della gara dove1(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.