Pedine che si duplicano in un piano cartesiano
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Pedine che si duplicano in un piano cartesiano
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?
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"
---
"Chissa se la fanno anche da asporto"
Re: Pedine che si duplicano in un piano cartesiano
(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
$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
"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
"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
Re: Pedine che si duplicano in un piano cartesiano
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!
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!
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"
Re: Pedine che si duplicano in un piano cartesiano
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)}$.
$$\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!
Ultima modifica di cip999 il 26 giu 2015, 23:33, modificato 2 volte in totale.
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Re: Pedine che si duplicano in un piano cartesiano
@Talete: si, anche se forse con i post di sopra è ormai inutile dirlo xD
@cip999 giusto, era quella l'idea figa (anche se mi sa che c'è un typo nella formula della sommatoria)
E non siate pigri e fate i conti in 3D
@cip999 giusto, era quella l'idea figa (anche se mi sa che c'è un typo nella formula della sommatoria)
E non siate pigri e fate i conti in 3D
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
Re: Pedine che si duplicano in un piano cartesiano
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$.
Generalizzando come nel caso in $2D$ $k \rightarrow 2k-4$ nel caso $3D$ $k \rightarrow 6k-15$ .
PS: 100 messaggiii!!
$$ 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$.
Generalizzando come nel caso in $2D$ $k \rightarrow 2k-4$ nel caso $3D$ $k \rightarrow 6k-15$ .
PS: 100 messaggiii!!
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"
Re: Pedine che si duplicano in un piano cartesiano
Beh, ce n'erano almeno due...karlosson_sul_tetto ha scritto:(anche se mi sa che c'è un typo nella formula della sommatoria)
Cosa ci fa questo simbolo malefico in un topic di combinatoria?LucaMac ha scritto:$$\sum_{cyc}$$
Re: Pedine che si duplicano in un piano cartesiano
Come ho già detto in altri topic.
"TUTTO E' ALGEBRA"
"TUTTO E' ALGEBRA"
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"
Re: Pedine che si duplicano in un piano cartesiano
n00bLucaMac ha scritto:PS: 100 messaggiii!!
(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)
Re: Pedine che si duplicano in un piano cartesiano
...ingenui figli dell'estate...Drago96 ha scritto:n00bLucaMac ha scritto:PS: 100 messaggiii!!
(ma in realtà l'autore del topic ci batte entrambi insieme)
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Pedine che si duplicano in un piano cartesiano
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