Des ampoules

par **beagle** » 03 Juin 2010, 15:45

Ben314 a écrit:Partant de ça : (mais je sais pas s'il n'y a pas mieux...)
J'ai comme minorant pour n=1,2,3,4,5,6 les valeurs k=0,1,2,3,5,8
En particulier, pour n=4, mon minorant vaut 3 !!!

Ok, merci Ben.
faut que je truande, je suis un peu au-dessus.

par **beagle** » 03 Juin 2010, 15:53

il y a un 4x4 que j'ai réduit à ceci,
0001
0010
0001
0010

on devrait donc pouvoir passer à 3, Ben?C'est ça?

par **Ben314** » 03 Juin 2010, 16:01

Non, je pense plutôt que "mon" minorant, bien que valable, n'est pas du tout optimum : je fait le calcul comme si dans une classe (i.e. un groupe de config. équivalentes à tripatouillage d'interupteurs prés) il n'y en avais toujours qu'une seule avec un "petit" nombre d'ampoules allumées.
Il me semble que ce n'est pas le cas donc "mon" minorant doit pouvoir être amélioré.

Je ne sais pas comment fait miikou pour trouver son n²/2 - (n^3/2Pi)^1/2 qui est meilleur que ma minoration ni Doraki qui semble n'avoir qu'un seul coeff inomial là où j'ai une somme...

P.S. En la regardant "dans le blanc des yeux", ta config 4x4 me semble bien être dans son "état mini d'allumage".

par **Doraki** » 03 Juin 2010, 16:21

Pour n=4, la valeur exacte est 4.
Si on part de la configuration ou les 4 ampoules au centre sont allumées, on ne peut pas obtenir de configuration avec moins de 4 ampoules.

Et pour n=5, c'est 7.

(j'avais qu'un seul coefficient binomial parceque je me suis trompé en croyant que ça se simplifiait)

par **beagle** » 03 Juin 2010, 16:29

(effectivement) un 5x5 avec du 7 que je n'arrive pas à réduire:
10000
00101
00001
01000
01010

bon, au départ j'avais un peu fait exprès, mais je ne maitrise pas tous les éléments,
tu trouves 7 comment Doraki?par ta formule initiale?Autre?Les deux?

par **nodjim** » 03 Juin 2010, 16:54

Je trouve qu'on peut toujours allumer plus de la moitié des lampes du tableau, quelque chose du genre n(n+1)/2.

par **Doraki** » 03 Juin 2010, 17:12

Ca fait une majoration du nombre cherché par n²/2...

par **nodjim** » 03 Juin 2010, 18:39

Oui c'est large je sais.

par **Imod** » 05 Juin 2010, 11:48

Un problème sûrement connexe :doh:

Nombre d'orbites pour le groupe des actions sur les lignes et les colonnes ?

Imod

par **miikou** » 05 Juin 2010, 12:36

salut

y'a de ca Imod ;)

par **miikou** » 06 Juin 2010, 19:21

Bonsoir,

Le sujet est clos ? auquel cas j'ai une question complémentaire de quoi torturer vos méninges encore qq heures :we:

par **Ben314** » 06 Juin 2010, 20:56

En ce qui me concerne, le sujet est pas clos sauf que
1) En ce moment je fait pas beaucoup de maths.
2) En essayant d'améliorer mon minorant par exemple dans le cas n=4 (en étudiant le nombre de config du style 2 ampoules alumées sur une même ligne/colonne dont l'orbite contient deux configs avec seulement deux ampoules allumée...) je fini par trouver que k=4, mais je vois pas comment faire dans le cas quelconque...

Comment obtient tu ton minorant n²/2 - (n^3/2Pi)^1/2 ?

par **miikou** » 06 Juin 2010, 22:30

il faut enleve le pi desole :)

par **miikou** » 10 Juin 2010, 13:24

je donne la solution ? ou vous preferer y reflechir encore ?

par **Ben314** » 10 Juin 2010, 14:29

En ce qui me concerne, je cherche plus (pas trop de temps...)

par **miikou** » 12 Juin 2010, 11:08

bon bah va falloir que je me remet au latex :D

par **miikou** » 12 Juin 2010, 11:46

On y joue un ptit coup ?

http://www.quickflashgames.com/games/berlekamps-game/

par **vingtdieux** » 13 Juin 2010, 00:43

En tout cas je sais que dans un problème proche de celui-là où en fait les ampoules sont au départ toutes connectées, il s'agit de couper les fils de connection un a un jusqu'à que les ampoules s'eteignent. Le nombre de fil a couper fait appel à la théorie de la percolation.

Des ampoules

Qui est en ligne