Ammorteeee!

Giochini matematici elementari ma non olimpici.
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Ammorteeee!

Messaggio da Gottinger95 »

Ah, per la numerabilità di \(\mathbb{N}^k\) mi è venuta un'idea carina. E' stato detto che se \(A \subseteq B\) e \(B\) è numerabile, allora \(A\) è numerabile.
Detti \(p_1, \ldots, p_k\) i primi \(k\) numeri primi, allora metto in corrispondenza biunivoca \((a_1, \ldots,a_k ) \in \mathbb{N}^k\) con \(p_1^{a_1} \cdot \ldots p_k ^{a_k}\). Visto che i numeri della forma \(p_1^{a_1} \cdot \ldots p_k ^{a_k}\) sono un sottoinsieme dei numeri naturali, sono anch'essi numerabili. Che sia biunivoca è naturale: ad ogni \(k\)-upla di naturali corrisponde un solo numero, e ad ogni numero divisibile solo per primi tra \(p_1, \ldots p_k\) corrisponde una sola \(k\)-upla di naturali.

A questo punto posso numerare tutto facilmente:
1.\((a_1, \ldots, a_k) \in \mathbb{Z}^k\) lo metto in corrispondenza biunivoca con \(\displaystyle (|a_1|, \ldots, |a_k|, \frac{sgn(a_1) + 1}{2}, \ldots, \frac{sgn(a_k)+1}{2}) \in \mathbb{N}^{2k}\);
2.\(\displaystyle (\frac{a_1}{b_1}, \ldots, \frac{a_k}{b_k}) \in \mathbb{Q}^k\) lo metto in corrispondenza biunivoca con \(\displaystyle (|a_1|, \ldots, |a_k|, |b_1|, \ldots, |b_k|, \frac{sgn(a_1/b_1)+1}{2}, \ldots, \frac{sgn(a_k / b_k)}{2}) \in \mathbb{N}^{3k}\).
3. Per l'insieme dei polinomi a coefficienti razionali, servono alcune piccole considerazioni. Nella dimostrazione della numerabilità di \(\mathbb{N}^k\), non abbiamo imposto limiti superiori su \(k\). Di fatto, anche prendendo un \(k\) ENORME, ho comunque sempre abbastanza primi. In particolare, anche un \(k\) infinito va bene, perchè i numeri primi sono infiniti. Sia \(Q_k[x]\) l'insieme polinomi a coefficienti razionali che ha al massimo grado \(k\). Dato
\(\displaystyle P(x) \in Q_n[x]\ |\ P(x) = \sum_{i=0}^{n} c_i x^i \)
posso metterlo in corrispondenza con \( (c_0, \ldots, c_n) \in \mathbb{Q}^{n+1}\), che può essere messo in corrispondenza biunivoca con \(\mathbb{N}^{3n+3}\). Dunque l'insieme dei polinomi di grado \(n\)-esimo è numerabile. Prendendo \(n\) sempre più grande, abbraccerò una classe di polinomi sempre più grande, e per \(n\) che va all'infinito abbraccerò tutti i polinomi a coefficienti razionali.
Per convincersene, basta accorgersi che preso un numero naturale qualsiasi che rispetti le condizioni per essere messo in corrispondenza con \(\mathbb{Q}^k\) (e lo si può fare in un modo solo), allora può essere messo in corrispondenza con un solo polinomio di grado \(k-1\); viceversa, ogni polinomio di grado \(k+1\) si può mettere in corrispondenza con una \(k\)-upla di numeri razionali, che a sua volta può essere messa in corrispondenza con uno e un solo numero naturale.

P.S. Ehm...il passaggio all'infinito l'ho fatto con molta indifferenza (e mettendoci parole suggestive come ENORME), ma non so se è giusto xD
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Ammorteeee!

Messaggio da fph »

In effetti il passaggio all'infinito secondo me detto così non funziona. :) Non hai un teorema in generale che ti dice che se gli insiemi $S_\alpha$ sono numerabili per ogni $\alpha \in A$, allora anche $\bigcup_{\alpha\in A} S_\alpha$ lo è. Questa proprietà è vera solo se $A$ è numerabile anch'esso. Potresti concludere al volo citando questo teorema.

Però a questo punto è più divertente provare a dimostrarlo:
bonus bonus question (non-elementary): se $A$ è numerabile e gli insiemi $S_\alpha$ sono numerabili per ogni $\alpha \in A$, allora anche $\bigcup_{\alpha\in A} S_\alpha$ è numerabile.

Sketch della dimostrazione: (1) ti basta fare il caso in cui $A=\mathbb{N}$ e $S_\alpha=\mathbb{N}$ per ogni $\alpha$ (perché?). (2) ti basta fare il caso in cui gli $S_\alpha$ sono disgiunti (perché?) (3) metti in corrispondenza l'elemento $k$ dell'insieme $S_\alpha$ con la coppia $(k,\alpha)\in\mathbb{N} \times \mathbb{N}$. Com'è questa corrispondenza? (4) concludi. Sai già dimostrare che $\mathbb{N}\times \mathbb{N}$ è numerabile, vero?

Altra bonus question: trova un controesempio rimuovendo l'ipotesi che $A$ è numerabile (ce n'è uno molto stupido).
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Ammorteeee!

Messaggio da Gottinger95 »

(1) Facciamo solo il caso in cui \(A = \mathbb{N}\), \(S_{\alpha} = \mathbb{N}\), perchè se \(A, S_{\alpha}\) sono numerabili, allora ognuno di essi può essere messo in corrispondenza biunivoca con \(\mathbb{N}\) (si potrebbe pure dire che in fondo cambio solo il nome agli elementi).
(2) Faccio solo il caso in cui gli \(S_{\alpha}\) sono disgiunti; se ci fosse un caso in cui \(S_{\alpha_1} \cap S_{\alpha_2} = C\), allora invece di considerare \(S_{\alpha_1}\) e \(S_{\alpha_2}\) considero \(S_{\alpha_1} \cup C\) e \(S_{\alpha_2} / C\): in questo modo \(S_{\alpha_1} \cup S_{\alpha_2}\) rimane invariato, ma ci si riconduce al caso in cui gli insiemi sono disgiunti.
(3) Metto in corrispondenza l'elemento \(k\) dell'insieme \(S_{\alpha}\) con il numero naturale \(2^k \cdot 3^{\alpha}\); questa corrispondenza è biunivoca, perchè ad ogni elemento di \(\bigcup_{\alpha \in A} S_{\alpha}\) corrisponde un solo numero della forma \(2^a 3^b\) (per l'ipotesi che siano disgiunti l'\(\alpha\) è unico, e una volta trovato l'\(\alpha\) il \(k\) è unico), e viceversa ad ogni numero della forma \(2^a 3^b\) corrisponde un solo elemento di \(\bigcup_{\alpha \in A} S_{\alpha}\).
(4) I numeri della forma \(2^a 3^b\) sono un sottoinsieme di \(\mathbb{N}\), e perciò anch'essi numerabili. Da questo segue che \(\bigcup_{\alpha \in A} S_{\alpha}\) è numerabile.

Beh, per il controesempio ce n'è uno molto molto stupido (che non so se è TROPPO stupido): \(A= \mathbb{R}\) (non numerabile), \(S_{\alpha} = \alpha\) (numerabile) \(\rightarrow \ \ \bigcup_{\alpha \in A} S_{\alpha} = \mathbb{R}\) non numerabile.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Ammorteeee!

Messaggio da fph »

Bene! Unico dettaglio, la costruzione del 2 devi farla nel caso più generale in cui tutti gli $S_\alpha$ potrebbero avere elementi comuni: nella pratica fai quel giochino prima per $\alpha=1$ se ha elementi comuni con $S_0$, poi per $\alpha=2$ se ha elementi comuni con $S_0 \cup S_1$, eccetera. E nel controesempio immagino tu intenda $S_\alpha=\{\alpha\}$, con le parentesi, ma è solo un typo.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Ammorteeee!

Messaggio da Gottinger95 »

Si, intendevo \(\{\alpha\}\). Per il punto (2) facciamo così: Sia \( S_{\alpha_1} \cap S_{\alpha_2} = C\) un intersezione non vuota di due \(S_{\alpha}\) per qualche \(\alpha_1, \alpha_2 \in A= \mathbb{N}\). Visto che in \(\mathbb{N}\) ho l'ordinamento, posso supporre \(\alpha_1 > \alpha_2\). Allora invece di \( S_{\alpha_1} , S_{\alpha_2}\) considero \(S_{\alpha_1} \) e \(S_{\alpha_2} / C\); in sostanza "accumulo" l'intersezione sull'insieme con l'\(\alpha\) maggiore. Ugualmente a prima, l'unione rimane invariata e gli insiemi sono disgiunti. Applicando questo procedimento su tutte le intersezioni a un certo punto finiranno, perchè in questo procedimento non genero nuove intersezioni (gli insiemi non hanno guadagnato elementi, anzi, ne possono perdere) e le intersezioni sono numerabili. Infatti \((\alpha_1, \alpha_2) \in A^2 = \mathbb{N}^2\), che già abbiamo dimostrato essere numerabile.

EDIT: ah, non avevo letto che già mi avevi suggerito come correggere il (2). Vabè, dovrebbe esser giusta anche così, seppure un po' più macchinosa.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: Ammorteeee!

Messaggio da maurizio43 »

Scusate se riesumo un gioco-quiz di febbraio in cui mi sono imbattuto solo adesso.

E' barare se si assume che 'bianco' si possa dire anche 'non nero' , e 'nero' si possa dire anche 'non bianco' ?

Se è lecito, allora il metodo più semplice dovrebbe essere questo :
Il N. 10 dice direttamente il colore del N.9 .
Il N. 9, se il suo colore pronunciato dal N. 10 che lo precede è lo stesso che lui vede sul numero seguente 8, dice direttamente quel 'colore',
se " " " " " N. 10 che lo precede è oppostro a quello che lui vede sul numero seguente 8, dice 'non colore' dell' 8
Il N. 8, e tutti gli altri in sequenza, si comportano analogamente, sfruttando l' informazione data sul loro colore da chi li precede.
In questa maniera si salvano sicuramente quelli dal N. 9 al N. 1, e anche il N.10 si può salvare, nell' ipotesi che 10 e 9 abbiano lo stesso colore.
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Ammorteeee!

Messaggio da EvaristeG »

E' barare se si assume che uno si salvi sia dicendo bianco che dicendo non bianco, come fai tu. In realtà, la formulazione corretta è che ogni nano possa dire solo un colore nient'altro (neanche avverbi, quindi neanche non).
Rispondi