Fonction injective dont l'ensemble de départ est {0,1}

Pavel Gorofsky

Bonjour
Pour un devoir en mathématiques appliquées à la cryptographie je dois utiliser un petit théorème, cependant je m'interroge sur la bonne notation de ce dernier et de la notation utilisée, c'est un devoir où je suis obligé de citer l'ensemble du théorème ainsi que sa preuve, c'est pourquoi j'aimerais que ce dernier soit "propre" tant dans son énoncé que dans sa démonstration.
Le voici.

Cordialement,
P.G

Math Coss

Au lieu de "then", je mettrais quelque chose du genre « Comme ces huit valeurs sont différentes, ».

Au passage, ce serait plus facile à vérifier en classant les triplets par ordre croissant de leurs images.

JLT

On peut aller plus vite : en regardant la parité des deux membres on voit que $c=c'$, donc $3a+2b=3a'+2b'$, puis on compare encore la parité.

Pavel Gorofsky

Bonjour JLT
Merci pour votre réponse,
Pouvez-vous m'expliquer la démarche de ce type de démonstration pour ce cas précis du moins.
Cordialement,
P.G.

JLT

$c+1$ est égal à $1$ ou $2$. Comme $\dfrac{12a+8b}{c+1}=2(3a+2b)\times \dfrac{2}{c+1}$, il est pair donc $f(a,b,c)$ a la même parité que $\dfrac{2}{c+1}$. Donc si $c=0$, $f(a,b,c)$ est pair et si $c=1$ alors $f(a,b,c)$ est impair.

Pavel Gorofsky

JLT

Merci à vous,

Pouvez-vous m'expliquer le lien entre le fait de montrer cela et le fait de prouver l'injection de la fonction $f$ ? Je n'arrive pas à trouver
Cordialement.

JLT

Tout est dans mes deux précédents messages. Je pars de $f(a,b,c)=f(a',b',c')$. Je montre d'abord que $c=c'$ d'après mon deuxième message, et ensuite $a=a'$ puis $b=b'$.

Pavel Gorofsky

JLT

Je voulais une explication sur le fait d'affirmer que $c=c'$ d'après votre deuxième message en étudiant la parité de $f(a,b,c)$.

gerard0

Ben ... comme c pair dit c=0 et c impair dit c=1, il te suffit de regarder f(a,b,c) dans les deux cas et tu verras que f(a,b,c) a la même parité que c.

Tu pourrais faire un petit effort pour adapter toi-même les indications qu'on te donne. Chercher !

Cordialement.

[une phrase fausse supprimée]

Pavel Gorofsky

JLT

Si j'ai bien compris en montrant cela : 

$c+1$ est égal à $1$ ou $2$. Comme $12a+8b/(c+1)=2(3a+2b)×2/(c+1)$, il est pair donc $f(a,b,c)$f a la même parité que $2/(c+1)$. Donc si $c=0$,$f (a,b,c)$f est pair et si $c=1$ alors $f(a,b,c)$f est impair.
Cela nous permet d'affirmer que comme $f(a,b,c)=f(a',b',c')$ alors $2/(c+1)=2/(c'+1)$ et donc $c=c'$ ? c'est ce que je ne comprend pas comment en étudiant la parité on peut admettre que $2/(c+1)=2/(c'+1)$.

Pavel Gorofsky

Bonjour, gerard0 
Oui j'ai compris le raisonnement pour montrer la parité mais je me suis mal exprimé, c'est le fait d'étudier la parité et ensuite affirmer que $c=c'$ que je ne comprend pas.

TrackTrick

M'enfin.....

$f(a,b,c)="un truc pair" +\dfrac{2}{c+1} = f(a',b',c')="un truc pair" +\dfrac{2}{c'+1}$ donc $\dfrac{2}{c+1}$ et $\dfrac{2}{c'+1}$ ont nécessairement la même parité ! Or, comme JLT te l'as déjà dit, $\dfrac{2}{c+1}= 1$ ou $2$ ... donc ça ne laisse pas beaucoup de choix !

Math Coss

Du fait que $A=\dfrac{12a+8b}{c+1}=2(3a+2b)\times \dfrac{2}{c+1}$ est pair et que $f(a,b,c)=\dfrac{12a+8b}{c+1}=A+\dfrac{2}{c+1}$, $f(a,b,c)$ a la même parité que $\dfrac{2}{c+1}$, c'est-à-dire que :

• si $f(a,b,c)$ est pair, alors $\dfrac{2}{c+1}$ est pair donc $c=0$ (et, si $f(a,b,c)=f(a',b',c')$, alors $c'=0$ aussi !) ;
• si $f(a,b,c)$ est impair, alors $\dfrac{2}{c+1}$ est impair donc $c=1$ (et, si $f(a,b,c)=f(a',b',c')$, alors $c'=1$ aussi !).

Autrement dit, la parité de $f(a,b,c)$ détermine $c$. Par conséquent, si $f(a,b,c)=f(a',b',c')$, alors $c=c'$.

Pavel Gorofsky

Si j'ai bien compris , 
Si $f(a,b,c)=f(a',b',c')$ cela implique que $f(a,b,c)$ a la même parité que $f(a',b',c')$ or la parité des deux dépendent de $c$ et $c'$ et $c$ ne prend pour valeur que $0$ ou $1$ et lorsque c'est $0$, $f$ est pair et lorsque c'est $1$, $f$ est impair donc on peut affirmer que $c=c'$.
Et du coup on doit suivre le même raisonnement pour $a$ et $b$ ?
Cordialement.

Math Coss

Sachant que $c=c'$, l'hypothèse devient $\frac{12a+8b+2}{c+1}=f(a,b,c)=f(a',b',c)=\frac{12a'+8b'+2}{c+1}$. On en déduit que $12a+8b+2=12a'+8b'+2$, puis que $12a+8b=12a'+8b'$, puis que $3a+2b=3a'+2b'$, c'est-à-dire que $a=a'+2(a'+b'-a-b)$. Ainsi, $a$ et $a'$ ont la même parité et comme ils valent $0$ ou $1$, ils sont égaux. En reportant, on voit que $3a+2b=3a+2b'$, puis $2b=2b'$ et enfin $b=b'$.

lourrran

Pour ton message de 11h25, https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2350983/#Comment_2350983

la réponse est non.

La parité de $f(a,b,c)$ dépend de la parité de $c$.... oui et non. C'est vrai, mais ce n'est pas suffisamment précis.
Si on part par là, on peut aussi dire que la parité de $f(a,b,c)$ dépend de la parité de $a$.

Ici, la parité de $f(a,b,c)$ est la même que la parité de $c$. Il faut le prouver, l'expliquer... mais au final, c'est beaucoup plus précis et exploitable que dire 'la parité de ... dépend de ...'
Si $f(a,b,c) =f(a',b',c')$ alors ils ont même parité, et comme $f(a,b,c)$ a même parité que $c$, et que $f(a',b',c')$ a même parité que $c'$, on conclut que $c$ et $c'$ ont même parité.
Et comme les seules valeurs possibles pour $c$ et $c'$ sont $0$ ou $1$, si $c$ et $c'$ sont tous les 2 pairs, ils sont tous les 2 égaux à $0$. Et si $c$ et $c'$ impairs, ils sont tous les 2 égaux à $1$.  

Donc dans les 2 cas, si $f(a,b,c)=f(a',b',c')$ alors $c=c'$
La suite pour a et b est moins immédiate.

Pavel Gorofsky

lourrran

J'ai tenté une généralisation du théorème et rédigé une preuve qui reprend les concepts énoncés dans ce fil. Si vous pouvez identifier les potentiels erreurs cela me permettrait d'avancer merci à vous.

Cordialement,
P.G

gerard0

Bonjour.

1) Pourquoi en anglais ?

2) Pourquoi ne pas simplifier l'énoncé du théorème en utilisant le mot "injective" ?

3) En général, on admet dans le début de la preuve les hypothèses du théorème, donc on ne dira pas "lef f be a function ...". D'ailleurs, tu n'es pas cohérent puisque tu ne redéfinis pas n !!!

4) Noter qu'un nombre a la même parité que lui-même sert-il à quelque chose ("Then f(a,b,c) et f(a',b',c') have the same parity") ???

5) Le "As shown in [1]" est ridicule ! C'est un exercice pour collégien, pas besoin d'aller chercher la référence ailleurs.

J'arrête là, ça suffit bien pour dire que tu ne fais pas la rédaction d'une preuve mathématique qui est dans ta tête, mais l'écriture d'un texte magique dont tu crois que c'est ça les maths.

Je ne comprends pas pourquoi tu joues à ça, mais si tu as besoin de rédiger une preuve sur ce sujet, commence par l'écrire en bon français en écrivant ce que tu comprends et justifiant toutes les étapes par les règles élémentaires. Sans jouer au mathématicien professionnel.

