Olympiades exo combinatoire

Olympiades mathématiques, énigmes et défis
beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 16:14

par beagle » 30 Jan 2014, 16:58

chan79 a écrit:peut-être pour compter avec deux permutations


on choisit deux nombres parmi les 10 (par exemple 1 et 5: ça donne les permutations 1-2 et 5-6 )
ils ne doivent pas être consécutifs d'où le -10


I agree.
Si on reprend la série de 0 et 1,
on place deux fois le 1 dans 10 trous, C(2,10)
les doublons sont pour chaque 1 placé il a un adjaccent horaire (ou antihoraire,mais on se fixe juste un coté), donc il faut enlever C(1,10)
ça marche!
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.



beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 16:14

par beagle » 30 Jan 2014, 17:55

Avec les séries de 1 et 0, c'est frisouille!
Les triples, je choisis dans C(3,10) et j'enlève les cas qui ne marchent pas:
les 111 accolés, ben c'est encore du C(1,10)
les 11 accolés avec l'autre 1 à distance
c'est du C(1,10) choisir le 11, fois 10-4= 6 emplacements pour le troisième 1
donc 6xC(1,10)

donc C(3,10)-7xC(1,10) = 120-70=50 cas
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 16:14

par beagle » 30 Jan 2014, 18:50

Pour les quadruples:
C(4,10)=210
on enlève les 1111 accolés, 1xC(1,10)
on enlève les 111 accolés 5xC(1,10)
on enlève les 11 accolés
il y a peut-ètre plus malin, mais comme je me suis gourré j'ai continué sur le mème schéma:
11 et les autres 1 sont non accolés:
C(1,10) x [C(2,6)-5)= 10xC(1,10)
11 et encore 11, c'est par exemple:
C(1,10) x 5 à diviser par 2 = 25

donc 210-16 (c1,10)-25= 25 quadruples

Bon alors, je suis à
1 pas de changements
10 permutations simples isolées
35 doubles
50 triples
25 quadruples
2 cinquuples

et les 2 vagues ou hola

les 125 cas de Chan, ouf!
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 16:14

par beagle » 30 Jan 2014, 19:01

Bonjour beagle,
pour les quadruples, te vexe pas , mais cela me fait pitié de te voir utiliser une méthode qui enlève 185 cas à 210.Tu pourrais pas calculer sans la soustraction,en positif directos, non?
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 16:14

par beagle » 30 Jan 2014, 19:29

suis pas vexé, donc toi tu calcules directement les séries:
1010101000
1010010100
1010100100
et tout se passe comme s'il y en avait 10, 10 et 10/2 quoi, c'est ça?
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 30 Jan 2014, 21:43

Sauf erreur, s'il y a chevaliers, il y a effectivement 2 types de solutions :
1) Les chevaliers se déplacent tous d'un cran vers la droite (ou la gauche) -> 2 solutions
2) Un certain nombre chevaliers échangent leur place avec le chevalier suivant (dans l'ordre trigo par exemple).
Pour fixé (où est la partie entière), on cherche donc le nombre de -uplets tels que pour tout et, dans le cas où , on doit aussi avoir .
a) Si , on cherche donc tels que .
Il y a donc (coeff. binomial) solutions dans ce cas avec évidement une seule solution si .
b) Si , on cherche donc tels que .
Il y a donc solutions et il faut évidement que dans ce cas.

Au total, il y a donc permutations possibles.
On en déduit que , et en utilisant le fait que que, pour , on a :
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 16:14

par beagle » 30 Jan 2014, 22:10

Dans ces conditions je passe sélectioneur,
je choisis Ben314 pour les olympiades.

darkwoltech ne soit pas déçu, je te qualifie comme premier remplaçant.
Donc des fois où Ben314 se blesse avec un exo, tu auras ta place.
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

Avatar de l’utilisateur
chan79
Modérateur
Messages: 10330
Enregistré le: 04 Mar 2007, 21:39

par chan79 » 30 Jan 2014, 22:21

Ben314 a écrit:Sauf erreur, s'il y a chevaliers, il y a effectivement 2 types de solutions :
1) Les chevaliers se déplacent tous d'un cran vers la droite (ou la gauche) -> 2 solutions
2) Un certain nombre chevaliers échangent leur place avec le chevalier suivant (dans l'ordre trigo par exemple).
Pour fixé (où est la partie entière), on cherche donc le nombre de -uplets tels que pour tout et, dans le cas où , on doit aussi avoir .
a) Si , on cherche donc tels que .
Il y a donc (coeff. binomial) solutions dans ce cas avec évidement une seule solution si .
b) Si , on cherche donc tels que .
Il y a donc solutions et il faut évidement que dans ce cas.

Au total, il y a donc permutations possibles.
On en déduit que , et en utilisant le fait que que, pour , on a :


Bien vu !!!

Avatar de l’utilisateur
Darkwolftech
Membre Relatif
Messages: 140
Enregistré le: 11 Jan 2014, 20:42

par Darkwolftech » 31 Jan 2014, 21:16

Salut à tous

Merci beaucoup pour vos (nombreuses !!) réponses, je crois pouvoir m'en sortir :zen:

Dans ces conditions je passe sélectioneur,
je choisis Ben314 pour les olympiades.

darkwoltech ne soit pas déçu, je te qualifie comme premier remplaçant.
Donc des fois où Ben314 se blesse avec un exo, tu auras ta place.

Il est vrai que tu fais le bon choix Beagle en sélectionnant Ben314 pour les olympiades ! Perso à la lecture de sa preuve, ce fut plutôt ... violent et ... brutal (en fait j'étais un peu comme ça :eek:)

Merci encore ! :++:
Lucas

Avatar de l’utilisateur
chan79
Modérateur
Messages: 10330
Enregistré le: 04 Mar 2007, 21:39

par chan79 » 13 Fév 2014, 18:11

Salut
Question supplémentaire: Exprimer en fonction de :lol3:

Avatar de l’utilisateur
chan79
Modérateur
Messages: 10330
Enregistré le: 04 Mar 2007, 21:39

par chan79 » 17 Fév 2014, 10:58

On peut remarquer que , pour :



avec et

Avatar de l’utilisateur
Darkwolftech
Membre Relatif
Messages: 140
Enregistré le: 11 Jan 2014, 20:42

par Darkwolftech » 23 Fév 2014, 21:46

chan79 a écrit:On peut remarquer que , pour :



avec et


Tiens c'est vachement marrant ça !!! Tu saurais me l'expliquer de manière pas trop compliquée ?

Sourire_banane
Membre Irrationnel
Messages: 1355
Enregistré le: 23 Juil 2013, 13:48

par Sourire_banane » 23 Fév 2014, 22:22

Par récurrence non ?

Avatar de l’utilisateur
Darkwolftech
Membre Relatif
Messages: 140
Enregistré le: 11 Jan 2014, 20:42

par Darkwolftech » 24 Fév 2014, 12:03

Sourire_banane a écrit:Par récurrence non ?


Ok, mais la formule n'est pas tombée de nulle part comme ça non ? :we:

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 24 Fév 2014, 12:31

Sans faire trop de théorie... :

- Partant de tu commence par regarder si, en posant (k=cst) il n'y aurais pas moyen de se ramener à une vrai récurence linéaire, c'est à dire sans le -2 à la fin.
Comme on a :

Donc il suffit de prendre pour que ça marche.

- Ensuite, pour trouver l'expression de en fonction de , on commence par ne pas tenir compte des condition initiales, mais par chercher des suites le plus simple possible vérifiant la relation .
Si on "teste" une suite géométrique (avec et non nuls) on a :

Formule dans laquelle il n'y a plus de n.
Il n'y a plus qu'à résoudfre cette équation du second degrés dont les solutions sont les fameux et du post de chan79.
On constate ensuite que, non seulement les suites de la forme et vérifient , mais que les suites de la forme ( et constante réelles quelconques) vérifient aussi la formule.

- On termine en cherchant quelles valeurs prendre pour et pour de façon à ce que les valeurs initiales soient bien égales à ce qu'on veut (donc ici on veut que et )
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
Darkwolftech
Membre Relatif
Messages: 140
Enregistré le: 11 Jan 2014, 20:42

par Darkwolftech » 24 Fév 2014, 21:39

Ben314 a écrit:Sans faire trop de théorie... :

- Partant de tu commence par regarder si, en posant (k=cst) il n'y aurais pas moyen de se ramener à une vrai récurence linéaire, c'est à dire sans le -2 à la fin.
Comme on a :

Donc il suffit de prendre pour que ça marche.

- Ensuite, pour trouver l'expression de en fonction de , on commence par ne pas tenir compte des condition initiales, mais par chercher des suites le plus simple possible vérifiant la relation .
Si on "teste" une suite géométrique (avec et non nuls) on a :

Formule dans laquelle il n'y a plus de n.
Il n'y a plus qu'à résoudfre cette équation du second degrés dont les solutions sont les fameux et du post de chan79.
On constate ensuite que, non seulement les suites de la forme et vérifient , mais que les suites de la forme ( et constante réelles quelconques) vérifient aussi la formule.

- On termine en cherchant quelles valeurs prendre pour et pour de façon à ce que les valeurs initiales soient bien égales à ce qu'on veut (donc ici on veut que et )


Ah oui super ! :zen:
Merci beaucoup pour cette explication, c'est vrai que c'est une curiosité assez marrante ... on pourrait rapprocher ça de la suite de Fibonacci peut-être ?

Avatar de l’utilisateur
chan79
Modérateur
Messages: 10330
Enregistré le: 04 Mar 2007, 21:39

par chan79 » 25 Fév 2014, 00:35

Darkwolftech a écrit:Ah oui super ! :zen:
Merci beaucoup pour cette explication, c'est vrai que c'est une curiosité assez marrante ... on pourrait rapprocher ça de la suite de Fibonacci peut-être ?

Salut
Au vu de la formule de récurrence trouvée par Ben314, j'avais cherché à comparer avec un tableur la suite et la suite de Fibonacci.
Finalement, j'ai fait la conjecture que
Avec c=2, la relation de récurrence est vérifiée quels que soient a et b. (dès que n>2)
avec a=b=1, on a =6 et =9

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 14 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite