Une propriété des mots "longs"

Olympiades mathématiques, énigmes et défis
URemery
Membre Naturel
Messages: 47
Enregistré le: 09 Nov 2016, 22:50
Localisation: 25000

Une propriété des mots "longs"

par URemery » 23 Mar 2017, 20:26

Salut à tous !

On considère un alphabet de cardinal .
On appelle "facteur pair" d'un mot sur un suite de lettres contiguës tirée de ce mot, dont chaque lettre apparaît un nombre pair de fois.
Il s'agit alors de montrer que tout mot de longueur supérieure à admet au moins un facteur pair.

Pour anecdote c'est un exo posé par mon prof d'option info. Un collègue taupin a trouvé une demo que je trouve très jolie alors j'aimerais voir si des artistes se cachent aussi parmi vous :lol:

Bonne réflexion ! ;)
Borne sup, maths spé !



pascal16
Membre Légendaire
Messages: 6663
Enregistré le: 01 Mar 2017, 14:58
Localisation: Angoulème : Ville de la BD et du FFA. gare TGV

Re: Une propriété des mots "longs"

par pascal16 » 23 Mar 2017, 21:15

Il ne parlerait pas des 2^n parties d'un ensemble à n éléments dans sa démo ?

URemery
Membre Naturel
Messages: 47
Enregistré le: 09 Nov 2016, 22:50
Localisation: 25000

Re: Une propriété des mots "longs"

par URemery » 23 Mar 2017, 21:31

Non non il s'agit plutôt d'un petit bonhomme arithmétique dans sa démo aha
Mais rien n'oblige a faire comme lui, au contraire c'est bien de voir des demos différentes ! Tu as trouvé un truc utilisant cela ?
Borne sup, maths spé !

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Une propriété des mots "longs"

par Ben314 » 23 Mar 2017, 22:17

Salut,
Soit j'ai rien compris à l'énoncé... soit c'est complètement évident...
Si est la longueur du mot, à chaque on associé le -uplet de dont le -ième terme correspond à la parité du nombre d'apparition de la lettre n° parmi les première du mot de départ.
Si l'application ne peut pas être injective et c'est fini vu que ça signifie qu'il existe deux "positions" telles que, dans le sous-mot allant de la -ième lettre à la -ième, chaque lettre apparait un nombre pair de fois.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Une propriété des mots "longs"

par nodgim » 24 Mar 2017, 20:06

J'ai pigé, bien que ce ne soit pas tout de même forcément évident au premier coup d’œil pour tout le monde....

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Une propriété des mots "longs"

par Ben314 » 24 Mar 2017, 21:37

Effectivement, j'ai peut-être exagéré en disant que "c'est évident" : pour que ce soit "évident", il faut avoir un peu l'habitude et que ça "saute aux yeux" que tout les truc du style "les sous-mots de allant de la lettre à la lettre ", c'est du même tonneaux que toutes les "relations de Chasles" où le premier truc qui vient à l'esprit, c'est d'écrire et autres . . .
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
Lostounet
Admin
Messages: 9665
Enregistré le: 16 Mai 2009, 13:00

Re: Une propriété des mots "longs"

par Lostounet » 24 Mar 2017, 22:55

nodgim a écrit:J'ai pigé, bien que ce ne soit pas tout de même forcément évident au premier coup d’œil pour tout le monde....


Je n'ai pas trop bien compris la fin ...
C'est un peu moins évident que ce qu'on aimerait :p

Quelqu'un pourrait-il m'expliquer?
Merci de ne pas m'envoyer de messages privés pour répondre à des questions mathématiques ou pour supprimer votre compte.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Une propriété des mots "longs"

par Ben314 » 25 Mar 2017, 00:04

Exemple :
Le mot de départ est ABACDBABCADBACBA avec 16 lettre choisies parmi 4 différentes A,B,C,D.
On construit la fonction F : {0..16} -> {0,1}^4 suivante :
F(0) = (0,0,0,0) mot de zéro lettre -> ni A, niB, ni C, ni D
F(1) = (1,0,0,0) A -> 1(impair) A
F(2) = (1,1,0,0) AB -> 1 (impair) A et 1 (impair) B
F(3) = (0,1,0,0) ABA -> 2 (pair) A et 1 (impair) B
F(4) = (0,1,1,0) ABAC -> 2 (pair) A ; 1 (impair) B et 1 (impair) C
. . .
F(16) = (1,0,0,1) ABACDBABCADBCDAC -> 5 (impair) A ; 4(pair) B ; 4 (pair) C et 3 (impair) D

Il y a 17 élément dans {0..16} et seulement 16 dans {0,1}^4 : F ne peut pas être injective et en fait, on a (par exemple) F(3) = (0,1,0,0) = F(11) correspondant à ABA et ABACDBABCAD
Ce qui signifie, par simple soustraction, que la partie bleue contient un nombre pair d'occurrence de chaque lettre.

Question : existe t-il un procédé (le plus simple possible) pour générer un mot de lettres prises dans un alphabet de lettres qui ne contient aucun sous-mot contenant un nombre pair d'occurence de chaque lettre ?
(ce qui revient bien sûr à lister tout les nombres de bits en base 2 de façon à ce qu'il y ait exactement un bit de différence entre un nombre et son suivant dans la liste)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
Lostounet
Admin
Messages: 9665
Enregistré le: 16 Mai 2009, 13:00

Re: Une propriété des mots "longs"

par Lostounet » 25 Mar 2017, 03:39

Merci Ben c'est plus clair maintenant, au moins pour la construction de F.

Mais un truc me dérange un peu: pourquoi tu commences ta construction par F(0) et pas par F(1)...

Car si on commence par 1 les ensembles ont même cardinal. En fait tout repose ici..
Merci de ne pas m'envoyer de messages privés pour répondre à des questions mathématiques ou pour supprimer votre compte.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: Une propriété des mots "longs"

par Ben314 » 25 Mar 2017, 04:03

Je commence à 0 parce que c'est ce qu'il y a de plus logique :
Si tu cherche les "sous mots" de ABCDE, du style BC ou CDE ou ABC, et que veut les écrire comme des "soustraction" de "mot commençant au début", par exemple BC=ABC-A ou CDE=ABCDE-AB alors pour pouvoir écrire ABC sous cette forme il faut l'écrire sous la forme ABC-mot_vide et donc accepter "mot_vide" comme un mot.
Bref, si tu veut le "sous mot" formé des lettres de la -ième à la -ième, il faut prendre les premières auquel on "retranche" les première. Et évidement, si il faut accepter de parler des " premières lettres" vu que
Sur le principe c'est exactement la même logique qui conduit à poser qu'une somme vide vaut 0 où qu'un produit de "rien" dans un groupe quelconque, ça fait le neutre du groupe ou que vect{ensemble_vide}=singleton_vecteur_nul.
Tu as jamais jamais vu la notion de groupe/monoïde libre et celle de groupes définis par générateurs et relations ?
(on y définit la notion de "mot" et de "longueur de mot" et il y a bien sûr un "mot vide" de longueur nulle qui est l'élément neutre du monoïde ou du groupe exactement comme en informatique il existe une unique chaine de caractère composée de zéro caractères)

Sinon, évidement l'autre raison (mais bien moins valable), c'est que vu que tu veut aboutir au fait que F est non injective, tout est bon à prendre pour avoir l'ensemble de départ le plus gros possible.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 10 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite