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 - 14-07-2015 09:01:09

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Racine carrée de fatcorielle

Bonjour à tous,
Montrer qu'on peut trouver une infinité de factorielles pouvant s'écrire sous la forme a*b, a>b, avec (a-b)/a plus petit que toute valeur fixée aussi petite que l'on veut.

Bon amusement.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 14-07-2015 10:26:50

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

racine carrée de factoriemle

Je suppose que tu veux dire que (a-b)/a doit être plus petit qu'une valeur donnée aussi petite que l'on veut .

Vasimolo

 #3 - 14-07-2015 11:52:35

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Racine acrrée de factorielle

Je suppose que tu veux dire que (a-b)/a doit être plus petit qu'une valeur donnée aussi petite que l'on veut .

Vasimolo

Oui Vasimolo, merci, j'ai corrigé.

 #4 - 14-07-2015 15:07:50

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

racine carrée de factorirlle

Bon premièrement n'importe quelles factorielles s'écrit sous la forme a*b.

Maintenant il faut vérifier la condition :

On sait tous que n!=n*(n-1)*...*2*1

Donc on prend a=n*(n-1)*...*(n-k+1) avec k la partie entière de n/2, pour b on prend le reste, et s'il n'y a pas de gonades dans le potage normalement ça devrait être bon.


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #5 - 14-07-2015 17:51:22

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

rzcine carrée de factorielle

Shadock,
Si je choisis la valeur 0,1, qui n'est pas bien contraignante, es tu sûr qu'avec ta méthode tu vas trouver une infinité de factorielles décomposées correctement ?

 #6 - 16-07-2015 01:24:52

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Racine carrée de facttorielle

Non lol


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #7 - 17-07-2015 08:19:05

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

racine carrée de faxtorielle

J'ajoute un indice: il y a une solution très simple en rapport avec la construction élémentaire de la factorielle.

 #8 - 17-07-2015 11:45:11

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2710
Lieu: Luxembourg

racine carrée de factorizlle

Euh ... il est où, l'indice ?

 #9 - 17-07-2015 12:15:19

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Rcine carrée de factorielle

Dans la phrase que j'ai écrite. Parfois, en disant que la solution est simple, ça ravive l'intérêt.
N'oublions pas par ailleurs que lorsque (b-a)/a tend vers 0, b/a tend vers 1....

 #10 - 17-07-2015 13:56:52

emmaenne
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3058
Lieu: Au sud du Nord

racine carrée fe factorielle

Moi, je n'ai pas compris ce qu'il faut faire.


Dans le cadre de la quinzaine du beau langage, ne disez pas disez, disez dites. (Julos Beaucarne)

 #11 - 17-07-2015 19:41:58

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Racine carrée de facorielle

L'énoncé, exprimé plus simplement, dit qu'on peut écrire une infinité de factorielles sous la forme n!=a*b d'un produit de 2 facteurs aussi proches qu'on veut l'un de l'autre (proximité relative, et non absolue).

 #12 - 17-07-2015 19:48:20

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

racine carrée de dactorielle

(b-a)/a tend vers 0 , tout est là smile

Vasimolo

 #13 - 17-07-2015 22:38:57

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Racine carrée de faactorielle

On prend a=n*1*(n-2)*3*... et b=(n-1)*2*(n-3)*4*... ?


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #14 - 20-07-2015 16:37:08

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1432

Racine carrée de factoreille

@shadock : j'ai plutôt l'impression que ça diverge...

Je reformule l'énoncé : montrer qu'il existe une suite de n tels que n! soit un multiple de K, avec K aussi proche qu'on veut de sqrt(n!), en relatif bien sur.

Le postulat de Bertrand nous indique que sqrt(n!) n'est jamais entier pour n > 1.
En effet, si P est le plus grand nombre premier < n, alors n! devrait être un multiple de P², donc n >= 2P, premier autre multiple de P. Or, entre P et 2P, on trouve P' premier > P d'après le postulat de Bertrand.

Donc on cherche à tendre vers la racine, sans jamais l'atteindre.
Reste à trouver une suite de n qui vérifient ça. Sauf que là, je vois pas trop pourquoi ça serait simple. Oui, il y a des nombres composés autour de sqrt(n!), mais rien n'indique qu'ils soient composés de facteurs premiers < n.
On peut aussi trouver à chaque fois le nombre a diviseur de n! tel que a<sqrt(n!) et pour tout x tel que a<x<srqt(n!) x ne divise pas n!, mais le fait de pouvoir le sortir n'indique pas que la méthode soit simple.

Le problème de trouver un tel a est équivalent au "Backpack problem" en version logarithmique : je prends tous les facteurs premiers de n!, passés en logarithme, et j'essaye de tomber au plus près de ln(sqrt(n!)).
Le problème entre dans la catégorie NP-complet, avec tout ce que ça implique. Par exemple, si je donne une valeur de a, il n'est même pas possible de vérifier en temps polynomial que la réponse est bonne...

Donc il faudrait à la rigueur trouver une série de n bien particuliers qui simplifient ce calcul. Sauf qu'étant donné que ça dépend fortement de la répartition des nombres premiers, en particulier ceux < n, c'est pas facile facile... en tout cas je sèche.

 #15 - 20-07-2015 18:18:48

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Racine carréee de factorielle

Scarta, j'ai proposé au pif absolu lol

Je me suis dis si je prends le plus grand avec le plus petit puis de troisième plus grand avec le ... de même les rangs intermédiaires, on devrait arriver à minimiser b-a mais ce n'est qu'une supposition. Je réfléchis encore à la solution que j'ai proposé. Je vais faire un peu de Python si j'ai le temps !

PS : Il semble que le post est été supprimé, mais est-ce bien toi qui a dit " Pour réaliser un tri, on n'implémente pas en général un convertisseur de structure vers un réel mais plutôt une fonction de comparaison entre 2 structures." ?


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #16 - 20-07-2015 18:44:15

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Racine carrée de factorieelle

Bonjour à tous.
Je donne la solution, je pense que là c'est bloqué.

NB: est ce dû à cette période de chaleur excessive ? Perso je ne suis pas en mesure de me concentrer longtemps sur un problème de maths ardu....

On peut construire 2 suites imbriquées qui donneront chacune une infinité de solutions au problème posé: dans les suites, on prend les entiers successifs 2 par 2, ce sont les éléments successifs des factorielles.

-Une 1ère suite qui commence par (1/2). Elle est suivie par (3/4). Comme 1/2 <1, on compense en multipliant par (4/3).
(1/2)(4/3)=2/3
Comme 2/3 <1, on continue en multipliant par 6/5>1
(2/3)(6/5)=(12/15)=(4/5)
Comme (4/5) <1, on multiplie par 8/7>1
(4/5)(8/7)=32/35
Comme 32/35<1, on multiplie par 10/9>1
(32/35)(10/9)=1.015...
Comme 1.015...>1, on multiplie par 11/12<1
1.015...(11/12)=0.923...
etc...
Ainsi cette factorielle se décompose comme suit:
(1*4*6*8*10*11)*(2*3*5*7*9*12)
Le principe est de compenser un 1+e en multipliant par un 1-f, e et f <<1.
(1+e)(1-f)=1+e-f-ef arrondi à 1+e-f.
1-f<1+e-f<1+e.

ça converge.
Comme les n/(n+1) successifs convergent doucement vers 1, la suite idem.

Dans les faits, n(n+1) ou (n+1)/n représente, à partir de quelques itérations, l'écart relatif maximal. Les valeurs des factorielles successives sont tjs inférieures à ce max, et parfois de beaucoup.

La seconde suite est construite à partir de (2/3).

 #17 - 20-07-2015 21:15:58

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Racine carrée de factorielel

Bon , ça marche mais l'indice était quand même un peu pourri , non lollollol

Vasimolo

 #18 - 20-07-2015 22:31:32

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1432

racine carrée de factoriemle

@shadock : je me rappelle plus. Mais c'est bien possible ça me ressemble une phrase pareille smile

Et sinon, comme Vasimolo, je confirme que ça marche avec la même remarque tongue
Du coup, est-ce une solution miracle à un problème NP montrant que P=NP?
Bien évidemment, non smile cette solution est une solution "potable" du problème du sac à dos tout en étant rarement la meilleure

 #19 - 20-07-2015 23:14:54

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Racie carrée de factorielle

nodgim ta manière de faire est intéressante, voyons voir (par cette chaleur) combien de temps il me faut pour faire ça en python big_smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #20 - 21-07-2015 09:21:02

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

racine carrée de factoeielle

Shadock, en python je sais pas mais un simple tableur donne déja ça jusque 100!  (j'ai limité pour ne pas trop charger le msg))
La 1ère colonne est le résultat, les 2 suivantes sont les facteurs utilisés, la dernière colonne est la fraction (n+1)/n et sert de comparaison avec le résultat.
Observons la précision du résultat en 93/94. En fait, 1 résultat sur 2 est proche de (n+1)/n ou n/(n+1), l'autre est bien plus près de 1. Et si on va plus loin, c'est 1 résultat sur 4, puis sur 8, puis 16,...qui est le meilleur. 

0,5    ...............1    2    2
0,666666667    3    4    1,333333333
0,8.............    5    6    1,2
0,914285714    7    8    1,142857143
1,015873016    9    10    1,111111111
0,931216931    11    12    1,090909091
1,002849003    13    14    1,076923077
0,94017094    15    16    1,066666667
0,995475113    17    18    1,058823529
1,04786854    19    20    1,052631579
1,000238152    21    22    1,047619048
0,958561562    23    24    1,043478261
0,996904025    25    26    1,04
1,033826396    27    28    1,037037037
0,999365516    29    30    1,034482759
1,031603113    31    32    1,032258065
1,001261845    33    34    1,03030303
0,973449016    35    36    1,028571429
0,999758449    37    38    1,027027027
1,025393281    39    40    1,025641026
1,000979156    41    42    1,024390244
0,978229629    43    44    1,023255814
0,999968066    45    46    1,022222222
1,021243982    47    48    1,021276596
1,000819102    49    50    1,020408163
0,981572581    51    52    1,019607843
1,000092818    53    54    1,018867925
0,982234018    55    56    1,018181818
0,999466194    57    58    1,01754386
1,016406299    59    60    1,016949153
1,000012649    61    62    1,016393443
0,984387451    63    64    1,015873016
0,999531873    65    66    1,015384615
1,01445026    67    68    1,014925373
0,999958113    69    70    1,014492754
1,01404203    71    72    1,014084507
1,000338759    73    74    1,01369863
0,987176407    75    76    1,013333333
0,99999688    77    78    1,012987013
1,012655069    79    80    1,012658228
1,000305616    81    82    1,012345679
0,988397216    83    84    1,012048193
1,000025419    85    86    1,011764706
0,988661494    87    88    1,011494253
0,99977005.    89    90    1,011235955
1,010756534    91    92    1,010989011
1,000003805    93    94    1,010752688
0,989587098    95    96    1,010526316
0,999789027    97    98    1,010309278
1,009887906    99    100    1,01010101

 #21 - 21-07-2015 13:43:01

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

racine carrér de factorielle

Tu peux utiliser la balise ["code"] et ainsi mettre 1000000 lignes si tu veux sans faire de page à rallonge wink

Code:

0,5    ...............1    2    2
0,666666667    3    4    1,333333333
0,8.............    5    6    1,2
0,914285714    7    8    1,142857143
1,015873016    9    10    1,111111111
0,931216931    11    12    1,090909091
1,002849003    13    14    1,076923077
0,94017094    15    16    1,066666667
0,995475113    17    18    1,058823529
1,04786854    19    20    1,052631579
1,000238152    21    22    1,047619048
0,958561562    23    24    1,043478261
0,996904025    25    26    1,04
1,033826396    27    28    1,037037037
0,999365516    29    30    1,034482759
1,031603113    31    32    1,032258065
1,001261845    33    34    1,03030303
0,973449016    35    36    1,028571429
0,999758449    37    38    1,027027027
1,025393281    39    40    1,025641026
1,000979156    41    42    1,024390244
0,978229629    43    44    1,023255814
0,999968066    45    46    1,022222222
1,021243982    47    48    1,021276596
1,000819102    49    50    1,020408163
0,981572581    51    52    1,019607843
1,000092818    53    54    1,018867925
0,982234018    55    56    1,018181818
0,999466194    57    58    1,01754386
1,016406299    59    60    1,016949153
1,000012649    61    62    1,016393443
0,984387451    63    64    1,015873016
0,999531873    65    66    1,015384615
1,01445026    67    68    1,014925373
0,999958113    69    70    1,014492754
1,01404203    71    72    1,014084507
1,000338759    73    74    1,01369863
0,987176407    75    76    1,013333333
0,99999688    77    78    1,012987013
1,012655069    79    80    1,012658228
1,000305616    81    82    1,012345679
0,988397216    83    84    1,012048193
1,000025419    85    86    1,011764706
0,988661494    87    88    1,011494253
0,99977005.    89    90    1,011235955
1,010756534    91    92    1,010989011
1,000003805    93    94    1,010752688
0,989587098    95    96    1,010526316
0,999789027    97    98    1,010309278
1,009887906    99    100    1,01010101

"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #22 - 22-07-2015 08:21:08

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

racine carrée de factoroelle

D'accord.
De toute façon, la précision de calcul du tableur limite vite le nombre de lignes:

1................    3181    3182    1,000314367   
0,99968593    3183    3184    1,000314169   
0,999999803    3185    3186    1,000313972   
1,000313577    3187    3188    1,000313775   
1................    3189    3190    1,000313578   
1,000313381    3191    3192    1,000313381   
1,000000196    3193    3194    1,000313185   
0,999687305    3195    3196    1,000312989   
1................    3197    3198    1,000312793   
0,9996875...    3199    3200    1,000312598   
0,999999805    3201    3202    1,000312402   
1,000312012    3203    3204    1,000312207   
1.................    3205    3206    1,000312012   

le 1 apparait 1 fois sur 4.

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 10 moutons, ils meurent tous sauf 9, combien en reste-t-il ?

Sujets similaires

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