Gioco matematico fra amici - SNS 1978 (Conferma soluzione)

[elios]

"Due amici A e B fanno questo gioco: quando uno dei due dice un numero intero positivo, l'altro lo dimezza se è pari, mentre gli toglie uno se è dispari. Vince chi pronuncia il numero 1. (Esempio: A dice 18, B risponde 9, A risponde 8, B con 4, A e con 2 e B dice 1: B vince in 6 colpi) Il giocatore A comincia il gioco scegliendo un numero maggiore di 30.000 e minore di 31.000.
Quale scelta deve fare se vuole vincere nel minimo numero di colpi?"

Vince comunque quello che deve rispondere al numero 2, quindi A deve fare in modo che sia B a pronunciare il numero 2.
A questo punto, è chiaro che il minor numero di colpi si ha per una discesa più "ripida" dei numeri, che ovviamente è data dal dimezzare i numeri piuttosto che togliere uno. Quindi la discesa più rapida si ha se il numero iniziale fosse una potenza di 2. Ma non ci sono potenze di 2 comprese fra 30.000 e 31.000..
Perciò, io ho ipotizzato che la discesa più rapida di numeri sia data da un numero del tipo $2^k*h$, con $k$ massimo e $h$ minimo. Il risultato che ottengo è $2^(11)*15=2048*15=30.720$. Infatti dopo 11 mosse si è già arrivati a 15, e dopo altre 6 si è arrivati ad 1. Siccome inizia A e vuole vincere, lui dovrà partire con 30.721
Infatti:
$A -> 30.721$
$B -> 30.720$
$A -> 15.360$
$B -> 7.680$
$A -> 3.840$
$B -> 1.920$
$A -> 960$
$B -> 480$
$A -> 240$
$B -> 120$
$A -> 60$
$B -> 30$
$A -> 15$
$B -> 14$
$A -> 7$
$B -> 6$
$A -> 3$
$B -> 2$
$A -> 1$
vincendo in un totale di 19 "colpi", come li chiama il testo..

Che ne dite? Posso giustificare meglio questa mia soluzione, se è corretta? Grazie.

[G.D.]

Io sono d'accordo.

[elios]

Secondo te è inevitabile quella parte di calcoli, e di tentativi?
Temo sempre che si possa rendere più letterale e più generico..

[G.D.]

Mah, onestamente io non avrei saputo fare di meglio.
Considera però che io so scarso e con i quesiti di TdN e affini ancora di più: ergo, io mi sarei buttato ancor di più a tentativi.

Magari attendiamo che qualcuno più ferrato in questo tipo di problemi posti un parere.

[alsfigato]

Scusa ma non ho capito come hai stabilito il massimo e il minimo...

[elios]

Eh, nel modo più barbaro che ci sia, cioè calcolatrice alla mano, ho fatto i conti per cui il risultato mi veniva compreso fra 30.000 e 31.000

[LucaGamba16]

Partendo dal fondo del gioco, ogni volta si può aggiungere 1 o moltiplicare per 2. Esclusi i primi due numeri (1 e 2) moltiplicare per 2 da un incremento maggiore rispetto che sommare 1. Di conseguenza, visto che non ci sono potenze di 2 comprese tra 30000 e 31000 cerchiamo il numero scritto come somma di potenze di 2 con il minor numero di addendi possibile. Tale numero è 30720 = 16384+8192+4096+2048. A questo punto raccogliamo 2048 alla somma ed otteniamo 2048 (1+2+4+8). Quello che c'è tra parentesi è ciò che è successo alla fine del gioco, il quale visto al contrario, è in questa forma: A 1; B2; A 2+1; B 4+2; A 4+2+1; B 8+4+2; A 8+4+2+1. Quello che si è fatto è stato scrivere separatamente tutte le volte che si addizionava 1. Arrivati a questo punto si contano le mosse, che sono 18. Per far si che A inizi e finisca il gioco questo numero dovrebbe essere dispari ma basta supporre che il numero iniziale fosse 30721 per ottenere 19 mosse e mantenere il ragionamento di prima valido.
Il fatto che si addizioni all'inizio nel "gioco ribaltato" è sensato poiché 2(x+1)>2x+1 per x intero positivo.