Colorazione dei naturali e cicciotti monocromatici
Colorazione dei naturali e cicciotti monocromatici
Sia A un sottoinsieme dei numeri naturali.
A si dice "cicciotto" se esiste un $ ~ d \in \mathbb{N} $ tale che per ogni $ ~ k \in \mathbb{N} $ esistono $ ~ a_1,a_2,\ldots,a_k $ elementi di A tali che $ ~ a_1 < a_2 < \ldots < a_k $ e $ ~ a_{i+1} - a_i \le d $ per ogni $ ~ 1 \le i < k $.
$ ~ \mathbb{N} $ non è solo cicciotto, ma anche ciccione.
Dimostriamo che se coloriamo $ ~ \mathbb{N} $ con finiti colori, esiste un insieme cicciotto monocromatico.
A si dice "cicciotto" se esiste un $ ~ d \in \mathbb{N} $ tale che per ogni $ ~ k \in \mathbb{N} $ esistono $ ~ a_1,a_2,\ldots,a_k $ elementi di A tali che $ ~ a_1 < a_2 < \ldots < a_k $ e $ ~ a_{i+1} - a_i \le d $ per ogni $ ~ 1 \le i < k $.
$ ~ \mathbb{N} $ non è solo cicciotto, ma anche ciccione.
Dimostriamo che se coloriamo $ ~ \mathbb{N} $ con finiti colori, esiste un insieme cicciotto monocromatico.
Se coloriamo $ \mathbb{N} $ con finiti colori, dato che l'insieme è infinito, ci sarà almeno un colore di cui sono colorati infiniti naturali.
Diciamo che sia il verde
Dato che ci sono infiniti numeri verdi, due verdi consecutivi devono avere distanza inferiore ad un certo $ ~d $.
Quindi l'insieme dei verdi è un sottoinsieme A infinito e monocromatico.
Diciamo che sia il verde
Dato che ci sono infiniti numeri verdi, due verdi consecutivi devono avere distanza inferiore ad un certo $ ~d $.
Quindi l'insieme dei verdi è un sottoinsieme A infinito e monocromatico.
Coloriamo i naturali con $ ~m $ colori diversi e supponiamo falsa la tesi: per ogni $ ~d $ esiste $ ~k_d $ tale che non esiste una sequenza di $ ~k_d $ elementi dello stesso colore 'abbastanza vicini'.
Allora in un qualsiasi insieme di $ ~d \cdot (k_d - 1) + 1 $ naturali consecutivi ce ne sono al massimo $ ~k_d - 1 $ di ciascun colore: in totale $ ~m \cdot (k_d - 1) $.
Se $ ~d > m $ risulta che alcuni naturali non sono stati colorati: assurdo.
Allora in un qualsiasi insieme di $ ~d \cdot (k_d - 1) + 1 $ naturali consecutivi ce ne sono al massimo $ ~k_d - 1 $ di ciascun colore: in totale $ ~m \cdot (k_d - 1) $.
Se $ ~d > m $ risulta che alcuni naturali non sono stati colorati: assurdo.
Definiamo obeso un sottoinsieme di N tale che per un qualche d esiste una serie infinita in esso contenuta:
$ a_1<a_2<\dots <a_k<\dots $ dove $ a_{i+1}-a_i\le d $
Definiamo magrolino un insieme non cicciotto.
E ora una cura dimagrante in omaggio a chiunque risponda alle seguenti domande:
A) se a un insieme obeso sottraggo un insieme magrolino, ottengo sempre un insieme obeso?
B) e' possibile partizionare un insieme obeso in infiniti insiemi obesi?
C) l'insieme dei numeri primi e' cicciotto?
$ a_1<a_2<\dots <a_k<\dots $ dove $ a_{i+1}-a_i\le d $
Definiamo magrolino un insieme non cicciotto.
E ora una cura dimagrante in omaggio a chiunque risponda alle seguenti domande:
A) se a un insieme obeso sottraggo un insieme magrolino, ottengo sempre un insieme obeso?
B) e' possibile partizionare un insieme obeso in infiniti insiemi obesi?
C) l'insieme dei numeri primi e' cicciotto?
"Sei la Barbara della situazione!" (Tap)
Sono ancora lontano dalla collina dei cicciotti.... comunque:
- Se un sottoinsieme è finito, allora è cicciotto.
- Un insieme obeso è un insieme cicciotto infinito.
- Un insieme magrolino è infinito
- Esistono partizioni di $ $\mathbb{N} $ in numero finito di sottoinsiemi tali che sono tutti magrolini eccetto uno che è obeso
- Un insieme magrolino può essere sottoinsieme di uno obeso; un insieme obeso non può essere sottoinsieme di uno magrolino
- Gli insiemi obesi e gli insiemi magrolini possono essere considerati delle successioni crescenti a valori interi positivi $ $ o_n $ e $ $ m_n $ tali che $ $ \Delta o_n $ è limitata mentre $ $ \Delta m_n $ è illimitata.
- Un insieme obeso può essere partizionato in infiniti sottoinsiemi magrolini.
(dim.: Esiste una biiezione tra $ $\mathbb{N} $ e l'insieme obeso; $ $\mathbb{N} $ è facilmente partizionabile in insiemi magrolini (infinite progressioni aritmetiche ad esempio).)
Per quanto riguarda i problemi di Piever:
1) e 2)
Credo che il primo implichi il secondo.
Infatti, supponiamo $ $ \mathbb{M} \subset \mathbb{O} $, allora, dimostrando che $ $ o_{n_k} $ è obesa se $ $ n_k $ è magrolina, partizioniamo $ $ \mathbb{O} $ con tutte le sottosuccessioni $ $ o_{n_k} $, distinte tra loro perchè lo sono le $ $ n_k $.
3)
L'insieme dei numeri primi è magrolino.
dim.: L'intervallo $ $ [(n+1)! + 2 , (n+1)! + n+1] $ contiene n numeri composti consecutivi, cioè $ $ \Delta p_n $ è illimitata.
- Se un sottoinsieme è finito, allora è cicciotto.
- Un insieme obeso è un insieme cicciotto infinito.
- Un insieme magrolino è infinito
- Esistono partizioni di $ $\mathbb{N} $ in numero finito di sottoinsiemi tali che sono tutti magrolini eccetto uno che è obeso
- Un insieme magrolino può essere sottoinsieme di uno obeso; un insieme obeso non può essere sottoinsieme di uno magrolino
- Gli insiemi obesi e gli insiemi magrolini possono essere considerati delle successioni crescenti a valori interi positivi $ $ o_n $ e $ $ m_n $ tali che $ $ \Delta o_n $ è limitata mentre $ $ \Delta m_n $ è illimitata.
- Un insieme obeso può essere partizionato in infiniti sottoinsiemi magrolini.
(dim.: Esiste una biiezione tra $ $\mathbb{N} $ e l'insieme obeso; $ $\mathbb{N} $ è facilmente partizionabile in insiemi magrolini (infinite progressioni aritmetiche ad esempio).)
Per quanto riguarda i problemi di Piever:
1) e 2)
Credo che il primo implichi il secondo.
Infatti, supponiamo $ $ \mathbb{M} \subset \mathbb{O} $, allora, dimostrando che $ $ o_{n_k} $ è obesa se $ $ n_k $ è magrolina, partizioniamo $ $ \mathbb{O} $ con tutte le sottosuccessioni $ $ o_{n_k} $, distinte tra loro perchè lo sono le $ $ n_k $.
3)
L'insieme dei numeri primi è magrolino.
dim.: L'intervallo $ $ [(n+1)! + 2 , (n+1)! + n+1] $ contiene n numeri composti consecutivi, cioè $ $ \Delta p_n $ è illimitata.
Argh... hai fatto un po' di confusione con le definizioni!
- Se un insieme è finito, allora è cicciotto.
---> falsissimo, io per ogni k chiedo k elementi distinti, quindi ogni insieme cicciotto è infinito
- Un insieme obeso è un insieme cicciotto infinito.
-----> vedi prima
- Un insieme magrolino è infinito
-----> un insieme finito è per forza magrolino... vedi prima
- Esistono partizioni di N in numero finito di sottoinsiemi tali che sono tutti magrolini eccetto uno che è obeso
-----> ok, basta prendere {1}, {2}, ..., {k} e poi {tutti quelli che restano}
- Un insieme magrolino può essere sottoinsieme di uno obeso; un insieme obeso non può essere sottoinsieme di uno magrolino
----> Perfetto!
- Un insieme obeso può essere partizionato in infiniti sottoinsiemi magrolini.
-----> ok, basta prendere un insieme per ogni singolo elemento, ma le progressioni aritmetiche non saranno mai magroline!
1) e 2) ---> non li ho capiti
3) ---> l'unione degli intervalli $ ~ [2^{2k}, 2^{2k+1}] $ è un insieme cicciotto, ma ha buchi arbitrariamente grandi
- Se un insieme è finito, allora è cicciotto.
---> falsissimo, io per ogni k chiedo k elementi distinti, quindi ogni insieme cicciotto è infinito
- Un insieme obeso è un insieme cicciotto infinito.
-----> vedi prima
- Un insieme magrolino è infinito
-----> un insieme finito è per forza magrolino... vedi prima
- Esistono partizioni di N in numero finito di sottoinsiemi tali che sono tutti magrolini eccetto uno che è obeso
-----> ok, basta prendere {1}, {2}, ..., {k} e poi {tutti quelli che restano}
- Un insieme magrolino può essere sottoinsieme di uno obeso; un insieme obeso non può essere sottoinsieme di uno magrolino
----> Perfetto!
- Un insieme obeso può essere partizionato in infiniti sottoinsiemi magrolini.
-----> ok, basta prendere un insieme per ogni singolo elemento, ma le progressioni aritmetiche non saranno mai magroline!
1) e 2) ---> non li ho capiti
3) ---> l'unione degli intervalli $ ~ [2^{2k}, 2^{2k+1}] $ è un insieme cicciotto, ma ha buchi arbitrariamente grandi
mmm...ehh?
Ok, ho frainteso la definizione, però mi sembrava più coerente.
A questo punto non capisco la differenza tra ciccioso e obeso .
Comunque...volevo scrivere progressioni GEOMETRICHE... sorry...
Non ho capito perchè l'unione degli intervalli $ ~ [2^{2k}, 2^{2k+1}] $ è cicciotto pur contenendo intervalli arbitrariamente grandi....
Ok, ho frainteso la definizione, però mi sembrava più coerente.
A questo punto non capisco la differenza tra ciccioso e obeso .
Comunque...volevo scrivere progressioni GEOMETRICHE... sorry...
Non ho capito perchè l'unione degli intervalli $ ~ [2^{2k}, 2^{2k+1}] $ è cicciotto pur contenendo intervalli arbitrariamente grandi....
Re: Colorazione dei naturali e cicciotti monocromatici
analizziamo i casi: o questo problema è troppo stupido, oppure io non ho capito un ***** del testo.
La condizione che esistano $ ~ a_1,a_2,\ldots,a_k $ elementi di A tali che $ ~ a_1 < a_2 < \ldots < a_k $ e $ ~ a_{i+1} - a_i \le d $ per ogni $ ~ 1 \le i < k $ si può sostituire con la condizione che esistano $ ~ a_k $ elementi di A, infatti $ ~ a_{i} \le a_k $ per ogni $ ~ 1 \le i < k $
la condizione che esiste un $ ~ d \in \mathbb{N} $ tale che vi siano le proprietà sopra elencate è sostituibile con la condizione che $ ~ a_k\le a_1+(k-1)d $. Quindi $ ~ a_k $ per ogni valore di $ ~k,d $ ha un valore massimo. Inoltre $ ~ a_1 < a_2 < \ldots < a_k $ dunque $ ~ a_1+(k-1)\le a_k $. Importante è invece la condizione che tutto ciò valga per ogni valore di $ ~ k \in \mathbb{N} $, infatti ciò vuol dire, dato che $ ~ a_1+(k-1)\le a_k $, non c'è un valore finito di $ ~ a_k $ di elementi del sottoinsieme A, quindi il sottoinsieme A contiene infiniti elementi. Se si colorano degli elementi con un un numero finito di colori colorando con ogni colore un numero finito di elementi si possono colorare solo un numero finito di elementi. Dato che A contiene inifiniti elementi esiste almeno un colore che è stato usato per colorare infiniti elementi, che possiamo raccogliere in un insieme cicciotto monocromatico. Tutto giusto?
La condizione che esistano $ ~ a_1,a_2,\ldots,a_k $ elementi di A tali che $ ~ a_1 < a_2 < \ldots < a_k $ e $ ~ a_{i+1} - a_i \le d $ per ogni $ ~ 1 \le i < k $ si può sostituire con la condizione che esistano $ ~ a_k $ elementi di A, infatti $ ~ a_{i} \le a_k $ per ogni $ ~ 1 \le i < k $
la condizione che esiste un $ ~ d \in \mathbb{N} $ tale che vi siano le proprietà sopra elencate è sostituibile con la condizione che $ ~ a_k\le a_1+(k-1)d $. Quindi $ ~ a_k $ per ogni valore di $ ~k,d $ ha un valore massimo. Inoltre $ ~ a_1 < a_2 < \ldots < a_k $ dunque $ ~ a_1+(k-1)\le a_k $. Importante è invece la condizione che tutto ciò valga per ogni valore di $ ~ k \in \mathbb{N} $, infatti ciò vuol dire, dato che $ ~ a_1+(k-1)\le a_k $, non c'è un valore finito di $ ~ a_k $ di elementi del sottoinsieme A, quindi il sottoinsieme A contiene infiniti elementi. Se si colorano degli elementi con un un numero finito di colori colorando con ogni colore un numero finito di elementi si possono colorare solo un numero finito di elementi. Dato che A contiene inifiniti elementi esiste almeno un colore che è stato usato per colorare infiniti elementi, che possiamo raccogliere in un insieme cicciotto monocromatico. Tutto giusto?
Forse ora ho capito la definizione di cicciotto, ma per andare sul sicuro lo scrivo, così si scoprono eventuali altri malintesi....albert_K ha scritto: Non ho capito perchè l'unione degli intervalli $ ~ [2^{2k}, 2^{2k+1}] $ è cicciotto pur contenendo intervalli arbitrariamente grandi....
Un insieme è cicciotto se contiene una successione strettamente crescente finita ma di lunghezza arbitraria , la cui successione differenza (quella che indicavo prima con $ $ \Delta $) è limitata da un d fissato.
Il fatto è che leggendo la definizione sembrava che gli $ $a_1, a_2 , \dots $ fossero gli elementi del cicciotto a partire dal primo...
Sicuramente era evidente che un insieme cicciotto è infinito, ma questo non influiva troppo sui lemmi che ho enunciato prima (a parte quelli che dicono esplicitamente: "un insieme finito è cicciotto" ).
Insieme cicciotto di Albert_K : $ $ C \subseteq \mathbb{N} $ tale che tutti i suoi elementi ordinati formino una successione crescente $ $ c_n $ tale che $ $ \Delta c_n $ è limitata.
Insieme obeso di Albert_K: Insieme cicciotto infinito.
Insieme magrolino di Albert_K: $ $ M \subseteq \mathbb{N} $ non cicciotto, ovvero tale che tutti i suoi elementi ordinati formino una successione crescente $ $ m_n $ tale che $ $ \Delta m_n $ è illimitata.