IOI 2015/2

Esercizi sulla verità delle proposizioni e problemi che non sembrano rientrare in nessun'altra categoria.

IOI 2015/2

Messaggioda Delfad0r » 12/08/2015, 15:27

Ebbene sì!
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:
  1. date 3 monete $A,B,C$ ti dice la più pesante
  2. date 3 monete $A,B,C$ ti dice la più leggera
  3. date 3 monete $A,B,C$ ti dice quella mediana (nè la più pesante, nè la più leggera)
  4. 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
Ordinale con meno operazioni possibile.

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 :oops: ^^. 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.
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19

Torna a Logica e Matematizzazione

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite