The invariance principle

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

The invariance principle

Messaggio da enomis_costa88 »

Come preannunciato in un'altro thread ho preparato una piccola lista di esercizi sugli invarianti (mi sono stupito anche io di quanti ne ho trovati..pensavo di faticare a trovarne 2 o 3) . Spero vivamente che risultino graditi (vista la scarsa attenzione riservata solitamente a combinatoria) e invito chiunque abbia delle idee a postarle.

Qualche esercizio preso dall'Engel:

1) inizio con gli interi positivi 1,..,4n-1
Mosse:in ogni mossa posso cancellare due interi e scrivere (una sola volta) la loro differenza.
Th:dopo 4n-2 passi avrò sempre almeno un'intero pari.

2)sia $ a_1,a_2,a_3...a_n $ una permutazione dell'n-upla 1,2,..,n dove n è dispari
TH: $ (a_1-1)(a_2-2)...(a_n-n) $è pari

3)ho a gettoni bianchi; b gettoni neri, c gettoni rossi.
Mosse: scegliere 2 gettoni diversi e ripiazzarli con uno del terzo colore
TH:se rimanesse solo un gettone dimostrare che il suo colore non dipende dallo svolgimento del gioco.

4)Ho una tabella rettangolare contenente interi positivi.
Mosse:-raddoppiare i numeri contenuti in una riga
-sottrarre uno ai numeri contenuti in una colonna.
TH: posso ottenere una tabella di 0?

5) questo starebbe benissimo anche in algebra..però ritengo opportuno seguire la "catalogazione" dell'Engel (è il numero 30 pagina 11 nel capitolo sugli invarianti)

solve the equation: $ ( x^2-3x+3)^2-3(x^2-3x+3)+3=x $

6)In un tavolo (cicolare) ci sono sedute 6 persone. Ciascuna ha i seguenti numeri di monetine:1,0,1,0,0,0(la prima una moneta, la seconda nessuna..)
Mosse: regalare una moneta a due vicini di posto.
Th:possono in un numero finito di mosse avere tutti le stesse monete?

Quanche altro esercizio preso dalle gare italiane:

7) Cesenatico 2001:
100 lampadine sono disposte a quadrato (10*10) alcune di esse sono spente altre accese.
Gli interruttori sono fatti in modo che cambiando di stato una lampadina si cambi anche tutta la sua riga e la sua colonna.
a) partendo da quali configurazioni è possibile accenderle tutte?
b)stesso ma con 81 lampadine disposte 9*9.

8 ) Cesenatico 1999:
Ho un reticolo rettangolare (m*n) di palafitte. Ogni palafitta ha sopra una capanna. Dalla palafitta di ogni capanna partono p ponti che la collegano alle capanne vicine (mai in diagonale, possibili 2 o più collegamenti tra capanne contigue, inaccettabili i "cappi"). Per quali valori di (m,n,p) si può collocare i ponti in modo che si possa raggiungere ogni capanna da qualsiasi altra?

Questi sono abbastanza semplici. Se li doveste finire sono graditi dei "rilanci"(spero anche da parte mia).

Buon lavoro.
Avatar utente
HumanTorch
Messaggi: 281
Iscritto il: 01 gen 1970, 01:00
Località: Tricase

Re: The invariance principle

Messaggio da HumanTorch »

enomis_costa88 ha scritto: 1) inizio con gli interi positivi 1,..,4n-1
Mosse:in ogni mossa posso cancellare due interi e scrivere (una sola volta) la loro differenza.
Th:dopo 4n-2 passi avrò sempre almeno un'intero pari.
Cancellando 2 numeri ne otteniamo 1, quindi dopo $ 4n-2 $ ne resterà uno solo. La differenza $ |a-b| $ ha la stessa parità della somma $ a+b $, quindi consideriamo quest'ultima. La somma totale dei numeri sulla lavagna è $ \frac{4n(4n-1)}{2}\equiv 0 $ (mod 2). L'ultimo numero sulla lavagna quindi sarà pari a $ 2n(4n-1) $, e sarà perciò pari, come lo è la differenza.
enomis_costa88 ha scritto:2)sia $ a_1,a_2,a_3...a_n $ una permutazione dell'n-upla 1,2,..,n dove n è dispari
TH: $ (a_1-1)(a_2-2)...(a_n-n) $è pari
Sia $ n=2m+1 $
Fra 1 e 2m ci sono tanti dispari quanto pari, quindi dobbiamo ordinare gli $ a_i $ alternando pari e dispari. Quindi $ a_1\equiv a_3\equiv..\equiv a_{2k+1}\equiv 0 $ mod 2, ovvero dobbiamo sistemare $ m $ numeri pari in $ m+1 $ posti: dovendo un posto rimanere scoperto, avremo almeno un j t.c. $ 2|a_j-j $
enomis_costa88 ha scritto:5) solve the equation: $ ( x^2-3x+3)^2-3(x^2-3x+3)+3=x $
Sia $ F(x)=x^2-3x+3 $.
Il discriminante di $ F(F(x)) $ è negativo, quindi il membro di sinistra è positivo, ergo anche x è positivo.
In $ [\frac{3}{2};\infty[ $ $ F(x) $ è continua e monotona crescente (poichè $ P(x+h)-P(h)=h(2x+h-3)+3>0 $ per $ x>\frac{3}{2} $, -e, fra parentesi, $ P'(x)=2x-3 $), quindi $ F(F(x)))=x\rightarrow $ $ (F)x=x $, verificando che ciò è vero per $ x=3 $ o $ x=1 $.
Lavorando su $ h\to 0 $ otteniamo un risultato analogo sull'intervallo $ [0;1,5[ $
Avendo due radici, tal teorema di Ruffini possiamo ricavare le restanti due.
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Re: The invariance principle

Messaggio da Boll »

enomis_costa88 ha scritto: 3)ho a gettoni bianchi; b gettoni neri, c gettoni rossi.
Mosse: scegliere 2 gettoni diversi e ripiazzarli con uno del terzo colore
TH:se rimanesse solo un gettone dimostrare che il suo colore non dipende dallo svolgimento del gioco.
La congruenza modulo 2 (la parità :D) è invariante nel gioco, o meglio, quantità che hanno diversa parità, continuano ad avere diversa parità, quantità che hanno uguale parità continuano ad avere uguale parità.

Quindi se si arriva a $ (1,0,0) $ evidentemente l'1 è la quantità che all'inizio aveva parità diversa dalle altre 2 (ammesso che esista e che si arrivi a $ (1,0,0) $)
Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info »

Ho fatto i primi 5, ma non ho proprio capito cosa c’entra l’invarianza con i numeri 2,4 e 5 (me lo spiegate plz?)…Scrivo la sol del 4, che mi ha lasciato un po’ a pensare...non grantisco nulla... cmq ottima iniziativa Enemis_Costa88! :D

Risposta: si… credo... quasi sempre! Se esiste uno 0 però tutti i numeri della colonna contenenti lo 0 devono essere già 0 in partenza…

- Notiamo che se esiste un numero uguale a 0, devono essere tutti uguali a 0 in quella colonna, altrimenti in quella colonna i numeri potrebbero solo aumentare; diminuire di 1 porterebbe la casella con 0 ad essere negativa e da un numero negativo le mosse non permettono di giungere a numeri positivi. Questa restrizione sarà necessaria per il seguito;

- Notiamo che se e possibile portare a termine il procedimento con un rettangolo 1Xn, è possibile anche per kXn. Infatti le ulteriori mosse che agiscono su altre colonne non potrebbero modificare una colonna già azzerata; quindi possiamo azzerare le colonne separatamente, osservando che mentre azzeriamo una colonna i numeri delle altre colonne non ancora azzerate possono solo aumentare ed in particolare rimarranno positivi;

- E sempre possibile azzerare un rettangolo 1X2. Supponiamo i due numeri siano a,b con a>b (condizione che si può porre moltiplicando a più volte o rinominando). Ora moltiplichiamo b più volte in modo da ottenere la condizione 2b > a [sempre con b<a]. Ora questo è stato posto perché a-k=2(b-k) -> k=2b-a. Così che diminuendo di 1 k volte i due valori otteniamo: [a,b] – [2(a-b),(a-b)], [2(a-b),2(a-b)],[0,0]. Notiamo che questo procedimento porta come passaggio intermedio da [a,b] a [2(a-b),2(a-b)], ovverosia rende uguali i 2 numeri (questa osservazione serve per il passo induttivo seguente);

- Ora la tabella 1Xn si ricava induttivamente. Si rendono prima di tutto uguali n-1 caselle con il passo induttivo e poi si trattano queste ultime come un numero solo, ovverosia ad ogni numero si applica sempre la stessa operazione: se si diminuisce di 1, diminuiscono tutti per forza, altrimenti se moltiplichiamo uno per 2 dobbiamo moltiplicare anche gli altri (n-1). In sostanza ci siamo ricondotti ad una tabella 2Xn e sappiamo allora arrivare ad n numeri tutti uguali. Da qui e facile azzerare tutto diminuendo più volte di 1;
Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 »

info ha scritto:Ho fatto i primi 5, ma non ho proprio capito cosa c’entra l’invarianza con i numeri 2,4 e 5 (me lo spiegate plz?)
visto che questi sono tutti già risolti..te lo spiego:

2) la parità di (a_n-n)...(a_1-1) è l'invariante.

4)un'invariante è la possibilità di rendere uguale a 0 una colonna e poi di rendere anche le altre indipendentemente dalle mosse fatte e poi ce n'è un'altro che tu non hai usato pienamente avendo indotto(nella tua soluzione si intravede come la possibilità di trattare come due numeri le colonne nel passo induttivo..vorrei dire che la definizione di invariante è piuttosto larga).

5)in questo c'è una soluzione un po' diversa (e un po' più elegante anche se non si evita qualche calcolo, un'accenno ad esso c'è in quella di Human quando dice f(f(x))=x ==>f(x)=x in questo caso mi pare che l'implicazione sia sbagliata - e comunque non dovete dimostrare una funzionale - però lavorandoci un po' su..) che sfrutta un'invariante un po' particolare..

La definizione data da Gobbino agli invarianti è la seguente:"un'invariante è una quantità semplice che non cambia o cambia in modo controllato"

Ps anche nell'ultimo potrebbero sorgere dei dubbi..ma per spiegare aspetto che qualcuno lo risolva.

Commenti:
@Human Torch: ok sulle soluzioni (anche se non ho seguito esattamente tutti i passaggi della 5..che mi pare un po' brutale insomma tirare fuori la continuità e la crescienza mi pare eccessivo :wink: comunque non mi pare dimostri un'implicazione - credo falsa almeno in quel verso..a verso opposto sarebbe vera, in ogni caso se per dimostrare quel verso dovete rovinarvi la vita con l'analisi.. - come detto su verificandola però nei due casi interessanti) nel quinto potresti dire tutte le soluzioni già che ci sei..

@Boll ok ci siamo..hai scritto anche la condizione necessaria perchè accada.

@info..qualche appunto:
1) il mio nick sarebbe enomis_costa88 e potete chiamarmi enomis; ec88 ; simone..ma Enemis non mi aveva mai chiamato nessuno :lol:
2)la risposta è sempre..lo 0 è escluso per ipotesi..si parla di interi positivi.
per il resto il quattro non era semplicissimo come gli altri quindi complimenti.

Buon lavoro e buona serata.
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

Bah, riguardo al 5, se non sono completamente ubriaco, io più che in Algebra ce lo vedo bene come esercizio di II media, dopo aver fatto Ruffini e divisione fra polinomi.

Quell'equazione ha tre radici in 1!!!!
Praticamente la prima cosa che si fa quando si vede un polinomio "brutto" è guardare se ha una radice in 1. Quello in particolare si riscrive dopo pochi conti come
$ (x-1)^3(x-3)=0 $

Sono andato anche a leggermi la soluzione dell'Engel e non capisco cosa c'entri con le invarianti...
Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 »

Boll ha scritto: Sono andato anche a leggermi la soluzione dell'Engel e non capisco cosa c'entri con le invarianti...
ok già che ci siamo scriviamola (tradotta un po' a modo mio..visto anche che era stata la mia stessa idea)..

sia h(x)=x^2-3x+3
sia g(x)=x

l'equazione diventa h(h(x))=x che è soddisfatta da h(x) per qualche valore particolare (non essendo h(h(x))-x=0 costante in 0 max 4 per ruffini)

voglio cercare almeno una funzione f che abbia solo punti fissi nelle 2 trasformazioni (posso vederle come mosse di un gioco) f(x) applicate in x sia una che due volte ovvero punti INVARIANTI.. ovvero quantità che cambiano in modo controllato.

una volta trovata una funzione di questo tipo essa soddisferà (sicuramente) la funzionale
f(f(x))=x per qualsiasi valore, inoltre la h(x) la soddisfa solo per max 4 valori particolari.

nei valori in cui f(x)=h(x)=x risulterà valida la funzionale anche per h(x)(almeno la precedente è valida se f(x)=g(x)=x che si verifica essere l'unico polinomio che ha solo punti invarianti nella trasformazione da f(x) a x;inoltre per quei valori particolari in cui h(x)=f(x)=x anche h(x) è invariante rispetto alla trasformazione h(x) applicata sia una che due volte).

è facile verificare che g(x) è polinomio che assume valori invarianti rispetto alla trasformazione f(x) (ove f(x) è stato precedentemente fissato a f(x)=g(x)=x) applicata sia una che due volte.

uguagliando x^2-3x+3=x ottengo x_1=3 e x_2=1

ora per il caro vecchio Paolo Ruffini - o se preferisco per divisione tra polinomi insomma tra h(h(x))-x e x^2-4x+3 - trovo (come già detto da Boll) gli altri due zeri(x_3=1 ;x_4=1).


PS so che può sembrare un strano come invariante (sopratutto perchè nell'engel non lo ha spiegato benissimo..anzi a dire il vero forse ho cambiato qualcosina) se dovessi essere stato un po' poco chiaro ditemelo.

PPS Boll non è completamente ubriaco.. questo stesso esercizino poteva essere bruciato osservando gli zeri banali, mi sembra solo più carino così.

Buona serata
Rispondi