Il problema (il cui testo integrale sta qui http://olympiads.kz/ioi2015/day1/scales/it-IT.ITA.pdf) recitava più o meno così.
Hai 6 monete di pesi distini e incogniti e le vuoi ordinare; hai a disposizione una bilancia che supporta le seguenti operazioni:
- date 3 monete $A,B,C$ ti dice la più pesante
- date 3 monete $A,B,C$ ti dice la più leggera
- date 3 monete $A,B,C$ ti dice quella mediana (nè la più pesante, nè la più leggera)
- date 4 monete $A,B,C,D$ considera solo le monete più pesanti di $D$; se ce ne sono, ti dice qual è la più leggera di queste; altrimenti, ti dice la più leggera in assoluto
Il punteggio veniva assegnato in base a quante operazioni il programma faceva, rispetto a un misterioso $Q$, che era il numero di operazioni che una soluzione ottimale doveva fare nel peggiore dei casi (o, in altre parole, $Q$ è il più grande numero tale che esiste un insieme di quattro monete il cui ordinamento non è determinabile con $Q-1$ operazioni).
E ora vi chiedo: riuscite a indovinare quanto vale $Q$? E a dimostrarlo? Riuscite a trovare una strategia che usi al più $Q$ operazioni?
Nota: delle tre domande, io posso rispondere sì solo alla prima
^^. Posto qui questo problema perchè sono curioso di vedere cosa si riesca a dire dal punto di vista logico/matematico su un problema che avrebbe dovuto essere di informatica.