Domande e risposte.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

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]

Una.
Ovvero "Ti bastano mille euro?"

Cordialmente, Alex

[axpgn]

Upper bound: $n$

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

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"axpgn":

Una.
Ovvero "Ti bastano mille euro?"

Cordialmente, Alex

Sì, ma mo' cacciali fuori

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"axpgn":

Upper bound: $ n $

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

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

[axpgn]

"3m0o":Sì, ma mo' cacciali fuori

Puoi rispondere solo "sì" o "no"

"3m0o":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

- È 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

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

No, si può fare molto meglio

[axpgn]

Oh, non avevo dubbi, conoscendoti

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Un bel hint:

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!

[axpgn]

Mi permetto di criticare

Se nel testo del quesito scrivi "ordine totalmente casuale" non puoi scegliere un ordine!
Non è più "totalmente casuale", in pratica introduci una condizione ulteriore, un dato in più; quindi la mia precedente risposta è corretta, relativamente al problema iniziale

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Non volevo dire scegliere in quel senso, si l'ordine con cui rispondo è totalmente casuale

[axpgn]

E allora cosa volevi dire con quell'hint che non è un hint?

[hydro1]

"axpgn":E allora cosa volevi dire con quell'hint che non è un hint?

Secondo me vuol dire la seguente cosa: le risposte non sono simultanee, ma sequenziali. Cioè lui sceglie un ordine in cui rispondere alle domande, e poi risponde in quell'ordine. Se rispondesse a tutte le domande contemporaneamente penso che la tua risposta sarebbe ottimale.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Esatto hydro, vuol dire questo

Supponiamo che mi fate
1. Domanda 1
2. Domanda 2
3. Domanda 3
4. Domanda 4

E che io risponda (casualmente) nel seguente ordine
1. Domanda 2
2. Domanda 3
3. Domanda 1
4. Domanda 4

Allora voi ricevete le risposte nel ordine con cui ho risposto, cioè
1. Risposta alla domanda 2
2. Risposta alla domanda 3
3. Risposta alla domanda 1
4. Risposta alla domanda 4

Solo che voi non sapete che la prima risposta si riferisce alla domanda 2 perché non conoscete l'ordine con cui ho risposto siccome è casuale, però sapete che la prima risposta è la risposta alla prima domanda a cui ho risposto.

[axpgn]

Tutte le domande sono come questa:

- Considerando la rappresentazione binaria del numero pensato, è zero la cifra in posizione corrispondente al numero d'ordine della tua risposta a questa domanda? O qualcosa del genere
Quindi $\ceil(log_2 n)$ domande ...

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

axpgn

Penso che la tua funzioni e mi piace di più della mia.
Per semplicità chiamo \(k \) il numero pensato. Io ho trovato una formulazione - credo equivalente alla tua. Ovvero quella di porre \( \left \lceil \log_2(n) \right \rceil \) volte la seguente domanda:

È vero che {[Se questa è la prima domanda a cui rispondi allora \( k > n/2 \) ] AND [se questa è la seconda domanda a cui rispondi risposta allora (\( k\leq n/4 \) OR \( k \geq 3n/4 \) )] AND ...} ?

Ad esempio con \(n = 16 \) abbiamo che la domanda può essere ad esempio

È vera che: {[Se questa è la prima domanda a cui rispondi allora \( k > 8 \) ] AND [se questa è la seconda domanda a cui rispondi allora (\( k \leq 4 \) OR \( k \geq 13 \) )] AND [se questa è la terza domanda a cui rispondi allora (\( k \leq 2 \) OR \( 5 \leq k \leq 6 \) OR \(11 \leq k \leq 12 \) OR \( 15 \leq k \leq 16 \))] AND [se questa è la quarta domanda a cui rispondi allora (\( k =1 \) OR \( k=3 \) OR \(k=5\) OR \( k=7 \) OR \( k=10 \) OR \( k=12 \) OR \( k=14 \) OR \( k=16 \) )]} ?

Vediamo quindi che ogni numero è posto in corrispondenza univoca nel seguente modo
1 -> 0111
2 -> 0110
3 -> 0101
4 -> 0100
5 -> 0011
6 -> 0010
7 -> 0001
8 -> 0000
9 -> 1000
10 ->1001
11 ->1010
12 ->1011
13 ->1100
14 ->1101
15 ->1110
16 ->1111

Dove 0=no e 1=si.

Siccome "Se P allora Q" è sempre vero quando P è falso allora con gli AND otteniamo la risposta desiderata solo quando P è vera! Quindi quando P è vera otteniamo come risposta "sì" se Q è vero e otteniamo "no" quando Q è falso.

[axpgn]

Penso che sostanzialmente siano la stessa cosa e mi era anche balenata l'idea di tentare qualcosa di simile a quello che hai fatto ma ho lasciato perdere subito: troppo casino per me
E allora ho cercato di semplificare e mi pare che funzioni

Cordialmente, Alex