Newsgroup: it.hobby.enigmi
Titolo: Il problema delle bandiere

Nato quasi per caso da una mailing list la cui soluzione proposta era a dir
poco scandalosa ha comunque offerto agli iscritti di tale mailing list
l'opportunità di aver pensato e proposto due interessanti soluzioni : una
"colta e raffinata" e una più terra terra, la soluzione che vi chiedo è
quella terra terra (a cui sono particolarmente affezionato poichè mia :-)).
Il problema non è difficile ma neanche facilissimo.
Ecco il problema:
Una persona deve comunicare ad un'altra persona un numero compreso tra 1 e
64 in sole 3 mosse.
Informazioni:
1) Colui che deve comunicare il numero possiede 2 bandiere: una sulla
destra e una sulla sinistra che potrà alzare ottenendo quindi i 4 possibili
stati di bandiere alte e basse. Faccio notare che non si possono fare
mastrussamenti come scambiare la bandiera di destra con la sinistra
buttarne una per terra, urla, movimenti strani, ecc.., insomma gli stati
sono solo i 4 canonici.
2) Per separare i segnali (e solo per separare i segnali) per esempio
stenderà le braccia orizzontalmente o alzerà una gamba o comunque farà
qualche cosa che renderà il pasaggio dell'informazione più chiaro
(naturalmente verrà comunicato all'inizio)
3) Almeno una delle due persone non conosce la numerazione binaria.
4) Nessuno dei due possiede l'orologio ne un qualunque segnatempo, non vi è
insomma la possibilità di utilizzare il tempo come uno strumento per la
risoluzione del gioco.
5) All'inizio colui che dovrà comunicare il numero consegnerà un foglio
all'altro in cui vi è scritto il modo per comunicare tale numero.
6) Colui che dovrà individuare il numero non ha la possibilità per scrivere
niente (non è dotato neanche di grosse capacità astratte di calcolo....anzi
piuttosto pochine)
Buon lavoro :-)
Francesco

Se le non grosse capacità astratte di calcolo lo consentono...
-
.
.
S
P
O
I
L
E
R
.
.
-
   Bandiera (1 dx) * 32
+ Bandiera (1 sx) * 16
+ Bandiera (2 dx) *  8
+ Bandiera (2 sx) *  4
+ Bandiera (3 dx) *  2
+ Bandiera (3 sx) *  1
Questo non presuppone necessariamente la conoscenza della numerazione binaria 
(su cui ovviamente si basa la procedeura di codifica). Non mi sembrano nemmeno 
calcoli troppo impegnativi per l'(ignorante in matematica) quadratico medio.
Dade :)

Ho dimenticato di aggiungere che alla somma finale va aggiunto 1, ovviamente.
Dade :)

 calcoli troppo impegnativi per l'(ignorante in matematica) quadratico
medio.
Ma sti subdoli  "binaristi" le escogitano tutte...uffi ^__^
Diciamo allora che non ci sono proprio operazioni da fare...tiè :-)
Francesco
p.s. bravo comunque (ma non è la soluzione che cercavo)

 stati di bandiere alte e basse.
Si tratta, se non interpreto male, di 4 posizioni ripetute 3 volte,
se e' cosi' allora si risolve in questo modo:
1 mossa: ognuna delle 4 posizioni (chiamiamole ABCD) indica 1/4 di 64,
A= il numero sta tra 1 e 16, B= sta tra 17 e 32, ecc.
2 mossa: ognuna delle 4 posizioni (chiamiamole EFGH) indica 1/4 di 16
E = 1 2 3 4  F = 5 6 7 8  G = 9 10 11 12 
ecc.se
 la 1 mossa era A
E = 17 18 19 20 F = 21 22 23 24 ecc. se la 1 mossa era B
3 mossa: ognuna delle 4 posizioni (chiamiamole ILMN) indica il mumero
I=1 L=2 M=3 N=4 
ecc.se
 la 2 mossa era E
I= 21 L= 22 M=23 N=24 
ecc.se
 la 2 mossa era F
Saluti
R.


gira e rigira si DEVE parlare di numeri binari!!!
da quel che mi ricordo degli studi fatti:
i problemi sono classificabili a seconda della complessità,
problemi della stessa complessità sono riconducibili l'uno all'altro,
i più complessi sono quelli np-completi (o come si scrive)
se un giorno si riuscisse a risolvere anche un solo np-completo, allora
sarebbero
risolti tutti gli altri (per es. il problema del postino).
i problemi np-completi possono essere risolti con la forza-bruta, ma si
cerca qui
una soluzione algoritmica...
il tuo problema ha complessità logaritmica (ogni volta si dimezzano le
possibilità)
e viene risolto in log2(n) passi....
nell'esempio  log2(64) = 6
stesso procedimento che si utilizzerebbe con un problema a base di numeri
binari---> ergo.... etc. etc

 Si tratta, se non interpreto male, di 4 posizioni ripetute 3 volte,
Hai interpretato talmente bene che hai indovinato ^__^
BRAVO !
Francesco

"Flame71"
bah non so se sia da consideare un problema affrontato coi numeri binari ma
si risolve come ha descritto broccan
Francesco

 ha scritto nel messaggio
news:ZPNfd.3542$Ni.1...@twister1.libero.it...

dividere ogni volta per 2... bisezione, binario, ....
attenzione che dire risolto COI numeri binari è differente che dire:
risolto DAI numeri binari....
i numeri binari sono una comoda rappresentazione, ma non l'unica, sono solo
uno degli
infiniti metodi di risoluzione (= a tutti quelli dei problemi con la stessa
complessità)
es. ricerca di un numero sull'elenco telefonico
soluzione = apro a caso il librone (= divido per 2)... se il nome è < del
primo della pagina... altrimenti....
prendo la parte restante e divido per 2....
domandina: se il librone ha 64 pagine, indovina quante smazzate devo fare al
massimo?

.
.
.
.
.
.
.
.
.
spoiler
.
.
.
.
.
.
.
.
.
spoiler
.
.
.
.
.
.
.
.
.
spoiler
.
.
.
.
.
.
.
.
.
spoiler
.
.
.
.
.
.
.
.
.
spoiler
.
.
.
.
.
.
.
.
.
spoiler
.
.
.
.
.
.
.
.
.
non vedo cosa ci sia di complicato...
in ogni passo con due bandiere è possibile indicare 4 valori, 
informaticamente parlando 2^2 valori...
i passi possibili sono 3, quindi 2 bandiere (o bit) alla volta per 3 volte 
danno 6 bandiere (o bit)... in tutto si possono esprimere quindi 2^6 = 64 
valori...
visto che il numero da comunicare è compreso tra 0 e 63 (o 1 e 64) direi che 
non ci sono problemi a farlo...
nb: non è possibile trasmettere valori fuori dal range dei 64 previsti senza 
aggiungere dell'incertezza...
forse ti riferivi al codice esatto da usare tra il trasmettitore ed il 
ricevitore...
ma anche in questo le difficoltà sono esigue... visto che il metodo deve 
essere semplice, lo baserò su tabelle invece che su equazioni da 
calcolare...
il numero di diversi valori che è possibile trasmettere è 64, ma le bandiere 
permettono solo di trasmettere 4 valori per volta... ragiono come se ogni 
trasmissione sia una approssimazione sempre migliore al valore da 
trasmettere (in campo applicativo molti ADC, convertitori 
analogico-digitali, funzionano così)...
64 diviso 4 fa 16: uso questo valore come base per la mia tabella 
(tecnicamente si chiama PASSO DI QUANTIZZAZIONE)... la tabella relativa al 
primo invio sarà dunque:
b b 0
b a 16
a b 32
a a 48
in cui b sta per basso, a sta per alto e i numeri indicano il LIVELLO 
(uguale al passo di quantizzazione per il numero del livello stesso)
con la seconda trasmissione, si intende dare una migliore approssimazione 
all'interno di ogni livello individuato al passo precedente. in questo caso 
i valori tra cui discernere sono 16 e le bandiere permettono come al solito 
solo 4 alternative... analogamente a prima trovo che il nuovo passo di 
quantizzazione è 16 diviso 4 uguale 4 e dunque la tabella con i livelli per 
il secondo invio sarà:
b b 0
b a 4
a b 8
a a 16
procedo quindi all'ultimo passo in cui i valori ammissibili sono 4. molto 
semplicemente sarà:
b b 0
b a 1
a b 2
a a 3
come avviene appunto nei convertitori analogico-digitali ad approssimazione 
multipla, il ricevitore deve sommare i valori trovati relativi ad ogni passo 
ed otterrà esattamente il valore che si era voluto inviare...
questo metodo prevede la consultazione di 3 tabelle e una somma di 3 
addendi...
il codice binario non è direttamente richiamato in causa... 
(informaticamente parlando, forse era più comodo considerare il valore di 
ogni singola bandiera come bit di informazione e quindi considerare la 
sequenza di tutti e sei i bit trasmessi come descrizione in codice binario 
del valore da trasmettere... ma la conversione sarebbe stata sicuramente più 
ostica!)
Stefano