Domande e risposte.

[3m0o]

Supponiamo che io abbia scelto un numero intero compreso tra \(1\) e \(n\), e che voi possiate scrivermi quante domande "si-no" volete. Io dopo averle lette tutte risponderò sinceramente a tutte quante ma in ordine totalmente casuale, quindi voi riceverete solo una lista di tanti "si" o di "no" quante le domande ricevute, ma non saprete quale risposta si riferisce a quale domanda. Qual è il numero minimo di domande che dovete farmi per capire con certezza qual è il numero che ho pensato?

[axpgn]

Testo nascosto, fai click qui per vederlo

Una.
Ovvero "Ti bastano mille euro?"

Cordialmente, Alex

[axpgn]

Testo nascosto, fai click qui per vederlo

Upper bound: $n$

- È compreso tra $1$ e $1$ compresi?
- È compreso tra $1$ e $2$ compresi?
- ecc.

[3m0o]

Testo nascosto, fai click qui per vederlo

Una.
Ovvero "Ti bastano mille euro?"

Cordialmente, Alex

Sì, ma mo' cacciali fuori

[3m0o]

Testo nascosto, fai click qui per vederlo

Upper bound: $ n $

- È compreso tra $ 1 $ e $ 1 $ compresi?
- È compreso tra $ 1 $ e $ 2 $ compresi?
- ecc.

Testo nascosto, fai click qui per vederlo

L'upper bound è giusto, nel senso che con \(n\) domande come le hai poste tu, le trovi, ma è anche il lower bound?

[axpgn]

Sì, ma mo' cacciali fuori

Puoi rispondere solo "sì" o "no"

Testo nascosto, fai click qui per vederlo

L'upper bound è giusto, nel senso che con \( n \) domande come le hai poste tu, le trovi, ma è anche il lower bound?

Una cosa alla volta

[axpgn]

Minimo miglioramento

Testo nascosto, fai click qui per vederlo

- È maggiore di $1$?
- È maggiore di $2$?
....
- È maggiore di $n-1$?

In questo modo mi bastano $n-1$ domande.

Mi verrebbe da dire che non si possa con meno dato che con $n$ domande posso avere da zero a $n-1$ "sì" e dato che non posso ordinarli, posso avere al massimo $n$ informazioni. IMHO

Cordialmente, Alex

[3m0o]

No, si può fare molto meglio

[axpgn]

Oh, non avevo dubbi, conoscendoti

[3m0o]

Un bel hint:

Testo nascosto, fai click qui per vederlo

Ci tengo a precisare che io rispondo alle domande in ordine casuale, questo significa che le risposte le ottenete nel ordine con cui ho risposto solo che non sapete l'ordine casuale che ho scelto!