25. Gioco di segni

[Sonner]

Arnaldo e Beatrice si alternano nel mettere un + o un - davanti a ciascuno dei numeri da 1 a 20 (in qualsiasi ordine). Dopo che vengono scelti tutti i 20 segni, Beatrice vince il valore assoluto della somma risultante.
1) Trovare, se esiste, la migliore strategia per ciascuno dei giocatori
2) Quanto vince Beatrice se tutti e due usano la propria strategia migliore?

[Drago96]

L'obiettivo di Arnaldo è di far vincere il meno possibile a Beatrice, giusto?
Beatrice per vincere il più possibile deve mettere tutti segni concordi, invece arnaldo deve mettere segni opposti a quelli di beatrice.
immagino che inizi arnaldo, giusto?
Allora può scegliere due modi di iniziare, che portano allo stesso risultato: mettere un segno all' 1 oppure al 20.
se A parte dall' 1, allora B metterà lo stesso segno al 20, poi A il segno opposto al 19 e così via, alternando i segni e andando in ordine decrescente. In questo modo B guadagna 30.
se A parte dal 20, allora B metterà lo stesso segno al 19, poi A segno opposto al 18 e così via; anche in questo modo B vince 30.

Corretto?

[Sonner]

Beatrice per vincere il più possibile deve mettere tutti segni concordi, invece arnaldo deve mettere segni opposti a quelli di beatrice.

L'idea è più o meno quella giusta, prova a dimostrarla

[Drago96]

Beatrice per vincere il più possibile deve mettere tutti segni concordi, invece arnaldo deve mettere segni opposti a quelli di beatrice.

L'idea è più o meno quella giusta, prova a dimostrarla

Come posso fare? Mi sembra ovvio...
L'unica cosa che posso dire per farla un po' più formale é che il modulo aumenta con segni concordi e dimonuisce con segni discordi per definizione!

Oppure intendevi un'altra cosa?

[Hawk]

Allora può scegliere due modi di iniziare, che portano allo stesso risultato: mettere un segno all' 1 oppure al 20.

Qui mi sembra ci sia un errore, forse hai commesso qualche errore nella somma, oppure sto dicendo una sciocchezza. A me viene:

$ |1+20-19+18-17+16-15+14.....-3+2|=\left|\displaystyle\sum_{n=1}^{10}2n-\displaystyle\sum_{i=1}^{10}(2i-1)+2\right|=12 $

Ho provato anche con la calcolatrice, per sfizio ho poi usato la sommatoria (per non dimenticarne l'uso).

Comunque se ne deduce che questa è la migliore strategia, l'altra no.
Provo a dimostrare quello che ha chiesto Sonner.

Beatrice mette il 20 con lo stesso segno del numero scelto da Arnaldo. Quest'ultimo deve sommare sempre i numeri in modo tale che il totale si avvicini allo zero. Beatrice, invece, deve aggiungere un numero tale che annulli quello scelto da Arnaldo. Diventa quindi un differenza tra un numero ed il proprio consecutivo, che è quindi minima e pari ad 1.
Infatti: $ 21-19+18-17+1...=21-1-1.... $
Per questo Beatrice deve sempre scegliere i numeri con lo stesso segno, e Arnaldo con il segno opposto.
Non so' se è proprio una dimostrazione, potreste darmi qualche dritta, oppure va bene?

[Drago96]

Hai assolutamente ragione...
Non so perchè mi sia venuto 30 anche partendo da 1... in effetti mi pareva un po' strano...

[darkcrystal]

Come posso fare? Mi sembra ovvio...
L'unica cosa che posso dire per farla un po' più formale é che il modulo aumenta con segni concordi e dimonuisce con segni discordi per definizione!

Il problema è carino, quindi mi spiace che da qualche giorno non ci siano interventi.

Vorrei solo far presente che un esercizio del genere è costituito (essenzialmente) da tre parti:
- primo, decidere quale pensate sia la cifra che vincerà B se entrambi i giocatori adotteranno la strategia migliore possibile. Diciamo che questa cifra sia X;
- secondo, descrivere una strategia che consenta a B di vincere almeno X indipendentemente da quello che fa A;
- terzo, descrivere una strategia che consenta ad A di far sì che la cifra vinta da B non superi X, indipendentemente da quello che fa B.

Questo certamente fa vedere che le due strategie non sono migliorabili, e dimostra qual è la cifra che sarà vinta da B nel caso di giocatori perfetti.
Quello che intendeva Sonner, almeno credo, è proprio che bisogna dimostrare che ci sono strategie che portano chi le impiega al risultato voluto (guadagnare almeno X / non far guadagnare più di X), qualunque cosa faccia l'avversario (cioè senza supporre che l'avversario giochi con quella che noi pensiamo essere la strategia migliore).

E ora, buon lavoro.

[Drago96]

Ci riprovo.
Beatrice per vincere il più possibile deve mettere lo stesso segno ai numeri che sceglie, scegliendo sempre il più grande numero disponibile; infatti se mettesse segni discordi il modulo diminuirebbe, mentre se scegliesse i numeri "a caso" A ne approfitterebbe scegliendo lui il numero più grande con segno opposto.
La strategia migliore per A è mettere i segni opposti a quelli di B, per diminuire il mosulo e scegliendo sempre il più grande disponibile, altrimenti lascerebbe campo libero a B. Inoltre A, dato che inizia e non sa che segni userà B ma sa che copierà la sua prima mossa, deve partire da 1.

Facendo in questi modo B vince 12.

Spero che vada bene, perchè non so cos'altro dire

[darkcrystal]

La strategia migliore per A è mettere i segni opposti a quelli di B, per diminuire il mosulo e scegliendo sempre il più grande disponibile, altrimenti lascerebbe campo libero a B. Inoltre A, dato che inizia e non sa che segni userà B ma sa che copierà la sua prima mossa, deve partire da 1.

Se ho ben capito quello che intendi, purtroppo questa non è la strategia vincente per A.

Se infatti A si limita a scegliere sempre il più grande numero disponibile si può avere la seguente partita:
- A inizia e sceglie +1
- B sceglie -2 (non è certo contro le regole, anche se a noi può non sembrare la mossa migliore possibile)
- A, seguendo la tua strategia, sceglie +20 (il più grande numero disponibile, con segno opposto a quello della somma attuale)
- B sceglie a questo punto di mettere +19.
- A e B si alternano ora nel modo "usuale", scegliendo il numero più grande ed il segno nel modo che descrivi, e la partita finisce con

+1 -2 +20 +19 -18 +17 -16 +15 -14 +13 -12 +11 -10 +9 -8 +7 -6 +5 -4 +3 = +30, decisamente peggio (dal punto di vista di A) del 12 che stavamo cercando!

Spero che questo esempio ti mostri dove risiedono la difficoltà e l'importanza di descrivere una strategia che vada bene sempre, indipendentemente dalle mosse dell'avversario. Comunque non disperare, l'idea di fondo non è sbagliata (in particolare quando dici che A vuole "diminuire il modulo"), prova a continuare a pensarci...

[Drago96]

Ok, capito...
Allora A deve scegliere sempre il numero successivo (o quello più vicino possibile) a quello di B e mettere segno opposto. Va meglio?
La strategia di B mi pare sia corretta, giusto?

[Citrullo]

Beatrice guadagnerà 12.

Chiamo A e B i personaggi.

La strategia di B può essere quella di scegliere sempre il più alto numero possibile, con segno concorde al primo numero scelto da A che chiamo k. In questo modo alla fine ordino le scelte di A e B in due serie $ a_i $ e $ b_i $ escludendo per il momento k e U, l'ultimo numero scelto da B (così le due serie han lo stesso numero di elementi, cioè 9). Ora so che $ \forall i $ $ b_i>a_i $ perchè B ha scelto il numero più grande quando poteva, ma allora $ b_i-a_i \geq 1 $ e perciò $ \displaystyle \sum_{i=1}^9 b_i-a_i \geq 9 $ quindi il guagagno di B sarà di almeno $ 9+k+U $. Dato che k e U sono due numeri distinti tra 1 e 20 $ k+u \geq 3 \rightarrow $ B guadagna almeno 12.

