Colorazione dei naturali e cicciotti monocromatici

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Colorazione dei naturali e cicciotti monocromatici

Messaggio da edriv » 28 giu 2007, 12:35

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.

albert_K
Messaggi: 182
Iscritto il: 10 set 2006, 19:34
Contatta:

Messaggio da albert_K » 28 giu 2007, 15:38

Vorrei la dimostrazione di: $ \mathbb{N} $ è ciccione :lol:

Avatar utente
Zoidberg
Messaggi: 312
Iscritto il: 10 mar 2006, 15:41
Località: Pisa - Trebaseleghe (PD)
Contatta:

Messaggio da Zoidberg » 28 giu 2007, 16:17

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 :D
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.

albert_K
Messaggi: 182
Iscritto il: 10 set 2006, 19:34
Contatta:

Messaggio da albert_K » 28 giu 2007, 17:01

Se colori di verde, ad esempio, le potenze di due non riesci a determinare un d che maggiori la differenza tra due elementi consecutivi!

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 28 giu 2007, 17:58

Appunto. Seconda dimostrazione sbagliata (una è già stata cancellata)

Avanti il prossimo :lol:

Avatar utente
Zoidberg
Messaggi: 312
Iscritto il: 10 mar 2006, 15:41
Località: Pisa - Trebaseleghe (PD)
Contatta:

Messaggio da Zoidberg » 28 giu 2007, 18:02

hihi!
era una dimostrazione senza ambizioni!
Domani dopo l'orale ci penso seriamente! :D

Hammond
Messaggi: 110
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Messaggio da Hammond » 29 giu 2007, 17:01

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.

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 29 giu 2007, 17:38

Prendo $ ~ d(k_d - 1) + 1 $ naturali consecutivi, ne coloro $ ~ k_d - 1 $ consecutivi all'inizio, e ne coloro uno alla fine. Se d è abbastanza grande, questo non mi da nessun problema.

Fuori 3 :D
Un cumumo di cadaveri davanti alla collina dei cicciotti, chi sarà a conquistarla? 8)

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 29 giu 2007, 18:51

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?
"Sei la Barbara della situazione!" (Tap)

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 29 giu 2007, 19:07

Fuori 4! :D


Noooooooo non era un'alta soluzione uffa :cry: :cry: :cry: :cry: :cry: :cry:

albert_K
Messaggi: 182
Iscritto il: 10 set 2006, 19:34
Contatta:

Messaggio da albert_K » 29 giu 2007, 20:36

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.

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 29 giu 2007, 21:21

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

albert_K
Messaggi: 182
Iscritto il: 10 set 2006, 19:34
Contatta:

Messaggio da albert_K » 29 giu 2007, 21:46

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....

sgiangrag
Messaggi: 113
Iscritto il: 03 mag 2005, 13:37

Re: Colorazione dei naturali e cicciotti monocromatici

Messaggio da sgiangrag » 30 giu 2007, 09:12

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?

albert_K
Messaggi: 182
Iscritto il: 10 set 2006, 19:34
Contatta:

Messaggio da albert_K » 30 giu 2007, 11:25

albert_K ha scritto: Non ho capito perchè l'unione degli intervalli $ ~ [2^{2k}, 2^{2k+1}] $ è cicciotto pur contenendo intervalli arbitrariamente grandi....
Forse ora ho capito la definizione di cicciotto, ma per andare sul sicuro lo scrivo, così si scoprono eventuali altri malintesi....

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.

Rispondi