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

nombre d'expredsions

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 d'xepressions

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

nombre d'exoressions

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

Nombr d'expressions

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

Nombbre 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 : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
P2T
Des radis et un âne par clement.boulonne
29-08-2011 Enigmes Mathématiques
P2T
Gâteau 121 par Vasimolo
19-02-2016 Enigmes Mathématiques
26-09-2008 Enigmes Mathématiques
P2T
Magie 3 par Vasimolo
03-02-2012 Enigmes Mathématiques
P2T
Somme & produit par miss-alexia
30-03-2011 Enigmes Mathématiques
05-01-2011 Enigmes Mathématiques
25-10-2013 Enigmes Mathématiques
P2T
Suite logique par lerusse67
14-09-2013 Enigmes Mathématiques
03-05-2015 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