Des ampoules

par **miikou** » 02 Juin 2010, 12:27

Salut

On considere un tableau de n*n ampoules.
Pour chaque ligne et colonne on dispose d'un interrupteur.
Quand on actionne un interrupteur les ampoules de la ligne/colonne allumées s'eteignent et celles eteintes s'allument.

Pour un configuration initiale arbitraire :
quel est le nombre minimum d'ampoules alluméés apres avoir utiliser autant d'interrupteurs que l'on desire ?

par **Ben314** » 02 Juin 2010, 15:25

Je suis pas sûr d'avoir compris la question...
Il faut déterminer en fonction de la configuration initiale le nombre mini d'ampoules allumées aprés tripatouillage quelconque ?

par **miikou** » 02 Juin 2010, 17:21

salut,

oui

par **miikou** » 02 Juin 2010, 19:33

salut,

le max des minimums pour chaques tableaux possibles n*n

par **beagle** » 02 Juin 2010, 22:48

bon, juste avant d'aller me coucher en général j'éteints tout.

Donc
111111
100000
100000
100000
100000
100000

j'actionne en haut à gauche et au lit.

par **miikou** » 02 Juin 2010, 22:51

beagle a écrit:bon, juste avant d'aller me coucher en général j'éteints tout.

Donc
111111
100000
100000
100000
100000
100000

j'actionne en haut à gauche et au lit.

il y en a un pour chaque les lignes et chaques colonnes : dommage :bad:

par **beagle** » 02 Juin 2010, 22:59

ah oui, j'ai compris où est l'interruptueur, scuses, je l'avais mis dans la case.

donc
1111
0000
1111
0000

j'actionne rangée1 et rangée3 et au lit.
bon, la contribution est modeste j'en conviens.

par **beagle** » 02 Juin 2010, 23:22

encore une, variante de mon erreur de bouton précédent:
011110
100001
100001
100001
100001
011110
cela permet de tout éteindre.

par **Ben314** » 03 Juin 2010, 09:38

Je sens qu'il y a des cheveux qui vont se dresser sur des têtes (et, surtout, je risque de m'être fortement égaré... :mur: )
Bon, tout ça pour dire que je conjecture que le max des min est "environ supérieur" (???) à :

[Mais d'où as-t-il pu sortir un truc aussi pourri ????]

par **Doraki** » 03 Juin 2010, 10:13

J'ai que si k = max des mins des tableaux n*n,

,
mais les calculs deviennent horribles pour deviner un équivalent de k.

par **Ben314** » 03 Juin 2010, 10:23

Doraki a écrit:J'ai que si k = max des mins des tableaux n*n,
,
mais les calculs deviennent horribles pour deviner un équivalent de k.

Perso, j'ai plutôt

puis, en approximant la liste des coeff. binomiaux par la gaussienne (loie normale) puis en approximant la gaussienne

(valable pour x<0 "assez grand"), je tombe sur le résultat de mon post précédent...

par **miikou** » 03 Juin 2010, 10:41

salut

ben ton k verifie bien ton inégalité ( celle de ton dernier post )
par contre on a comme approximation grossiere k < n²/2

tu as trouver ca seul ou tu t'ai aider de la theorie des codes ?

par **Ben314** » 03 Juin 2010, 11:17

miikou a écrit:tu as trouver ca seul ou tu t'ai aider de la theorie des codes ?

En fait, je me suis pas trop aidé de "la théorie des codes" vu que... je sais même pas ce que c'est...

J'ai seulement utilisé des argument con-con de cardinalité :
Il y a

configurations possibles pour les ampoules et

façons de "jouer avec les interrupteurs" car un des interrupteurs ne sert à rien du fait que si on les bouges tous, ça ne change rien, par contre, tout les autres sont "utiles" et chaque config. d'interrupteur produit un résultats différent.
On peut donc ranger les

config. en

"paquets" de

configs. de façon à ce que les tripotages d'interrupteurs correspondent à un "paquet" (en utilisant des mots savants, les "paquets" sont les orbites suivant l'action du groupe additif

constitué par les configs d'interrupteurs qui agit sur l'ensemble

des configurations d'ampoules via

où

est le vecteur colonne entièrement constitué de 1 ).

Enfin, des configs. ayant moins (au sens large) de k ampoules allumées, il y en a exactement

donc, pour des raisons de cardinalité, si

, on est sûr qu'au moins une orbite (un "groupe") ne contient que des config. ayant strictement plus de k ampoules allumées.

Il ne reste plus qu'à estimer A(k) à l'aide de la gaussienne pour tomber sur mon estimation.

par **miikou** » 03 Juin 2010, 11:33

impressionant le coup de la matrice Mn²(Z/2Z) etc parcque c'est exactement la facon de voir les choses dans la theorie des codes.

enfin ta minoration doit surement etre juste ( ? )
moi j'ai n²/2 - (n^3/2Pi)^1/2

par **Ben314** » 03 Juin 2010, 11:44

miikou a écrit:enfin ta minoration doit surement etre juste ( ? )

Autant, sur le principe, je pense que "j'ai bon", autant sur mes résultats, dés qu'il y a plus de deux lignes de calculs, c'est assez aléatoire...

miikou a écrit:n²/2 - (n^3/2Pi)^1/2

Ce qui est quand même à peu prés le double de ce que je trouve...

par **miikou** » 03 Juin 2010, 11:48

lol désolé je me corrige

moi j'ai n²/2-(n^3/2pi)^1/2 < k < n²/2

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

Pour que je puisse jouer un peu avec vous,
pouvez-vous mettre un 4x4 avec plus de 4 irréductibles,
c'est pour une dissection, je voudrais voir sa structure.
d'avance merci.

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

4 est un peu petit,
mais je veux bien l'estimation de Ben pour n=4, 6,...cela donne quoi?

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

n=5, du 7 est difficile,certains impossible? à réduire,
mais c'est en gribouillant...

par **Ben314** » 03 Juin 2010, 15:43

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 !!!

Des ampoules

Des ampoules

Qui est en ligne