Cordialement.

lourrran

Pour un devoir en mathématiques appliquées à la cryptographie  :  Ok donc on n'est pas au collège ni au lycée, on sait (ou on croit) que les étudiants ont un niveau correct en mathématique.
Pour moi, quand on est entre adultes consentants, entre personnes qui ont déjà fait leurs preuves, on dit : on vérifie aisément que cette fonction est injective. 
Terminé.
Si vraiment on veut détailler on peut éventuellement dire :
si f(a',b',c,') = f(a,b,c), on vérifie aisément que c'=c, puis que b'=b et que a'=a.

Sous-entendu : Mr le professeur, j'ai passé l'âge de faire des exercices de niveau collège ou lycée.

Maintenant, si tu tiens à détailler, ou si tu en ressens le besoin, les remarques de gerard0 me semblent tout à fait pertinentes.

math2

Pour compléter un peu ce qu'écrit gérard0, j'ajouterais que pour moi le terme "théorème" est plutôt réservé à un énoncé majeur et non trivial. Or, cet énoncé est de démonstration tout à fait élémentaire (on pourrait le poser en examen à un première année d'université, probablement sans indication ou seulement avec l'indication de raisonner par parité), et je doute que ce soit le résultat essentiel de ce que tu souhaites faire. Il a probablement plus le statut de lemme, ou de résultat (personnellement je n'appellerai pas cela proposition non plus).

Et pour aller dans le sens de gérard0, il me semble qu'il faille introduire le $n$ avant le $f$.

lourrran

Je dirais même : il faut introduire $n$ avant $f_n$

Pavel Gorofsky

Bonjour, gerard0
Merci pour votre réponse constructive je vais répondre point par point

1) Pourquoi en anglais, 
Mes études se déroule à l'étranger malheureusement mes professeurs ne parlent pas la langue française 
2) Pourquoi ne pas simplement dire injective
Car mon devoir doit être rédigé en mathématiques "pure" on a l'obligation d'utiliser des symbole mathématiques et limiter la syntaxe.
3) Merci pour cette remarque il est vrai que c'est le cas je vais en tenir compte.
4) Idem il est vrai que cela importe peu je vais en tenir compte.
5) Il est obligatoire de mettre une référence dans ce devoir je suis obligé de citer un article, livre universitaire..... (dans la nouvelle version ci-dessous je place la référence en début de preuve).
Pour le reste de votre message je n'ai pas besoin de répondre si vous voulez décourager un étudiant qui tente une bonne rédaction d'une preuve mathématiques rien à redire. Je ne joue pas au mathématicien pro, je rédige simplement une réponse à un devoir où il est indiqué que chaque argument doit être détaillé et démontrer avec rigueur.

Ps. J'ai modifié "Theorem" et mis "Result" pour ne pas choquer...

Cordialement,
P.G

gerard0

PG.

1) Tu es sur un site français, la tradition est de s'y exprimer en français. On n'a pas à corriger un devoir d'étudiant, c'est pourtant ce que tu veux nous faire faire !!

2) Ta rédaction n'est pas purement en formules mathématiques, et "$f$ est injective" est parfaitement mathématiques. Il ne faut pas confondre mathématiques et cabalistique. J'ai d'ailleurs un gros doute sur la signification de tes nouvelles formules avec des $\wedge$ et la distinction que tu fais de $f(a,b,c)$ et $f(a',b',c')$ est toujours non signifiante. Comprends-tu vraiment ce que veut dire = en maths ??? Ça veut dire que c'est le même objet (ici le même nombre). Donc l'écrire de deux façons différentes ne dit rien !!

Pour le reste, je te laisse faire ce que tu veux, manifestement, il y a des éléments non mathématiques dans les exigences de tes formateurs, En tout cas, ça donne un texte grotesquement imitateur d'un article de chercheur. Sans quasiment de contenu mathématique ! Un joli paquet cadeau pour un colifichet d'occasion.

Pavel Gorofsky

gerard0

Merci pour votre réponse,

