Pedine che si duplicano in un piano cartesiano

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
karlosson_sul_tetto
Messaggi: 1439
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Pedine che si duplicano in un piano cartesiano

Messaggio da karlosson_sul_tetto » 26 giu 2015, 20:31

Abbiamo un certo numero $k$ di pedine nel piano cartesiano nel punto $(0,0)$; una mossa consiste nel prendere una pedina situata nel punto $(a,b)$, eliminarla e sostituirla con una pedina in $(a,b+1)$ e una in $(a+1,b)$. Vogliamo fare una serie di mosse in modo che su ogni punto del piano ci sia al massimo una pedina.
a) È possibile farlo per $k=3$?
b) È possibile farlo per $k=4$?
c) Se invece ci troviamo in uno spazio a 3 dimensioni, questa volta però partendo da una pedina $(a,b,c)$ mettere tre pedine in $(a+1,b,c)$, $(a,b+1,c)$, $(a,b,c+1)$, qual è il numero massimo di pedine che posso avere in $(0,0,0)$ all'inizio per riuscirci?
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

Talete
Messaggi: 744
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Pedine che si duplicano in un piano cartesiano

Messaggio da Talete » 26 giu 2015, 20:44

(a) Chiamo $M(x,y)$ la mossa applicata su $(x,y)$. Una successione che ci fa vincere con $k=3$ è:

$M(0,0)$, $M(1,0)$, $M(0,1)$, $M(0,0)$, $M(1,1)$.

Infatti dopo la prima mossa ho due pedine su $(0,0)$ e una su $(1,0)$ e su $(0,1)$. Dopo la seconda e la terza mossa ho due pedine su $(0,0)$ e su $(1,1)$, che con la quarta e la quinta mossa sposto in $(1,0)$, $(0,1)$, $(1,2)$ e $(2,1)$.

Ho come il presentimento che per $k=4$ non si possa fare... ;)

Dimmi se è giusto, almeno il punto (a)... cioè, dimmi se ho capito bene il testo :D
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

LucaMac
Messaggi: 178
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Re: Pedine che si duplicano in un piano cartesiano

Messaggio da LucaMac » 26 giu 2015, 22:10

