Coup de Boole

[Arbre]

Bonjour,





Au revoir.

[Matt_01]

Pour moi, on déduit que c'est vrai grâce au fait que m!(n-m+u)! / u! est pair dés que n>=m et u>=0 (et n>=3).

[Arbre]

Oui, on pourrait aussi le déduire du résultat supposé

[Matt_01]

Comment ?

[Arbre]

Tu pourrais développer, beaucoup plus ton explication ?

[Matt_01]

J'écris où a_k = 0 ou 1 et k(i) désigne le i eme chiffre dans l'écriture binaire de k (on vérifie bien que cette écriture est possible, c'est chiant mais facile).
Notre somme devient avec
Et maintenant je suis en train de douter de l'intitulé de ta question. Qu'est ce que le "mod 2" vient faire ici sachant qu'on parle de booléen ? Si tu considères f comme simplement une fonction de {0,1}^n dans {0,1} alors ok, la suite de ma démonstration consiste à compter le nombre de permutations phi telles que, à k donné, .
Ce genre de permutation, c'est juste les permutations qui envoient vers , 2 ensembles qui sont fixés par la donnée de et f. On peut finalement compter ces permutations et montrer que ce nombre est pair (les nombres de mon post précédent). Du coup on fait une somme de trucs pairs, ce qui donne une somme finale paire.

Si maintenant on s'intéresse à la valeur booléenne de notre somme, pour qu'elle vaille 1 il faut qu'au moins un élément vaille 1, et donc qu'il existe une permutation phi qui envoie vers et donc que .
La somme vaut donc 1 si , 0 sinon.

[Arbre]

Nul part tu n'utilises le fait que , or si on prend f(0,1)=0 et f(1,0)=1 on voit bien qu'ici cela ne marche pas.

[Arbre]

Pour ce qui est de ton résultat précédent où tu mentionnes bien le fait n>2.

1/ Comment montres-tu que cela, correspond à ce que tu comptes ?

2/ Comment montres-tu que ce nombre est bien pair ?

[MMu]

Dans il y a '' et ''.
Pour on a multiple de 2. Voilà !

[Arbre]

Tu n'as pas la même formule que Matt, lui divise par une factorielle, mais les questions que j'ai posé à Matt, tu n'y réponds pas non plus.

[MMu]

On peut généraliser la méthode.
Par ex pour (naturels) , on a

Do you follow me ?

[Arbre]

c'est surement généralisable, mais cela ne répond pas à mes questions, ou alors il faudrait me dire comment.

[Matt_01]

Si on note m le nombre de 1 dans k, p le nombre de 1 dans x :
On a p choix pour le premier 1 dans k, p-1 pour le deuxième etc ce qui donne p!/(p-m)!
Pour les n-p restants termes à déterminer, on a n-m choix puis n-m-1 puis ... puis 1.
Le résultat final est donc p!(n-m)!/(p-m)! qui est tout le temps pair pour n>=3.

[Arbre]

1/ Ok.

2/ Mais pourquoi ce nombre est toujours pair ?

[Matt_01]

Si p!/(p-m)! est impair alors p = 1 ou p=0 ou m=1.
Dans tous ces cas là, (n-m)! est pair (m<=p).

C'est usant de vouloir tant de justifications, c'est clairement évident par rapport au niveau du problème.

[Arbre]

Ok, bravo.