Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 09-02-2011 15:39:40

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Nmbre d'expressions

On essaye régulièrement d'obtenir un nombre à l'aide d'opérations élémentaires et de d'opérandes (n'est ce pas ? )

1) Combien d'expressions différentes (même si elles sont égales après calcul) peut-on former avec n opérandes et k opérations (à deux paramètres, comme le sont + - / * ^ mod ...). NB : les parenthèses sont gratuites et utilisables à l'envi.

2) On ajoute la possibilité d'utiliser la concaténation, ou, ce qui revient au même, l'opération X#Y = 10X+Y, mais sans qu'elle compte dans les k opérations autorisées (tout pareil que dans le problème de Thedoums : ici)

Je crois que c'est trop dur...



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 11-02-2011 09:45:05

LeSingeMalicieux
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1298
Lieu: Haute-Marne

Nombre 'dexpressions

Je pense qu'on devrait pouvoir résoudre une partie du cas 1) à l'aide de la notation polonaise préfixée.

Dans cette notation, on place l'opérande à gauche des deux opérateurs.
Quelques exemples :
+ab équivaut à a+b
-c+ab équivaut à c - (a+b)
*+abc équivaut à (a+b) * c
/*cd+ab équivaut à (c*d) / (a+b)

Utilisons a, b, c, etc pour représenter des opérateurs quelconques et l'opérande +

Avec deux opérateurs, une seule expression possible :
+ab   soit a+b

Avec trois opérateurs, deux expressions possibles :
+a+bc   soit a + (b+c)
++abc   soit (a+b) + c

Avec quatre opérateurs, trois expressions possibles :
++ab+cd   soit (a+b) + (c+d)
+a+b+cd   soit a + (b + (c+d))
+++abcd   soit ((a+b) + c) + d

etc.

Maintenant, suivant le nombre d'opérandes utilisés (+, -, *, /, ^, etc), pour chaque cas cité ci-dessus, les possibilités croissent rapidement.

Ajoutons à cela qu'il faut ensuite se méfier des opérateurs qui représentent des fonctions non continues sur le domaine de définition (division par 0, racine d'un nombre négatif dans R, et j'en passe). La tâche devient très ardue !

Mais c'est sans doute une piste à creuser pour ceux qui ont un niveau bien supérieur au mien.


Avoir quatre mains, c'est plus pratique pour taper sur un clavier.

 #3 - 11-02-2011 16:58:30

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Nmbre d'expressions

Bien parti le Singe, mais ne te préoccupe pas des divisions par zéro, on veut juste le nombre d'expressions, même celle qui ne donnent pas de résultats.

En fait, l'idée est de savoir combien il faut faire d'essais si on veut résoudre un problème de type "le compte est bon" en essayant toutes les combinaisons, les combinaisons interdites étant des combinaisons quand même...

 #4 - 12-02-2011 13:34:09

LeSingeMalicieux
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1298
Lieu: Haute-Marne

Nombre d'expresssions

Tiens, je m'aperçois déjà que j'ai oublié deux écritures possibles avec quatre opérandes. On a en fait cinq possibilités :
+a+b+cd   soit a + (b + (c + d))
++ab+cd   soit (a+b) + (c + d)
+a++bcd   soit a + ((b + c) + d)
++a+bcd   soit (a + (b + c)) + d
+++abcd   soit ((a + b) + c) + d

En tout cas, avec n opérandes, on formera toujours des écritures avec n-1 opérateurs.

Sinon pour chaque écriture trouvée, on peut distribuer les n opérandes de n! façons.
par exemple, l'écriture +a+bc (qui utilise trois opérandes) peut différer de six (3!) façons :
+a+bc
+a+cb
+b+ac
+b+ca
+c+ab
+c+ba

Ensuite, pour chaque expression, suivant le nombre k d'opérateurs permis (+, -, *, /, etc), on aura donc k^(n-1) expressions différentes possibles.

Ce qui nous fait n! * k^(n-1) possibilités pour une seule écriture.



Ainsi :
- Pour n=2, on a une écriture possible (+ab), ce qui nous donne 1*2*k expressions différentes possibles.
- Pour n=3, deux écritures possibles (voir mon précédent post), ce qui nous donne 2*6*k² expressions différentes possibles.
- Pour n=4, cinq écritures possibles (sous réserve que j'en aie encore oubliées), soit 5*24*k^3 expressions possibles.
- etc


Qui a envie de généraliser ? smile


Avoir quatre mains, c'est plus pratique pour taper sur un clavier.

 #5 - 15-02-2011 11:58:48

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

nombrr d'expressions

Merci le Singe pour ta participation un peu isolée... cette question n'a pas enthousiasmé les foules on dirait...

Bon, on a [latex]n[/latex] opérandes noté [latex]a_1,...,a_n[/latex] et [latex]k[/latex] opérations notées [latex]*^1,...*^k[/latex] (on n'est pas obligé de tout utiliser), posons déjà [latex]p = \min(n,k+1)[/latex] et oublions les parenthèses un instant.

Une expression (sans parenthèses) sera de la forme :
[TeX]a_1 *^1 a_2... *^{p-1} a_p[/TeX]
et il y a [latex](n.(n-1)....(n-p+1)).(k.(k-1)....(k-p+2))[/latex] telles expressions, soit [latex]n!/(n-p)! \times k!/(k-p+1)![/latex]

venons-en aux parenthèses, il en faut deux par opérateurs : [latex](... *_i ...)[/latex] sauf les plus extérieures qu'on peut virer, soit [latex]2(p-1)-2 = 2p-4[/latex] parenthèses.

Le nombre de façon de distribuer [latex]2p-4[/latex] parenthèses, est le nombre de "mots de Dyck" de longueur [latex]2p-4[/latex] qui vaut précisément [latex]C_{p-2}[/latex] (le [latex]p-2[/latex]-ième nombre de Catalan, voir ici) et est défini par :
[TeX]C_{p-2}=\frac{(2p-4)!}{(p-2)! (p-1)!}[/TeX]
ce qui nous donne au total (et après quelques regroupements) :
[TeX](2p-4)!\times p.{n \choose p}\times (p-1) {k \choose (p-1)}[/TeX]
Voilà, histoire de clore ce sujet. Je laisse en suspens la possibilité de concaténer les opérandes.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
P2T
05-09-2015 Enigmes Mathématiques
P2T
20-06-2014 Enigmes Mathématiques
P2T
15-01-2011 Enigmes Mathématiques
P2T
25-01-2008 Enigmes Mathématiques
P2T
Tous premiers par Vasimolo
28-04-2011 Enigmes Mathématiques
P2T
03-10-2008 Enigmes Mathématiques
17-10-2010 Enigmes Mathématiques
P2T
Gateau 30+ indice par gabrielduflot
28-08-2010 Enigmes Mathématiques
P2T
20-09-2007 Enigmes Mathématiques

Mots clés des moteurs de recherche

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete