Forum de mathématiques - Bibm@th.net

Abirmdr

Invité

Exo d'ensembles

Je suis en train de faire un exercice, aucunes idées et aucunes pistes pour le résoudre, donc ,l'énoncé dit :
Soit A={1,2,3,...,n} avec n entier naturel impair et soient x1,x2,....,xn des éléments de A distincts deux à deux,
Montrer qu'il existe i dans A tel que xi-i est pair .

Merci de votre aide, j'espère trouver des idées clairs et peut m'aider dans cet exo .

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Exo d'ensembles

Bonjour,

Si tous ces nombres étaient impairs, comme ils sont en nombre impair, leur somme serait ....
Or cette somme vaut ...
Donc...

A.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Exo d'ensembles

Ou encore, sinon,  par bijection les i pairs donneraient des $A_i$ impairs et vice versa, donc il y aurait autant de pairs que d'impairs dans A.

A.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Exo d'ensembles

Et enfin en décomposant la bijection en produit de cycles, l'un des cycles est de longueur impaire
( longueur 1 en cas de pt fixe) et donc si deux éléments successifs du cycle sont toujours à distance impaire, le premier et le dernier on forcément même parité.
$x_1   x_2 ...... x_{2k+1}$
$ x_2   x_3.....   x_1$

Cette dernière approche un peu plus constructive, permet de répertorier entre autres les bijections x telle que le i en question soit unique.
$E = \{ x  \in  S_n  ,  \exists ! \; i \; x_i - i \; pair \}$

Par exemple si n = 7, il faut les chercher en tous cas  parmi les permutations:

- possédant un 1-cycle unique (càd un point fixe et un seul) sans autre cycle d'ordre impair (donc de type (1,6) ou (1,2,4)
- possédant un 3-cycle unique sans autre cycle d'ordre impair (donc de type (3 , 2, 2)  ou (3,4))
- possédant un 5-cycle unique sans autre cycle d'ordre impair (donc de type ( 5, 2) )
- les 7-cycles

bref parmi les permutations ayant un unique cycle d'ordre impair.

Ainsi, entre autres (encore avec n=7) sont dans E, avec des types différents:

1 2 3 4 5 6 7
4 5 2 3 1 7 6   

1 2 3 4 5 6 7
4 7 1 3 6 5 2

1 2 3 4 5 6 7
4 5 1 3 6 7 2

1 2 3 4 5 6 7
4 5 2 1 6 3 7

En effet on a vu qu'un cycle de longueur impaire fournit (au moins) un i valable.
Le reste du travail à effectuer n'est pas vraiment automatique, mais cela circonscrit déjà la question en donnant un pseudo "gabarit" pour x.
Je ne me suis pas penché sur la question du dénombrement, mais je pense qu'un algorithme travaillant sur ces gabarits pourrait fournir E.

A.

Dernière modification par bridgslam (18-08-2023 13:04:52)

Bernard-maths

Membre Expert

Lieu : 34790 Grabels

Inscription : 18-12-2020

Messages : 1 901

Re : Exo d'ensembles

Bonjour à tous !

A est l'ensemble des n premiers nombres entiers, et il y a (n-1)/2 nombres pairs, et (n-1)/2 + 1 nombres impairs. Donc un nombre impair de plus que de pairs ...

Or par bijection A est mis en relation avec lui-même ( les x_i étant 2 à 2 distincts).

Si on considère les nombres pairs, ils seront mis en relation avec (n-1)/2 nombres, et comme il y a 1 nombre impair de plus que les pairs, il restera au moins un nombre impair non mis en relation avec les nombres pairs.

DONC ... je vous laisse conclure ?

Bernard-maths

Dernière modification par Bernard-maths (15-08-2023 16:14:22)

Abirmdr

Invité

Re : Exo d'ensembles

Bonjour,

Si tous ces nombres étaient impairs, comme ils sont en nombre impair, leur somme serait ....
Or cette somme vaut ...
Donc...

A.

Bonjour bridgslam , pouvez vous m'expliquer plus , j'ai pas compris quel raisonnement vous avez utilisé ، et si c'est l'absurde , quels nombres vous avez posé impair ?

Merci d'avance.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Exo d'ensembles

Bonsoir, 

Je vous ai proposé 3 pistes différentes.
Posez $b_i = a_i - i$.

Supposer qu'ils sont tous impairs ...
Ensuite sommer les , exprimez cette somme et trouvez une contradiction.

Bon courage
A.

Abirmdr

Invité

Re : Exo d'ensembles

Bonsoir, 

Je vous ai proposé 3 pistes différentes.
Posez $b_i = a_i - i$.

Supposer qu'ils sont tous impairs ...
Ensuite sommer les , exprimez cette somme et trouvez une contradiction.

Bon courage
A.

La somme ça va être nulle, n'est-ce pas ? Et le 0 est un nombre pair ? Donc une contradiction. C'est juste ??

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Exo d'ensembles

Bonsoir,

Tout à fait.

A.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Exo d'ensembles

Bonsoir ( bonjour plutôt),