Je ne cherche pas à me faire corriger mais à échanger sur les notations et la manière de démontrer quelque chose.
Je tiens compte de vos remarques qui me font avancer dans mon travail. 
J'ai utilisé le signe ∧ car cela permet de dire "et" dans une ligne où je ne sais pas si mettre "et" est adéquate. Si vous avez des suggestions...
Je ne comprends pas lorsque vous évoquez "la distinction" entre $f(a,b,c)$ et $f(a',b',c')$ qu'entendez-vous par là ? 
Concernant le $=$ dire que $2a=2b$ implique que $a=b$ me semble correct, mais je pense avoir fait une erreur sinon vous ne l'évoqueriez pas.
Cordialement.

gerard0

Heu ... si tu mettais autant d'effort à lire pour comprendre mes phrases qu'à faire semblant d'écrire des maths, tu progresserais.

* La distinction, c'est toi qui la fais, à écrire sans arrêt $f(a,b,c)=f(a',b',c')$. C'est toi qui écris !!

* Le $\wedge$ signifie plein de choses, "et" en logique, "produit vectoriel", "pgcd", etc. Ce que tu écris n'a aucun sens ! Et montre seulement que tu veux faire bien.

* J'ai parlé de la signification de "=", pas d'une implication dans ton texte. Il y a au moins une vingtaine de "=" dans ton texte !!

Mais contrairement à tes dires, tu ne veux pas avoir un texte mathématique, tu veux avoir un texte qui correspond à ton idée fausse de ce qu'est un texte mathématique : Illisible.

Et tu le ressors fièrement à chaque fois !!

JLT

Ce que dit gerard0 c'est que pour exprimer mathématiquement "$x$ et $y$ appartiennent à $A$", il ne faut pas écrire "$x\wedge y\in A$". Si on tient à utiliser le symbole $\wedge$, on peut écrire $(x\in A)\wedge (y\in A)$. Mais le mieux serait d'écrire "$x\in A$ et $y\in A$".

JLapin

Pavel Gorofsky a dit :

gerard0

Merci pour votre réponse,
Je ne cherche pas à me faire corriger mais à échanger sur les notations et la manière de démontrer quelque chose
Je tiens compte de vos remarques qui me font avancer dans mon travail. 

Voici une remarque : utilise davantage le langage courant.

J'ai vraiment du mal à imaginer qu'un professeur de maths impose une pareille purge à ses étudiants : as-tu un énoncé précis de la consigne ?

Pavel Gorofsky

gerard0

Merci de ta réponse Gérard encore une fois tu illustres ton entreprise de croisade contre une certaine hérésie de ma part alors que je suis là je le répète pour échanger sur une preuve en maths pas pour autre chose, contrairement aux autres ici les gens apportent des réponses qui aident avec une explication...

"Heu ... si tu mettais autant d'effort à lire pour comprendre mes phrases qu'à faire semblant d'écrire des maths, tu progresserais" je te demanderais de rester polis et pas juger, tes relations sociales doivent être catastrophique mon vieux. Et arrête de penser que tout le monde est se croit fier et pense être le premier partout.

Merci JLT je vais supprimer ∧ et modifier mon texte. Et merci aux autres.

Il s'agissait d'un devoir en cryptographie, la consigne était la suivante :

"Déterminer une fonction permettant de chiffrer 3 bits. Vous démontrerez de manière rigoureuse en limitant au maximum la syntaxe que votre fonction est injective, une rédaction académique est attendue. L'idée de ce devoir est que vous présentiez une preuve mathématique. Une référence au choix devra être mentionnée."

Cordialement

Cyrano

Si je lis bien ce que tu écris, tu utilises une "référence" pour justifier le fait que des sommes/produits d'entiers donnent encore un entier.
Je pense que même ton formateur verra que ça n'a absolument aucune pertinence de mettre une référence à cet endroit.
Je te suggère de l'enlever et de la mettre en amont de la démonstration (par exemple une référence où quelqu'un a déjà traité un problème similaire). 

JLapin

Pavel Gorofsky a dit :

Il s'agissait d'un devoir en cryptographie, la consigne était la suivante :
"Déterminer une fonction permettant de chiffrer 3 bits. Vous démontrerez de manière rigoureuse en limitant au maximum la syntaxe que votre fonction est injective, une rédaction académique est attendue.

Je ne vois pas ce que l'on peut reprocher à ton premier essai : montrer qu'une fonction est injective en présentant les 8 valeurs prises me semble bien plus lisible que les autres tentatives.

Simplement, remplace la phrase quantifiée de ton énoncé par "Alors $f$ est injective." et enlève ces histoires de "compter les solutions" qui ne signifient pas grand chose.

Pour la référence, je ne comprends pas très bien ce qui est attendu : peut-être peux-tu indiquer à quel endroit tu as trouvé cette fonction ?