Newsgroup: it.hobby.enigmi
Titolo: [MA] Solitario

.
. _ _ _ _ _ _
6|_|_|_|_|_|_|
5|_|_|_|_|_|_|
4|_|_|_|_|_|_|
3|_|_|_|_|_|_|
2|_|_|_|_|_|_|
1|x|_|_|_|_|_|
   a b c d e f....
Questa e' l'origine di una scacchiera che si estende a 
piacere verso l'alto e verso destra.
All'inizio c'e' una sola pedina in a1.
Una mossa consiste nel togliere una pedina esistente e 
sostituirla con altre 2 mettendole una sopra ed una a destra 
della pedina appena rimossa.
Evidentemente l'unica prima mossa possibile porta a questa 
posizione:
.
. _ _ _ _ _ _
6|_|_|_|_|_|_|
5|_|_|_|_|_|_|
4|_|_|_|_|_|_|
3|_|_|_|_|_|_|
2|x|_|_|_|_|_|
1|_|x|_|_|_|_|
   a b c d e f....
In questo modo abbiamo liberato la casella a1.
Lo scopo del gioco e' quello di riuscire a liberare in meno 
mosse possibile le prime 6 caselle d'angolo che sono:
a1,a2,a3,b1,b2,c1.
Munitevi di scacchiera e pedine... e tanti auguri (ma tanti) 
  :) dario


***********************************************************************
ciao  a tuttE/i    ;)
RISPETTO PER TUTTI E TUTTO!
1) TUTTO E' RELATIVO ;
2) HO FIDUCIA IN DIO ;
3) A TUTTO C'E' UNA SPIEGAZIONE RAZIONALE ;
4) TUTTO E' POSSIBILE ;
5) SONO COME S. TOMMASO : NON CI CREDO SE NON CI METTO IL NASO .
Marco ;)
***********************************************************************

 ************************************************************************
Scelta una pedina presente sulla scacchiera (chiamiamola A), che abbia le 
due caselle adiacenti sopra e destra vuote (chiamiamole B e C), una mossa 
consiste nel togliere A e contemporaneamente riempire B e C. Poi si passa 
ad una mossa successiva.
ciao :) dario

Munitevi di scacchiera e pedine... e tanti auguri (ma tanti) 
spoiler
Ma e` sicuro che si possa fare?
Con scacchiera e pedine si arriva rapidamente al bordo.
Su Gnumeric sembra che vada avanti per sempre.. :-((
-- 
Ci sentiamo  |  Remigio Zedda  || Attenzione! campo "From:" alterato
ciao Remigio |                 ||==> E-mail: 
remi...@tiscalinet.it
-------------|      ..si` d'accordo.. ma con la Deb e` un'altra cosa!
/* Linux 2.2.19pre17 su Debian GNU/Linux 2.2 Potato */

 Su Gnumeric sembra che vada avanti per sempre.. :-((
SPOILER
Difatti.. prima di ricevere qualche improperio, vi dico che, anche se a 
prima vista sembra un giochetto banale, in realta' lo scopo non e' 
raggiungibile, ma darne una dimostrazione non e' cosi' facile.
ciao :) dario
 

Munitevi di scacchiera e pedine... e tanti auguri (ma tanti)
spoiler
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
Se non ho frainteso il problema, la soluzione è rappresentata nella
seguente tabella dove sono riportate in ordine numerico le pedine
sostituite di volta in volta.
 4|_|_|_|_|_|_|
 3|9|8|7|_|_|_|
 2|6|5|4|_|_|_|
 1|1|2|3|_|_|_|
    a b c d e f....
Un saluto
Gianni
PS: Aderite compatti al Luigino Fans Club (n° 49 soci, finora)
--
Socio fondatore del Luigino Fans Club. Tessera n° 0001
Il grande Vicerè Fini, mette in discussione i parametri di Maastricht.
Vogliamo correre da soli? Torniamo al "tanti nemici, tanto onore"?

    a b c d e f....
La confusione c'e'. Per togliere la 6 devi rimettere la 5.
Come da un post precedente, il problema non ha soluzione.
ciao :) dario
 

 La confusione c'e'. Per togliere la 6 devi rimettere la 5.
OK! Infatti avevo frainteso.
Ciao


SPOILER

Caspita che magnata che mi son fatto, c'avrei fatto un figurone;-))
Vedevo che si ripeteva in continuazione ed avevo presagito che per
rispondere al problema avrei dovuto pero` dimostrarlo.
Allora quando ho tempo ci provo.. ma sara` gia` stato dimostrato:-((


 raggiungibile, ma darne una dimostrazione non e' cosi' facile.
Mi pare che si possa dimostrare con un piccolo artifizio: considero una
variante del gioco con meno vincoli; se dimostro l'impossibilità di questo,
risulta dimostrata anche l'impossibilità del gioco originario.
La variante consiste nel ritenere lecita, nelle fasi intermedie del gioco,
la sovrapposizione di più pedine nella stessa casella; naturalmente a gioco
finito dovrei avere le sei caselle d'angolo vuote, e non più di una pedina
in ciascuna delle altre.
(in pratica mi pare che la variante consista semplicemente nel considerare
tutte le mosse *necessarie*, indipendentemente dall'ordine in cui possano
essere eseguite).
Vediamo gli schemi seguenti, dove i numeri indicano quante pedine sono
presenti in ciascuna cella nelle diverse fasi:
.  A             B            C
. . . . .    . . . . .    . . . . .
. . . . .    . . . . .    1 . . . .
. . . . .    1 . . . .    . 3 . . .
1 . . . .    . 2 . . .    . . 3 . .
. 1 . . .    . . 1 . .    . . . 1 .
.   D            E
. . . . .   . 1 . . .
1 2 . . .   1 1 4 . .
. 1 4 . .   . 1 1 4 .
. . 1 2 .   . . 1 1 1
. . . 1 .   . . . 1 .
La fase A è quella obbligata dopo la prima mossa.
Dobbiamo rimuovere, prima o poi, le due pedine: tanto vale farlo subito e
arriviamo con qualche mossa alla fase B.
Allo stesso modo dalla fase B passiamo alla C.
Ora le sei caselle d'angolo sono libere, ma dobbiamo rimuovere almeno due
pedine da ciascuna casella che ne contiene tre: questo ci porta alla fase D.
Rimuoviamo almeno una pedina dove ce ne sono due, e almeno tre dove ne
abbiamo quattro: arriviamo alla fase E.
Abbiamo visto che la presenza di una diagonale 1-3-3-1 (fase C) comporta
necessariamente la formazione di un'altra diagonale 1-4-4-1 (fase E). Quindi
il gioco è *divergente*, cioè è impossibile eliminare tutte le
sovrapposizioni.
------------
Mi sembra che la dimostrazione funzioni; ne hai una più semplice?
ciao
paolo

 a1,a2,a3,b1,b2,c1.
Ho un argomentazione simile a quella di Paolo per dimostrare
l'impossibilità dell'impresa:
X
. X
. . X
. . . X
Dato cha dobbiamo pulire le sei caselle coi puntini, ed ogni casella
ha ospitato almeno una pedina prima di essere liberata, abbiamo fatto
almeno sei mosse, generando 12 pedine. Queste 12 pedine sono finite
tutte, in tempi diversi, nelle 4 caselle X. Dato che alla fine del
gioco solo 4 possono stare nelle X, altre 8 sono state rimosse,
generando 16 pedine.
Y
X Y
. X Y
. . X Y
. . . X Y
di queste 16, solo 5 possono essere quelle che possono terminare il
gioco in Y, altre 11 sono state rimosse dalla diagonale Y e sono
passate sulla diagonale successiva. Il numero delle pedine che non
possono essere ospitate in ogni diagonale è crescente e quasi
esponenziale (lo è asintoticamente), quindi tutta la faccenda diverge.
Ciao, Silv:o)

 almeno sei mosse, generando 12 pedine.
Mi pare che nel tuo ragionamento ci sia un bug.
Avevo iniziato con un ragionamento quasi identico, ma non ero arrivato alla
divergenza.
Parto dall'inizio:
Una pedina nella *diagonale* 1 (nella casella d'angolo).
La rimuovo e ne trovo 2 nella diagonale 2.
Le rimuovo entrambe e ne trovo 4 nella diagonale 3.
Le devo rimuovere tutte e quattro, e ne trovo 8 nella diagonale 4 (contro le
tue 12).
Ne mantengo ferme 4 e ne rimuovo 4: trovo 8 pedine nella diagonale 5.
Ne mantengo 5 e ne rimuovo 3: trovo 6 pedine nella diagonale 6, ...e ci
starebbero tutte.
IMO per giustificare la divergenza occorrono alcune considerazioni
aggiuntive, per esempio il fatto che nella prima riga ci sarà sempre una ed
una sola pedina (e altrettanto nella prima colonna).
Allora, quando considero la diagonale n, posso rimuovere la pedina in prima
riga (colonna), e quindi, rispetto al ragionamento precedente, aumentano le
pedine che entrano in diagonale n+1, oppure non la rimuovo, e nella n+1
diminuiscono gli spazi utili.
ciao
paolo

 ciao :) dario
Ecco una dimostrazione che sfrutta una simpatica tecnica
(credo di Conway) riadattata a partire da un altro problema analogo.
Diamo a ogni casella x,y il valore: F(x,y) = 1/2^(x + y)
e consideriamo la somma delle caselle occupate ad ogni turno:
Ad ogni mossa sparisce la pedina x,y e ne compaiono due in x+1,y
e x,y+1,
pertanto la differenza di valore del set di pedine è:
F(x+1,y)+F(x,y+1)-F(x,y) = 0 per ogni x,y
Per cui il totale è costante e siccome partiamo con una pedina in 1,1
tale valore è F(1,1)=1/4.
Per dimostrare che non esiste soluzione basta far vedere che se le sei
caselle d'angolo sono libere il totale è sempre <1/4.
Sappiamo che nella prima riga e colonna c'è sempre e solo una pedina;
Ci chiediamo qual è il massimo punteggio ottenibile lasciando libere
solo le sei d'angolo e occupandone una sola sulla 1° riga e colonna.
Tale valore massimo si ottiene coprendo tutte le infinite caselle,
meno le sei d'angolo, e sulla 1° riga e colonna coprendo le
caselle 1,4 e 4,1 che danno il maggior contributo alla somma
totale.
Disegnino chiarificatore: (x occupate, O libere)
.........
.........
Oxxxxx...
Oxxxxx...
xxxxxx...
Oxxxxx...
OOxxxx...
OOOxOO...
E risulta che tale somma, equivalente a:
sum F(x,y)  -F(2,2)+F(1,4)+F(4,1)
x,y>=2
vale proprio 1/4.
Perciò ogni insieme finito di pedine dà somma minore di 1/4 rendendo
il problema insolubile.
Ciao
Andrea