Une petite investigation supplémentaire en terme de dénombrement permet de résumer le résultat suivant:

Soit n naturel et impair.
Pour toute permutation x de $S_n$ il existe i appartenant à {1,...,n} tel que $x_i - i$ soit pair.
Il y en a $u=\{(n-1)/2\}!^2(n+1)^2/4$ telles que i soit unique , i est alors impair.

n=1. u=1         
n=3. u=4         
n=5. u=36       
n=7. u=576     

...
il y a en fait une petite généralisation au fait que u est carré, si on s'intéresse aux autres permutations.

On peut s'amuser à les lister.
J'ai fait jusqu'à n=5...

Alain

Dernière modification par bridgslam (23-08-2023 21:47:32)

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Exo d'ensembles

Bonjour,

Enfin on peut classer toutes les permutations de $S_n$ (n impair) ainsi:

- celles de la classe $C_1$ ayant exactement 1 indice i impair et 0 indice pair répondant à la question (qu'on vient de dénombrer)
- celles de la classe $C_2$ ayant exactement 2 indices i impairs et 1 indice pair répondant à la question
- ....
- celles de la classe $C_{p+1}$ ayant exactement p+1 indices i impairs et p indices pairs répondant à la question
-....
- celles de la classe $C_{(n+1)/2}$ avec (n+1)/2 indices i impairs et (n-1)/2 indices pairs répondant à la question (par exemple l'identité)

Ainsi, par exemple, (encore avec n=7) :
1 2 3 4 5 6 7
5 6 7 1 2 3 4     est dans $C_2$

tandis que
1 2 3 4 5 6 7         
1 2 3 4 5 6 7         

et
1 2 3 4 5 6 7
3 6 5 4 7 2 1

sont dans $C_4$

On peut dénombrer chaque classe si on a un peu de courage (très faisable si on dispose d'un peu de temps).
$C_1$ occupe un peu plus du quart du total des 3 classes si n = 5,  un peu plus du dixième du total des 4 classes si n = 7.

A.

Dernière modification par bridgslam (20-08-2023 11:13:06)

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Exo d'ensembles

Bonsoir,

J'ai disposé d'un peu de temps pour exprimer la taille des classes $C_p$ des permutations de $S_n$ , n impair, telles que
p indices impairs et (p-1) indices pairs vérifient la condition:

$Card ( C_p) = p!(p-1)! (C_{(n+1)/2}^p )^2(C_{(n-1)/2}^{p-1})^2 (( n+1)/2 - p )!^2$

les 120 permutations pour n=5 se répartissent alors en 36 ( indice unique, impair) , 72 ( trois indices, deux impairs et un pair ) ,12 ( cinq indices, trois impairs et deux pairs).

Vérifier dans le cas général que la somme des cardinaux $C_1, ..., C_{(n+1)/2} $ donne bien n! n'est pas forcément trivial.
Je n'ai pas essayé, n'étant pas vraiment fan (et même pas du tout) de ce genre de calcul.
Peut-être un logiciel de calcul formel le fait-il automatiquement d'ailleurs.

[ j'étais en phase d'investigation lorsque j'ai écrit ces remarques, en réalité- voir dernier message - tout s'arrange admirablement
et on a même avec cette nomenclature de bijections une application inattendue de la sommation des $ k\binom{n}{k}^2$
...
pas besoin de logiciel donc , a posteriori]

A.

Dernière modification par bridgslam (25-08-2023 13:02:34)

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Exo d'ensembles

Bonsoir,

l'expression donnant le cardinal de la classe $C_p$ des permutations $\sigma$ ayant p indices pairs et (p-1) indices impairs tels que $\sigma(i) - i $ soit pair , donnée auparavant, se simplifie en fait agréablement en :

$ \boxed{ \large Card( C_p ) = p \{  \frac {n-1}{2}! \binom{\frac{n+1}{2} }{p}\}^2 }$ ( et en utilisant le symbole moins vétuste des combinaisons ).

Avec cette expresssion la vérification algébrique de $ n! = \sum_{p \in \{1,..., (n+1)/2\}} \; p [  \frac {n-1}{2}! \binom{\frac{n+1}{2} }{p}]^2$
peut s'envisager plus sereinement :-).

(en effet une preuve ensembliste simple sur un ensemble à n (impair) éléments presque :-)  équitablement partagé en deux parties simplifie la partie sommatoire,
et tout se simplifie ensuite compte-tenu du coefficient fixe de la formule, cela donne bien,après deux lignes de calcul, n!)

On voit aussi arithmétiquement que le cardinal d'une classe rapporté au nombre p d'indices i impairs qui lui donne son nom est toujours un carré .
Notamment notre petite étude montre que pour  tout n impair  le nombre de permutations telles que i soit unique est un carré parfait (vu que p = 1).
Ce qu'on voyait déjà avec l'expression de u donnée dans un message antérieur.
Notre petite étude permet mieux d'en percevoir la raison...

Alain

Dernière modification par bridgslam (28-09-2023 15:37:59)