OliForum Matematico

Un insieme $ A $ di numeri interi è detto non isolato se, per ogni $ a \in A $ almeno uno dei numeri $ {a-1} $ e $ {a+1} $ appartiene anch'esso ad $ A $. Quanti sono i sottinsiemi non isolati di 5 elementi dell'insieme $ \{1,2,\dots,10\} $.

Generalizzazioni:

1) Quanti sono i sottinsiemi non isolati di $ \left\{1,2,\dots,n\right\} $ di cardinalità 5.

2) Quanti sono i sottinsiemi non isolati di $ \left\{1,2,\dots,n\right\} $ di cardinalità $ {k} $.

3) Quanti sono i sottinsiemi non isolati di $ \left\{1,2,\dots,n\right\} $.

quesito 0
5=2+3
se scelgo (1,2) le terneconsecutive sono nell'insieme (4, 5...10) e sono (10-6+1)=5. se scelgo (2,3) le terne sono nell'insieme (5, 6..10) e sono (10-7+1)=4.e cosi via. se scelgo (3,4) sono 3. se scelgo (4,5) sono 2. se scelgo (5,6) sono due dato che posso sempre scegliere anche (1,2,3). con (6,7) sono ancora 2. e adesso si risale, (7.8 )=3, (8,9)=4, (9, 10)=5. questo fatto è dato dalla simmetricità.
5=5+0
le conquine consecutive sono (10-5+1)=6
in totale sono 2(2+3+4+5)+2+6=36.

quesito 1
5=2+3
analogamente, con (1,2) ne sono (n-5), poi si scende fino a (n-8 ) , per ovvi motivi rimane costante, e poi si risale fino a (n-5), per un totale di (n-1) addendi..
5=5+0 le cinquine sono n+1-5=n-4.
in totale sono 2( n-5 + n-6 + n-7) + (n-7)(n-8 ) + (n-4)= $ (n-4)^2 $.

quesito 2
fammici pensare.. ma non mi pare per niente banale, per ogni n infatti p(1)=0, p(2)=n-1, p(3)=n-2, p(5)=(n-4)^2, p(i)=0 per ogni i>[n/3]...

quesito tre
Proviamo per ricorsione
sia $ ~k_i $ il numero di sottoinsiemi non isolati di un insieme di cardinalità i

se nel sottoinsieme c'è n ci deve essere n-1 quindi possiamo formare in totale $ k_{n-2} $ sottoinsiemi
se non c'è n abbiamo in totale $ k_{n-1} $

quindi direi che vale
$ k_n=k_{n-1}+k_{n-2} $

Ora, si ha $ k_1=0 $ e $ k_2=1 $ quindi direi che $ k_n=F_{n-1} $ (F è il numero di Fibonacci)

Problema 2.

Dato un intero n, una k-scomposizione di n è una k-upla di interi positivi $ ~ a_1,\ldots,a_k $ tali che $ ~ a_1 + \ldots + a_k = n $.
Lascio a voi dimostrare che un n ha $ ~ {n-1 \choose k-1} $ k-scomposizioni.

Prendiamo m caselle ordinate e coloriamone a in nero.
A seconda di come sono disposte quelle nere, troviamo una scomposizione di a, e a seconda di come sono disposte quelle bianche, troviamo una scomposizione di m-a. (dividendo le caselle bianche/nere in blocchi adiacenti)
La cosa interessante è che il numero di elementi in cui è scomposto a è circa uguale a quello in cui è scomposto m-a. Cioè, la loro differenza può essere al più 1. Se quelle nere sono scomposte in più parti, vuol dire che la prima e l'ultima casella sono nere. Se sono scomposte nello stesso numero di parti, posso scegliere il colore da cui iniziare.

Insomma, un sottoinsieme di {1,...,m} lo scrivo univocamente come:
un intero a tra 0 ed m (caselle bianche), un intero k tra 1 ed a, una k-scomposizione di a, e poi, alternativamente:
- una k-1 o k+1-scomposizione di m-a
- una k-scomposizione di m-a e un elemento di {0,1} (cioè con che colore iniziare)

Ora ci chiediamo in quanti modi possiamo colorare di nero {1,...,m} in modo che le caselle nere siano a, e scomposte in k parti. È equivalente a scegliere una k-scomposizione di a e, a scelta:
- una k-1 o k+1 -scomposizione di m-a
- una k-scomposizione di m-a ed un elemento di {0,1}
che si scelgono in $ \displaystyle {m-a-1 \choose k-2} + {m-a-1 \choose k} + 2{m-a-1 \choose k-1} $ che, usando le proprietà dei binomiali, fa:
$ \displaystyle {m-a+1 \choose k} $
Insomma, possiamo farlo in:
$ \displaystyle {a-1 \choose k-1} {m-a+1 \choose k} $
(casi limite a parte, aggiungerei...)

Se ho colorato di nero a caselle di {1,...,m}, che restano divise in k blocchi, allora posso aggiungere una casella ad ogni blocco, ottenendo una colorazione di {1,...,m+k} divisa ancora in k blocchi, ma che è non isolata, ed inoltre da una colorazione non isolata posso togliere una casella nera da ogni blocco, senza perdere l'informazione sul numero di blocchi!

Ora cerchiamo le colorazioni non isolate di {1,...,n} con k caselle nere. Facendo questo ragionamento sono:
$ \displaystyle \sum_{i=1}^n {k-i-1 \choose i-1}{n-k+1 \choose i} $
(casi estremi a parte, annullando i binomiali senza senso, e a meno di qualche costante variabile)

La formula fa schifo (non più della mia spiegazione), poi non so se si può esprimere senza sommatoria.

salva90 ha scritto:quesito tre
Proviamo per ricorsione ....

se nel sottoinsieme c'è n ci deve essere n-1 quindi possiamo formare in totale $ k_{n-2} $ sottoinsiemi

L'affermazione

se nel sottoinsieme c'è n ci deve essere n-1 quindi possiamo formare in totale $ k_{n-2} $ sottoinsiemi

non mi convince. Se in A vi sono n ed n-1 l'elemento n-2 potrebbe anche essere isolato. Mi spiego con un esempio

$ \left\{1,2,4,5,6\right\} $

è un sottinsieme non isolato di $ \left\{1,2,3,4,5,6\right\} $ però $ \left\{1,2,4\right\} $ non è non isolato in $ \left\{1,2,3,4\right\} $

vero. appena o tempo la sistemo. la mia paura è che venga una ricorsione ulteriormente più brutta

ercole, potresti dire quanto son belle le formule di 2) e 3)?

Io avrei un bound sul numero di sommatorie che vale rispettivamente 1,2.

edriv ha scritto:ercole, potresti dire quanto son belle le formule di 2) e 3)?

Io avrei un bound sul numero di sommatorie che vale rispettivamente 1,2.

La domanda 1 è stata assegnata nella gara Baltic Way 2007 (problema , le altre domande le ho inventate io ma non conosco la soluzione.

Piuttosto non ho ben compreso la tua soluzione del problema 2. Ma domani la leggerò con più attenzione.

Ercole

ercole ha scritto: le altre domande le ho inventate io ma non conosco la soluzione.

maledetto!

Comunque non ti consiglio di leggere la mia pseudosoluzione.
L'idea è solo questa:
- calcolare quanti sono i sottoinsiemi di {1,...,m} con a elementi che si dividono in k blocchi di numeri consecutivi
- osservare che ogni sottoinsieme non isolato si ottiene in modo unico a partire da un altro insieme (con meno elementi e lo stesso numero di blocchi), aggiungendo un elemento in mezzo ad ogni blocco.
Per blocco si intende che {3,4,5,7,9,10,23} è diviso nei blocchi {3,4,5},{7},{9,10},{23}.