Ammorteeee!

Giochini matematici elementari ma non olimpici.
Avatar utente
simone256
Messaggi: 452
Iscritto il: 07 mag 2012, 16:10
Località: Crema

Re: Ammorteeee!

Messaggio da simone256 » 01 mar 2013, 16:12

jordan ha scritto: In ordine:

1) Come dimostri che l'insieme degli interi pari positivi è numerabile?

2) Come dimostri che l'insieme degli interi è numerabile?

3) Come dimostri che l'insieme degli interi pari è numerabile?

4) Come dimostri che l'insieme dei razionali positivi è numerabile?

5) Come dimostri che l'insieme dei razionali è numerabile?


Ps. Non è quello per cui è nato il problema, nè la sezione giusta, ma sapere queste cose non fa sicuro male!
1) Ad ogni numero pari positivo $ 2n $ associo il numero naturale $ n $

2) Ad ogni numero naturale $ n $ associo $ (-1)^n \lceil\frac{n}{2}\rceil $

3) Ad ogni numero naturale $ n $ associo l'intero pari $ 2(-1)^n \lceil\frac{n}{2}\rceil $

E qui comincio a usare "due volte" variabili naturali:

4) Ad ogni numero coppia di numeri naturali $ n $, $ d $ associo il razionale positivo $ \displaystyle\frac{n}{d} $ (qui posso semplicemente dire di escludere frazioni uguali e che $ d $ debba essere diverso da $ 0 $?)

5) Ad ogni numero coppia di numeri naturali $ n $, $ d $ associo il razionale $ \displaystyle \frac{n}{(-1)^n \lceil\frac{n}{2}\rceil} $

Boh... :|
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.


$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo

Avatar utente
jordan
Messaggi: 3972
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Ammorteeee!

Messaggio da jordan » 02 mar 2013, 14:54

simone256 ha scritto:1) Ad ogni numero pari positivo $ 2n $ associo il numero naturale $ n $

2) Ad ogni numero naturale $ n $ associo $ (-1)^n \lceil\frac{n}{2}\rceil $

3) Ad ogni numero naturale $ n $ associo l'intero pari $ 2(-1)^n \lceil\frac{n}{2}\rceil $
Ok, dovresti essere convinto ora che almeno la 2) e la 3) sono funzioni biettive. Riguardo la 1), $0$ è un numero naturale, e non viene associato ad alcun intero positivo pari (anche se, ci vuole poco a correggere).

Piu' in generale, una volta che hai dimostrato che dati due insiemi non finiti $A \subseteq B$ tale che $B$ è numerabile, allora anche $A$ è numerabile (E' vero? Corollario: la domanda 5 implica tutte le altre..)

simone256 ha scritto:E qui comincio a usare "due volte" variabili naturali:

4) Ad ogni numero coppia di numeri naturali $ n $, $ d $ associo il razionale positivo $ \displaystyle\frac{n}{d} $ (qui posso semplicemente dire di escludere frazioni uguali e che $ d $ debba essere diverso da $ 0 $?)

5) Ad ogni numero coppia di numeri naturali $ n $, $ d $ associo il razionale $ \displaystyle \frac{n}{(-1)^n \lceil\frac{n}{2}\rceil} $
No, non ci siamo qui, non puoi usare coppie di numeri naturali. Come prima devi soltanto creare una funzione biettiva tra l'insieme richiesto e $\mathbb{N}:=\{0,1,2,\ldots\}$.

Sarebbe anche sufficiente che mostri che $\mathbb{N}^k$ è numerabile per ogni intero $k\ge 1$, e poi dire perchè è sufficiente..
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3972
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Ammorteeee!

Messaggio da jordan » 02 mar 2013, 14:56

Tornando in topic, non ho ancora risolto il problema dei cappelli con infiniti condannati; qualcuno ha avuto qualche idea?
The only goal of science is the honor of the human spirit.

_Ipazia_
Messaggi: 50
Iscritto il: 23 feb 2013, 15:23

Re: Numerabilità

Messaggio da _Ipazia_ » 02 mar 2013, 16:46

jordan ha scritto: 4) Come dimostri che l'insieme dei razionali positivi è numerabile?
Io qui assocerei semplicemente alla sequenza dei numeri naturali
$ N=(1,2,3..) $
la sequenza dei numeri razionali $ n/d $, $ n $ e $ d $ interi, ordinandoli mettendo prima i razionali la cui somma $ n+d $ è minore, a parità di somma mettendo prima i razionali con $ d $ minore, a parità di $ d $ prima i razionali il cui $ n $ è minore. Da questa sequenza toglierei tutti i razionali in cui $ n $ e $ d $ non sono primi tra loro e tutti i razionali in cui $ d=0 $. Avendoli ordinati quindi è possibile associare a ciascun razionale un numero naturale, contando la posizione che occupa nella sequenza ordinata. Però non credo che si possa dimostrare solo così, infatti non ho trovato nessuna formula con cui partendo da un numero naturale posso trovare il corrispettivo razionale..(sarebbe molto più facile se non ci fossero da togliere tutte le frazioni equivalenti :( )
jordan ha scritto:Tornando in topic, non ho ancora risolto il problema dei cappelli con infiniti condannati; qualcuno ha avuto qualche idea?
Io sono solo arrivata a notare che dividendoli in gruppi in cui il primo del gruppo salva tutti gli altri si possano salvare infiniti condannati, ma non se ne salverebbero altrettanti.. eppure il rapporto dei non salvati potrebbe essere piccolissimo..
“SE ASCOLTO DIMENTICO, SE GUARDO IMPARO, SE FACCIO CAPISCO”

Avatar utente
jordan
Messaggi: 3972
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Numerabilità

Messaggio da jordan » 02 mar 2013, 17:49

_Ipazia_ ha scritto:sarebbe molto più facile se non ci fossero da togliere tutte le frazioni equivalenti
Se dimostri che l'insieme è numerabile quando contiene anche altre frazioni "equivalenti", allori dimostri qualcosa di piu' forte, no?
The only goal of science is the honor of the human spirit.

_Ipazia_
Messaggi: 50
Iscritto il: 23 feb 2013, 15:23

Re: Numerabilità

Messaggio da _Ipazia_ » 03 mar 2013, 16:05

jordan ha scritto:
_Ipazia_ ha scritto:sarebbe molto più facile se non ci fossero da togliere tutte le frazioni equivalenti
Se dimostri che l'insieme è numerabile quando contiene anche altre frazioni "equivalenti", allori dimostri qualcosa di piu' forte, no?
Si ma trovando una funzione che associa a ogni numero naturale un razionale, se ci fossero le frazioni equivalenti la funzione non sarebbe più biiettiva, o no?


Comunque provo a scrivere questa "funzione" considerando solo l'intervallo da 0 a 1 di Q, dato che se un insieme è numerabile lo è anche un suo sottoinsieme infinito (vale anche il contrario vero? :shock: )
Ho ordinato i razionali in questo modo:
$ N(n): 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , ... $
$ Q(q): 0 , \frac{1}{1} , \frac{1}{2}, \frac{2}{2} , \frac{1}{3}, \frac{2}{3} , \frac{3}{3}, \frac{1}{4} , ... $
Osservando i denominatori, noto che quando nella sequenza cambia il denominatore (cioè al numero naturale 2, al 4, al 7, all'11..), il corrispondente n è dato da:
(indico con d il denominatore)
$ n=\frac{d(d+1)}{2} $
quindi trovo d:
$ d_{1,2}=\frac{-1\pm\sqrt{1+8n}}{2} $
posso eliminare la soluzione con d negativo, dato che considero solo razionali positivi, quindi:
$ d=\frac{-1+\sqrt{1+8n}}{2} $
Quindi, facendo in modo che la formula valga per tutti gli n:
$ d=\lceil\frac{-1+\sqrt{1+8n}}{2}\rceil $
Per il numeratore (lo chiamo m) invece:
$ m=n-\frac{d(d-1)}{2} $
Ho così associato ad ogni numero naturale un razionale dell'intervallo [0,1], lasciando però le frazioni equivalenti e quelle con denominatore=0..
“SE ASCOLTO DIMENTICO, SE GUARDO IMPARO, SE FACCIO CAPISCO”

Avatar utente
simone256
Messaggi: 452
Iscritto il: 07 mag 2012, 16:10
Località: Crema

Re: Ammorteeee!

Messaggio da simone256 » 03 mar 2013, 16:54

jordan ha scritto:Sarebbe anche sufficiente che mostri che $ \mathbb{N}^k $ è numerabile per ogni intero $ k \ge 1 $, e poi dire perchè è sufficiente..
Ah ok chiaro! Ho capito come funziona la dimostrazione ma ora devo cercare di sparare fuori una legge analitica! D:
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.


$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo

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

Re: Ammorteeee!

Messaggio da karlosson_sul_tetto » 05 mar 2013, 20:19

Anche se probabilmente non interessa a nessuno, posto la mia soluzione per infiniti condannati:
Definizioni e imprecisioni varie(per far sembrare la soluzione pomposa. Se stai leggendo questo hai perso):
1) "Un prigioniero muore/non si salva/si sacrifica"= l'algoritmo NON garantisce la sua vita, ma potrebbe capitare che il colore detto corrisponde al proprio e quindi si salva
2) Sia $ \Omega $ l'insieme dei prigionieri che si salvano e $ \Psi $ di quelli che muoiono
3) Fatto su cui gira la dimostrazione: il primo prigioniero NON può dare l'informazione per tutti gli altri prigionieri (non solo considerando la somma: se ci fosse un altro modo, l'informazione data dal primo è limitata mentre l'informazione su "tutti" è infinita)[Ovviamente se questo pseudo-assioma è falso crolla tutto]
4) Sia $ n $ il numero di prigionieri su cui il primo può dare/dà un informazione
5) Sia $ k $ il numero di colori
6) Sia $ N $ l'insieme dei prigionieri che NON ottengono l'informazione dal primo prigioniero .

