Un peu de réflexion

Bonjour,

Je ne voudrais pas avoir l'air de râler, mais cela ne me semble pas un problème simple "de réflexion". D'où l'as-tu sorti ?.

Kanut TCHIBOZO a écrit:

Combien peut-on former ,à partir de l'ensemble{1,2,...,2006},3 sous-ensembles non vides,disjoints deux à deux tels que chaque sous-ensemble ne comporte pas deux entiers consécutifs?

Je comprends la question comme :
De combien de façon peut-on, à partir de l'ensemble{1,2,...,2006}, remplir 3 boîtes distinctes de façon à ce que :
- chaque boîte a un moins un élément
- aucun élément n'est répété
- deux nombres consécutifs ne cohabitent jamais dans une même boîte

De plus :
- je considère que l'union des boîtes ne doit pas nécessairement faire {1,2,...,2006} entier (énoncé peu clair sur ce sujet)
- je considère les répartitions {1} {2} {3} et {1} {3} {2} comme différentes. Si ce n'est pas le cas, il faut diviser par 6 mes résultats.

Alors :

1) Soit une boîte A, calculons le nombre de façons U(n) (U pour "Une") de mettre dans A des nombres (au moins 1) de [1,n] sans qu'il y en ait de consécutifs.

U(n) = U(n-1) // les remplissages avec [1,n-1] sont admissibles
+ U(n-2) // + les remplissages conformes de n-2 avec le nombre n en plus
+ 1 // le nombre n seul
Donc :
U(n) = U(n-1) + U(n-2) + 1
avec : U(0)=0 et U(1)= 1

Et donc (je passe les calculs classiques) :

U(n)= (2phi+1)/(phi+2) phi^n + (1-phi)/(phi+2) (-1/phi)^n - 1
avec phi = (1+racine(5))/2 nombre d'or

2) Soient deux boîtes A et B, calculons le nombre de façons D(n) (D pour "Deux") de mettre dans A et B des nombres (au moins 1 par boîte) de [1,n] sans qu'il y en ait de consécutifs.

D(n) = D(n-1) // les remplissages avec [1,n-1] sont admissibles
+ D(n-1)-D(n-2) // les remplissages de n-1 contenant n-1 en mettant n dans l'autre boite
+ 2D(n-2) // les remplissages de n-2 en mettant n dans A et dans B (2 cas)
+ 2U(n-1) // n seul dans A ou dans B

D(n) = 2D(n-1) + D(n-2) + 2U(n-1)
D(0) = 0
D(1) = 0
Si on pose V(n) = D(n)+2U(n)+1, on a :
V(n) = 2V(n-1) + V(n-2)

Et donc (je passe les calculs classiques) :

V(n) = (3a+1)/(2(a+1))a^n - (a-1)/(2(a+1))(-1/a)^n
avec a = 1 + racine(2)
D(n) = (3a+1)/(2(a+1))a^n - (a-1)/(2(a+1))(-1/a)^n - 2(2phi+1)/(phi+2) phi^n - 2(1-phi)/(phi+2) (-1/phi)^n + 1



3) Soient trois boîtes A, B et C, calculons le nombre de façons T(n) (T pour "Trois") de mettre dans A, B et C des nombres (au moins 1 par boîte) de [1,n] sans qu'il y en ait de consécutifs

T(n) = T(n-1) // les remplissages avec [1,n-1] sont admissibles
+ 2(T(n-1)-T(n-2)) // les remplissages de n-1 contenant n-1 en mettant n dans l'une des deux autres boites
+ 3T(n-2) // les remplissages de n-2 en mettant n dans A ou B ou C (3 cas)
+ 3D(n-1) // n seul dans A ou B ou C

T(n) = 3T(n-1) + T(n-2) + 3D(n-1)
T(0) = 0
T(1) = 0

Si on pose W(n) = T(n) + 3D(n) + 3U(n) + 1, on a :
W(n) = 3W(n-1) + W(n-2)
W(0) = 1
W(1) = 4

Et donc (je passe les calculs classiques) :

W(n) = (4b+1)/(3b+2) b^n - (b-1)/(3b+2) (-1/b)^n
b = (3 + racine(13))/2

T(n) = (4b+1)/(3b+2) b^n - (b-1)/(3b+2) (-1/b)^n
- 3(3a+1)/(2(a+1))a^n + 3(a-1)/(2(a+1))(-1/a)^n
+ 3(2phi+1)/(phi+2) phi^n + 3(1-phi)/(phi+2) (-1/phi)^n
- 1Avec :
a = 1 + racine(2)
b = (3 + racine(13))/2
phi = (1+racine(5))/2

L'application de cette formule donne bien :
T(0) = 0
T(1) = 0
T(2) = 0
T(3) = 6
T(4) = 42
T(5) = 210
T(6) = 894
T(7) = 3486
T(8) = 12882
T(9) = 45984
T(10) = 160392
T(11) = 550656
T(12) = 1869768
T(13) = 6299664
T(14) = 21107832
T(15) = 70444662
T(16) = 234429810

T(2006) ne me paraît pas intéressant à exprimer. Il est de l'ordre de 10^(2040,9), soit un nombre de 2041 chiffres.

Il y a peut-être une astuce évidente à côté de laquelle je suis passé, mais, au vu du résultat, j'en doute.

--
Patrick

Bonjour,

pco a écrit:

De plus :
- je considère que l'union des boîtes ne doit pas nécessairement faire {1,2,...,2006} entier (énoncé peu clair sur ce sujet)
- je considère les répartitions {1} {2} {3} et {1} {3} {2} comme différentes. Si ce n'est pas le cas, il faut diviser par 6 mes résultats.

Devant la complexité du problème avec mes hypothèses (mais je confirme ma solution ci dessus), je pense que Kanut TCHIBOZO doit considérer que tous les éléments de {1,2,...,2006} doivent impérativement être répartis (autrement dit : l'union des trois sous-ensembles fait exactement {1,2,...,2006}).

Dans ce cas, c'est vraiment plus simple :

T(n) = 2T(n-1) + 3D(n-1) avec T(0) = 0
D(n) = D(n-1) + 2U(n-1) avec D(0) = 0
U(1) = 1 et U(n) = 0 partout ailleurs.

Ce qui implique :
D(0) = D(1) = 0 et D(n) = 2 pour n > 1

T(0) = T(1) = T(2) = 0 et T(n) = 2T(n-1) + 6 pour n > 2

Donc T(n) = 6(2^(n-2) - 1) pour n > 2

Donc T(2006) = 6(2^2004 - 1) ou 2^2004-1 si on ne considère pas les boîtes comme distinctes.

--
Patrick
qui rappelle le besoin d'avoir des énoncés les plus clairs possibles

vs pouvez utiliser le principe des tiroirs ok
the pigeone hole principle

Bonjour,

dahbani a écrit:

vs pouvez utiliser le principe des tiroirs

Certes ...

Et cela donne comme résultat quand on n'exige pas la présence de tous les nombres :
T(n) = ... ?

Et cela donne comme résultat quand on exige la présence de tous les nombres :
T(n) = ... ?


--
Patrick

Salut,

pco, je pense que ta deuxième interprétation est la bonne. (et je trouve, bien sûr, le même résultat que toi (en fait au début j'avais 3*2^{n-1}, alors je me demandais ce qui clochait, mais c'est juste que j'avais oublié que les sous-ensembles devaient être non-vides ))

Ma méthode (peut-être la même que la tienne, je ne l'ai pas lue) :
Alors, en partant de 3, chaque élément k \geq 3 doit appartenir à l'un de ces deux ensembles : soit l'ensemble contenant k-2, soit l'ensemble ne contenant ni k-1 ni k-2.
Donc on a deux choix et le reste est clair.

Hello

mathman a écrit:

je pense que ta deuxième interprétation est la bonne

Avec le recul, je le pense aussi ...

mathman a écrit:

Ma méthode (peut-être la même que la tienne, je ne l'ai pas lue) :
Alors, en partant de 3, chaque élément k \geq 3 doit appartenir à l'un de ces deux ensembles : soit l'ensemble contenant k-2, soit l'ensemble ne contenant ni k-1 ni k-2.
Donc on a deux choix et le reste est clair.

Oui, bien sûr.
Ma méthode est légèrement moins directe (et surtout moins claire) parceque je l'ai faite après la résolution (monstrueuse) de la première interprétation, en utilisant les mêmes notations.

--
Patrick

Les trois sous-ensembles forment une partition de l'ensemble {1,2,...,2006} ( Réponse à Pco).