Ehmm forse scrivo stupidagini, ma sia $M$ il massimo numero con cui si può vincere (ovviamente sei $V$ è l'insieme dei vincenti e $P$ dei perdenti si ha $V=\{ 1, \ldots , M \}$ e $P= \{ M+1, \ldots \ldots \} $ ).
Supponiamo di avere $k$ pedine.
Bisogna applicare necessariamente $k-1$ mosse alla casella $(0,0)$ e $k-2$ alle caselle $(1,0)$ e $(0,1)$ , trovandosi necessariamente con $2k-4$ pedine in $(1,1)$ . Ma allora se $k$ è vincente lo è anche $2k-4$. In particolare se $k=M$ si ha $2M-4 \leq M$ , allora $M \leq 4$. Ora se però $k=4$ si ha $2k-4=k$ e quindi "ci si ritrova infinite volte sempre con $4$ pedine nella casella $(r,r)$" non riuscendo a trovarsi con al più una pedina per casella.
Se $k=3$ basta applicare le mosse a $(0,0) ; (0,0) ; (1,0) ; (0,1) ; (1,1)$ .
Caso $3D$:
Ovviamente se un numero non funziona in $2D$ non funziona in $3D$ .
Per $k=2$ si può fare.
Dobbiamo vedere quindi solo $k=3$ ma ora non ho voglia, magari domani provo! :D
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"

cip999
Messaggi: 149
Iscritto il: 26 nov 2013, 14:44

Re: Pedine che si duplicano in un piano cartesiano

Messaggio da cip999 » 26 giu 2015, 22:39

Ma in realtà c'è quel bellissimo invariante dell'Engel: do alla pedina che si trova nella casella $(i, j)$ il peso $2^{-(i + j)}$. In questo modo il peso totale si conserva. Per $k = 4$ all'inizio il peso è pari a $4 \cdot 2^0 = 4$. Il peso massimo che si può avere con una pedina in ogni casella è
$$\sum_{i = 0}^{\infty} \left(\frac{1}{2^i}\sum_{j = 0}^{\infty} \frac{1}{2^j}\right) = \sum_{i = 0}^{\infty} \frac{1}{2^{i - 1}} = 4$$
E quindi a priori si potrebbe fare (a patto di arrivare a una configurazione con esattamente una pedina su ogni casella). Però notiamo subito che in tutta la riga $y = 0$ non potranno mai esserci più di $4$ pedine (anzi, ce ne saranno sempre esattamente $4$), e idem per la colonna $x = 0$. Quindi non si può. :(

In 3 dimensioni dovrebbe funzionare una cosa analoga in cui la pedina in $(i, j, k)$ ha peso $3^{-(i + j + k)}$.
LucaMac ha scritto:ma ora non ho voglia, magari domani provo!
:mrgreen:
Ultima modifica di cip999 il 26 giu 2015, 23:33, modificato 2 volte in totale.

Avatar utente
karlosson_sul_tetto
Messaggi: 1439
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Pedine che si duplicano in un piano cartesiano

Messaggio da karlosson_sul_tetto » 26 giu 2015, 22:48

@Talete: si, anche se forse con i post di sopra è ormai inutile dirlo xD
@cip999 giusto, era quella l'idea figa :D (anche se mi sa che c'è un typo nella formula della sommatoria)
E non siate pigri e fate i conti in 3D :lol:
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

LucaMac
Messaggi: 178
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Re: Pedine che si duplicano in un piano cartesiano

Messaggio da LucaMac » 26 giu 2015, 23:07

Dai, lo faccio ora , ogni riga per ogni passaggio:
$$ 3(0,0,0) $$ Ora obbligata:
$$ (0,0,0) + 2 \sum_{cyc}(1,0,0) $$ Ancora obbligata:
$$ (0,0,0) + \sum_{cyc} (1,0,0) + \sum_{cyc} (2,0,0) + 2 \sum_{cyc} (1,1,0) $$ Continua ad esserlo:
$$ (0,0,0) + \sum_{cyc} (1,0,0) + \sum_{cyc} (2,0,0) + \sum_{cyc} (1,1,0) + \sum_{sym} (2,1,0) + 3 \sum_{cyc} (1,1,1) $$
Arrivati quindi alla situazione di partenza con $(0,0,0) \rightarrow (1,1,1) $ analogamente al caso $2D$ con $4$ in $3D$ non si può con $3$. :D
Generalizzando come nel caso in $2D$ $k \rightarrow 2k-4$ nel caso $3D$ $k \rightarrow 6k-15$ .
PS: 100 messaggiii!! :D
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"

cip999
Messaggi: 149
Iscritto il: 26 nov 2013, 14:44

Re: Pedine che si duplicano in un piano cartesiano

Messaggio da cip999 » 26 giu 2015, 23:32

karlosson_sul_tetto ha scritto:(anche se mi sa che c'è un typo nella formula della sommatoria)
Beh, ce n'erano almeno due... :x :D
LucaMac ha scritto:$$\sum_{cyc}$$
Cosa ci fa questo simbolo malefico in un topic di combinatoria?

LucaMac
Messaggi: 178
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Re: Pedine che si duplicano in un piano cartesiano

Messaggio da LucaMac » 26 giu 2015, 23:34

Come ho già detto in altri topic.
"TUTTO E' ALGEBRA"
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"

Avatar utente
Drago96
Messaggi: 1145
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Pedine che si duplicano in un piano cartesiano

Messaggio da Drago96 » 26 giu 2015, 23:51

LucaMac ha scritto:PS: 100 messaggiii!! :D
n00b :P
(ma in realtà l'autore del topic ci batte entrambi insieme)

P.S: replico ancora con "il vero è l'intero"
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

EvaristeG
Site Admin
Messaggi: 4791
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Pedine che si duplicano in un piano cartesiano

Messaggio da EvaristeG » 06 lug 2015, 14:22

Drago96 ha scritto:
LucaMac ha scritto:PS: 100 messaggiii!! :D
n00b :P
(ma in realtà l'autore del topic ci batte entrambi insieme)
...ingenui figli dell'estate...

Gottinger95
Messaggi: 481
Iscritto il: 01 lug 2011, 22:52

Re: Pedine che si duplicano in un piano cartesiano

Messaggio da Gottinger95 » 21 lug 2015, 20:01

Sam non te fà il ganzo con i più piccoli
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe

Rispondi