D'altra parte esiste una strategia per A di far prendere sempre al massimo 12 a B, ed è la stessa dell'amica: A parte scegliendo 1, B le risponderà scegliendo j concorde con l'1 (se non lo fa tanto meglio per A, il delta è minore! vedi alla fine). Ora rimangono 18 numeri su cui A fa lo stesso identico gioco di B nel caso precedente, ovvero sceglie sempre il più grande sempre con lo stesso segno. Come sopra, se tolgo 1 e j e ordino le scelte in due serie $ a_i $ e $ b_i $ con $ 1 \leq i \leq 9 $ avrò $ \displaystyle \sum_{i=1}^9 a_i-b_i \geq 9 $ quindi A può far perdere a B almeno 9 punti. Il guadagno di B sarà allora $ \leq $ a $ j+1-9 $ e se A sceglie il suo massimo j (che è 20) otterrà un guadagno $ \leq 12 $.

Dato che B può riuscire a guadagnare un numero maggiore o uguale a 12 ma A può riuscire a lasciargliene un numero minore o uguale a 12, se entrambi giocano al meglio B guadagnerà 12.

EDIT: no mi son già reso conto che la seconda parte è sbagliata, ci ripenso

[Drago96]

Anch'io l'avevo fatto così e ne ero anche convinto, però...

La strategia migliore per A è mettere i segni opposti a quelli di B, per diminuire il mosulo e scegliendo sempre il più grande disponibile, altrimenti lascerebbe campo libero a B. Inoltre A, dato che inizia e non sa che segni userà B ma sa che copierà la sua prima mossa, deve partire da 1.

Se ho ben capito quello che intendi, purtroppo questa non è la strategia vincente per A.

Se infatti A si limita a scegliere sempre il più grande numero disponibile si può avere la seguente partita:
- A inizia e sceglie +1
- B sceglie -2 (non è certo contro le regole, anche se a noi può non sembrare la mossa migliore possibile)
- A, seguendo la tua strategia, sceglie +20 (il più grande numero disponibile, con segno opposto a quello della somma attuale)
- B sceglie a questo punto di mettere +19.
- A e B si alternano ora nel modo "usuale", scegliendo il numero più grande ed il segno nel modo che descrivi, e la partita finisce con

+1 -2 +20 +19 -18 +17 -16 +15 -14 +13 -12 +11 -10 +9 -8 +7 -6 +5 -4 +3 = +30, decisamente peggio (dal punto di vista di A) del 12 che stavamo cercando!

Spero che questo esempio ti mostri dove risiedono la difficoltà e l'importanza di descrivere una strategia che vada bene sempre, indipendentemente dalle mosse dell'avversario. Comunque non disperare, l'idea di fondo non è sbagliata (in particolare quando dici che A vuole "diminuire il modulo"), prova a continuare a pensarci...

[Citrullo]

Mi sa che abbiamo sbagliato alla grande!!

Proviamo a sparare molto più in alto: ora sostengo che B guadagnerà almeno 30..

Divido i numeri in coppie in ordine crescente: (1,2), (3,4), ..., (19,20).
Ogni volta che A sceglie un numero, B sceglie il "compagno di coppia" col segno opposto tranne quendo A prende un numero della coppia (19,20), e in quel caso egli sceglie l'altro con segno concorde. Per forza di cose, anche perdesse un punto ognuna delle altre 9 coppie, ne guadagna 39 nell'ultima, ottenendo un guadagno di almeno 30.

[Drago96]

Divido i numeri in coppie in ordine crescente: (1,2), (3,4), ..., (19,20).
Ogni volta che A sceglie un numero, B sceglie il "compagno di coppia" col segno opposto tranne quendo A prende un numero della coppia (19,20), e in quel caso egli sceglie l'altro con segno concorde.

Io direi al contrario: parte A, sceglie un numero; B sceglie un altro numero (secondo la sua strategia 20), allora B sceglierà il "compagno di coppia", con il segno opposto.

Dunque abbiamo 1+20-19+18...+2=12

Va bene?

[Ido Bovski]

Vogliamo risuscitare questa staffetta? Drago96, prendi tu il testimone?