Presuppongo di aver trovato un algoritmo funzionante. Distinguo tre casi:
1) $ \Psi $ è infinito
2) $ \Psi $ ha un solo elemento, ovvero il primo prigioniero.
3) $ \Psi $ ha più di un elemento, ma è limitato

Caso №1:
Banalmente, si può riutilizzare l'algoritmo per un numero di prigionieri limitato e fare in modo che il 1°, il $ (n+1) $°, il $ (n+2) $° si sacrifichino per dare l'informazione agli altri; in tal modo con $ n $ tendente a infinito $ \frac{|\Psi|}{|\Omega|} $ tende a $ 0 $.

Caso №2:
Siano $ X,Y \in N $ e $ a,b $ due "situazioni" (ovvero corrispondenza di colori per prigioniero) identiche tranne per $ X $ e $ Y $ (ovvero il colore del primo in $ a $ è uguale a quello del primo in $ b $, ecc.).
Notiamo che se esiste un siffatto algoritmo, tutti i prigionieri tranne $ X $ e $ Y $ diranno gli stessi colori, quindi in entrambi $ X_a $ può capire di trovarsi nel caso $ a $ solo grazie al colore detto dal 1°. Le possibili combinazioni di colori tra $ X $ e $ Y $ sono $ k^2 $, mentre il primo può dare un informazione per soli $ k $ casi, ovvero per il pigeonhole $ X $ e $ Y $ non possono capire in quale caso si trovano.

Caso №3:
Sia $ h $ il numero di prigionieri che si sacrificano. Prendiamo $ Z_1,Z_2,Z_3...Z_{h+1} \in N $. Analogamente al caso precedente, l'informazione data dai sacrificati "è" $ k^{h} $ mentre quella necessaria è $ k^{h+1} $, quindi questo caso non è possibile.

Spero sia corretta e decentemente comprensibile :)
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

Avatar utente
ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Re: Ammorteeee!

Messaggio da ndp15 » 05 mar 2013, 21:35

Era stato detto che si riusciva a salvarli tutti tranne il primo, non sprechiamo vite umane così a cuor leggero quindi. In particolare il fatto su cui gira la dimostrazione (cit.) è quindi falso (non sono andato avanti a leggere).
Comunque la soluzione che conosco usa qualche fatterello non elementare.

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

Re: Ammorteeee!

Messaggio da karlosson_sul_tetto » 05 mar 2013, 21:42

ndp15 ha scritto:Era stato detto che si riusciva a salvarli tutti tranne il primo, non sprechiamo vite umane così a cuor leggero quindi. In particolare il fatto su cui gira la dimostrazione (cit.) è quindi falso (non sono andato avanti a leggere).
Comunque la soluzione che conosco usa qualche fatterello non elementare.
D:
Per curiosità, perché(è falso)?
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

Avatar utente
ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Re: Ammorteeee!

Messaggio da ndp15 » 05 mar 2013, 21:53

karlosson_sul_tetto ha scritto: D:
Per curiosità, perché(è falso)?
Perché dire che c'è una soluzione in cui si salvano tutti tranne il primo equivale proprio a dire che con l'informazione di quanto detto dal primo condannato si innesta un procedimento in cui tutti gli altri si salvano.

Avatar utente
jordan
Messaggi: 3972
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Ammorteeee!

Messaggio da jordan » 27 mar 2013, 19:24

Sveliamo il mistero?
The only goal of science is the honor of the human spirit.

Avatar utente
ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Re: Ammorteeee!

Messaggio da ndp15 » 27 mar 2013, 21:00

jordan ha scritto:Sveliamo il mistero?
Copio e incollo da altro forum:"Possiamo vedere una disposizione dei nanetti come la rappresentazione in binario di un reale, con 0 indicato da un cappello nero ed 1 da un cappello bianco.

Poniamo la seguente relazione di equivalenza fra reali: a ~ b se, definitivamente, hanno la stessa rappresentazione in base due.

Una volta dimostrato che questa è una relazione di equivalenza otteniamo che l'insieme dei reali è partizionato in infinite classi di congruenza.

Per l'assioma della scelta (http://it.wikipedia.org/wiki/Assioma_della_scelta), possiamo prendere da ogni classe di congruenza un rappresentante privilegiato.

Ogni nanetto, guardando la stringa di fronte a sé, è in grado di capire in che classe di congruenza si trova la stringa intera, quindi conosce il rappresentante privilegiato di ogni classe. Il primo nanetto indica quindi (analogamente al caso finito) la parità del numero di cappelli neri fra i nanetti che hanno un cappello di colore diverso rispetto alla configurazione di cappelli del rappresentante privilegiato.

E' facile convincersi che, dal secondo in poi, tutti si salvano: ogni nano, poiché conosce il rappresentante privilegiato, è in grado di ricostruire se è uno dei nanetti con colore del cappello errato oppure no e di agire di conseguenza".

Avatar utente
jordan
Messaggi: 3972
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Ammorteeee!

Messaggio da jordan » 01 apr 2013, 13:56

Il che, funziona bene anche con un numero qualsiasi (finito) di colori.. :O
The only goal of science is the honor of the human spirit.

Avatar utente
Simo_the_wolf
Moderatore
Messaggi: 1014
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Re: Ammorteeee!

Messaggio da Simo_the_wolf » 22 apr 2013, 02:36

[modalità mne on]
Della versione infiniti prigionieri e 2 cappelli mi piace più la soluzione con l'ultrafiltro (che comunque richiede l'assioma della scelta e non è molto dissimile come soluzione a quella di prima):

Sia $s_{n} \equiv \sum_{k=2}^n x_k$ modulo $2$ dove $x_k =0$ se il $k$-esimo cappello è nero mentre $x_k=1$ se esso è bianco. $s_n$ è una successione a valori in $\{0,1\}$ e quindi posso prendere il limite lungo un ultrafiltro non principale (su $\mathbb{N}$; esso dipende solo dalla successione da un certo punto in poi. Sia $l$ questo limite e diciamo che il primo condannato dice $l$. A questo punto il secondo condannato vede solo i cappelli dal $3$ in poi e quindi sa che $s_n=x+s'_n$ dove $x$ è il suo cappello e $s'_n$ è la somma di tutti i cappelli che vede fino all'n-esimo. Prendendo il limite lungo lo stesso ultrafiltro di questa successione ottengo $l=x+l'$ da cui posso ricavare chi è $x$.

Allo stesso modo fanno gli altri. In questo modo posso risolvere il problema se ho una quantità non numerabile di colori, perché li indicizzo con $\mathbb{R} / \mathbb{Z}$ (in pratica faccio i reali mod 1) e poi li sommo e succede la stessa cosa.
[modalità mne off]

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite