OII 2002

1

Alcune interessanti scoperte genetiche sui moscerini:

  • i moscerini con una mutazione del gene X sono sempre albini;
  • i moscerini non albini non hanno alcuna mutazione del gene Y, oppure hanno una mutazione sia del gene Y che del gene Z.

Dite quale delle seguenti affermazioni e’ sicuramente vera:

  1. se un moscerino è albino, ha una mutazione del gene X;
  2. se un moscerino non ha una mutazione nè nel gene Y nè nel gene Z, allora è albino;
  3. se un moscerino ha una mutazione nel gene Y ma non nel gene Z, allora è albino;
  4. non esistono moscerini albini.

2

Aldo è più vecchio di Beatrice, ma hanno meno di due anni di differenza.
Inoltre, la somma dei quadrati delle loro età è minore di 100.
Sapendo che Beatrice ha più di cinque anni, quanti anni ha Aldo?

Nota Bene: assumiamo che l’età sia un numero intero; ad esempio, se una persona ha 13 anni 11 mesi e 12 giorni assumiamo che la sua età sia 13.

3

Nella città di Precisini valgono le seguenti regole:

  • non esistono due abitanti con lo stesso numero di capelli;
  • non esiste un abitante con 123456 capelli;
  • ci sono più abitanti di quanti capelli abbia un qualunque abitante.

Qual e’ il massimo numero abitanti di Precisini?

4

Anna deve inviare a Bruno un messaggio costituito da quattro bit, b1, b2, b3 e b4: ognuno dei quattro bit può essere 0 oppure 1.
Anna teme che durante la trasmissione si verifichino degli errori: un errore di trasmissione è una situazione per cui viene trasmesso uno 0 ma viene ricevuto un 1, o viceversa.
Per evitare almeno in parte i problemi di trasmissione, Anna decide di aggiungere al suo messaggio tre bit b5, b6 e b7 che sono calcolati a partire dagli altri quattro in base alle seguenti regole:

  • b5=b2+b3+b4;
  • b6=b1+b3+b4;
  • b7=b1+b2+b4;

La somma è definita secondo la seguente tabella:

  • 0+0=0
  • 0+1=1
  • 1+0=1
  • 1+1=0

Quindi, ad esempio, se il messaggio da trasmettere fosse 0110, Anna invierebbe 0110011.
Dunque, Anna invia sette bit (i quattro bit del messaggio originale, più i tre bit calcolati come sopra).
Bruno sa che durante la trasmissione o non si sono verificati errori, oppure si è verificato esattamente un errore (cioè, esattamente uno dei sette bit ricevuti è sbagliato).

Dovete aiutare Bruno a ricostruire i quattro bit del messaggio originale che Anna voleva inviare.

  1. Bruno ha ricevuto 1100011; il messaggio di Anna era ………… (quattro bit);
  2. Bruno ha ricevuto 1010110; il messaggio di Anna era ………… (quattro bit);
  3. Bruno ha ricevuto 1111111; il messaggio di Anna era ………… (quattro bit).

5

Un gruppo di persone (Alberto, Beatrice, Carlo, Davide, Enzo, Franco, Giulio e Harry) si scambiano abitualmente software free.
Ognuno di loro, appena entra in possesso di un nuovo CD, fa una copia per ciascuno dei suoi amici (saltando, naturalmente, gli amici che lo hanno già copiato) e invia il giorno stesso una copia a ciascun amico; ogni amico riceve il CD il giorno successivo alla spedizione.
Ognuno degli amici segue esattamente la procedura che abbiamo descritto.

La seguente tabella riassume le relazioni di amicizia che intercorrono fra le otto persone:

Gli amici di… sono…

  • Alberto: Beatrice, Carlo, Davide
  • Beatrice: Alberto, Enzo
  • Carlo: Alberto, Enzo, Giulio
  • Davide: Alberto, Harry
  • Enzo: Beatrice, Carlo, Franco
  • Franco: Enzo, Harry
  • Giulio: Carlo, Harry
  • Harry: Davide, Giulio, Franco

Alberto torna dagli USA una domenica con un nuovo CD di software e il giorno stesso invia la copia ai suoi amici. Il CD è nuovo e nessuno ne è in possesso.

Quale delle otto persone dovrà aspettare più tempo per poterlo copiare?

In quale giorno l’ultimo riceve una copia del CD?

6

Nel Mercante di Venezia di Shakespeare, Porzia aveva tre scrigni, uno d’oro, uno d’argento e uno di piombo e in uno c’era il suo ritratto.
Porzia voleva scegliere il suo sposo sulla base della sua intelligenza e fece incidere le seguenti iscrizioni sugli scrigni:

  • Scrigno d’oro: il ritratto è in questo scrigno
  • Scrigno d’argento: il ritratto non è in questo scrigno
  • Scrigno di piombo: il ritratto non è nello scrigno d’oro

Porzia spiegò al suo pretendente che di queste tre affermazioni al massimo una era vera.

Quale scrigno contiene il ritratto di Porzia?

7

Con riferimento alla domanda precedente il pretendente scelse in modo corretto e Porzia si sposò.
Un giorno Porzia pensò: “Mio marito ha mostrato di essere intelligente scegliendo lo scrigno giusto; però la domanda non era così difficile.
Avrei potuto fare una domanda più difficile per avere un marito molto intelligente”.
Così Porzia divorziò e cercò un marito più intelligente.

Questa volta fece incidere le seguenti iscrizioni:

  • Scrigno d’oro: il ritratto non è nello scrigno d’argento
  • Scrigno d’argento: il ritratto non è in questo scrigno
  • Scrigno di piombo: il ritratto è in questo scrigno

Porzia spiegò al suo pretendente che almeno una di queste tre affermazioni era vera e almeno una falsa.

Quale scrigno conteneva il ritratto?

Epilogo: nella storia il secondo pretendente non era altro che il primo marito di Porzia che anche questa volta rispose correttamente.
A questo punto Porzia decise di non sottoporre suo marito a nuove prove.

8

Con riferimento alle due domande precedenti immaginiamo che la figlia di Porzia, volendo imitare la madre, escogitò una prova più difficile per scegliere il suo sposo.
Su ogni scrigno erano incise due affermazioni e la figlia di Porzia spiegò ai suoi pretendenti che nessuno scrigno riportava più di un’affermazione falsa.

Sugli scrigni erano incise le seguenti iscrizioni:

Scrigno d’oro:

  • il ritratto non è qui dentro
  • il pittore del ritratto è nato a Roma

Scrigno d’argento:

  • il ritratto non è nello scrigno d’oro
  • il pittore del ritratto è nato e vissuto ad Atene

Scrigno di piombo:

  • il ritratto non è in questo scrigno
  • il ritratto è nello scrigno d’argento

Quale scrigno conteneva il ritratto?

9

Con riferimento alla domanda precedente immaginiamo che più pretendenti della figlia di Porzia furono in grado di individuare lo scrigno giusto.
Per scegliere finalmente lo sposo, la figlia di Porzia pose un altro quesito.

Su ogni scrigno erano incise due affermazioni e la figlia di Porzia spiegò ai suoi pretendenti che

  • su uno scrigno le affermazioni erano entrambe vere
  • su un altro erano entrambe false
  • sul terzo una era vera e una era falsa.

Sugli scrigni erano incise le seguenti iscrizioni:

Scrigno d’oro:

  • il ritratto non è qui dentro
  • il ritratto è nello scrigno d’argento

Scrigno d’argento:

  • il ritratto non è nello scrigno d’oro
  • il ritratto è nello scrigno di piombo

Scrigno di piombo:

  • il ritratto non è in questo scrigno
  • il ritratto è nello scrigno d’oro

Quale scrigno conteneva il ritratto?

10

Si hanno a disposizione due tubi A e B aperti ad una sola estremità.
Il tubo A contiene 4 dischi sovrapposti di diametro pari a quello del tubo e il tubo B è vuoto.
I dischi sono numerati da 1 a 4 e sono inizialmente disposti in ordine crescente, con il disco 1 in fondo al tubo A e il disco 4 in cima.

Si possono compiere 4 operazioni:

  1. Estrarre il disco in cima al tubo A ed inserirlo in cima al tubo B.
  2. Estrarre il disco in cima al tubo B ed inserirlo in cima al tubo A.
  3. Prendere il disco in cima a un tubo e tenerlo in mano. Si può avere in mano al più 1 disco alla volta.
  4. Supponendo di avere in mano un disco, lo si può inserire in cima ad uno dei due tubi.

Si chiede quale sia il minimo numero complessivo di operazioni dei tipi sopra indicati necessarie per muovere tutti i dischi dal tubo A al tubo B mantenendo l’ordine di partenza.

Nota che il trasferimento può essere fatto in diversi modi; la domanda richiede di indicare il numero MINIMO di operazioni necessarie.

Esempio

Se i dischi fossero solo due e il disco 2 fosse sopra al disco 1 nel tubo A allora la seguente sequenza di operazioni permette di effettuare il trasferimento dei dischi nel tubo B mantenendo l’ordine iniziale: un’operazione 3 (si prende un disco dal tubo A), seguita da un’operazione 1 e, infine, un’operazione 4.

In questo caso è facile anche vedere che non è possibile effettuare il trasferimento con un minor numero di mosse e, quindi, il numero minimo è 3.

Nota Bene: fai attenzione perché la domanda ha un punteggio molto alto e la risposta non è facile…