Équations fonctionnelles OIM 1987 et 1994

Julia Paule

Je m'intéresse aux équations fonctionnelles (chose que je voulais faire depuis longtemps), et il semble qu'il n'existe que peu de théorie sous-jacente, mais plutôt des méthodes, astuces, habitudes, savoir-faire ?

Dans ce papier : https://igor-kortchemski.perso.math.cnrs.fr/olympiades/Cours/Equations fonctionnelles/eqfonc.pdf, je bute en page 15 sur la solution de l'exercice OIM 1987 : Prouver qu'il n'existe pas de fonction $f : \N^* \to \N^*$ telle que pour tout entier $n>0$, $f\big(f(n)\big)=n +1987$.

Il semble que la solution indiquée ne justifie pas :
1) pourquoi on n'envisage pas les cas $m \geq 2$ (s'ils sont possibles),
2) pourquoi la disjonction de cas $f(k)=n$ ou $f(n)=k$ induit qu'on peut répartir les entiers de $1$ à $1987$ par paires deux à deux disjointes (cela ne me semble pas logique).
Merci d'avance (si vous avez le courage de vous y pencher).

PierreB

Bonjour
Si $f(k) = g^m(n)$ alors, pour cause d'injectivité, on a $k = g^{m-1}(f(n)) = f(n)+1987(m-1)$.
Puisque $f(n) \in \mathbb{N}^*$ et que $k \in\{1,2, \dots , 1987 \}$, cela ne peut arriver que pour $m-1 \leq 0$.

Pour le second point, je ne sais pas ce qui n'est pas logique, mais peut-être est-ce justement parce que l'on construit notre contradiction...
Pierre.

dp

Il y a une résolution dans Olympiades internationales de mathématiques 1976-2005 aux éditions Cassini qui prend à peine quelques lignes, si jamais.

Julia Paule

Merci. Pour la 1) c'est mieux comme ça. C'est vrai que les solutions des exercices précédents qui étaient beaucoup plus détaillées, m'ont mal habituée.

Pour la 2), on a donc $f(k)=n$ ou bien $f(n)=k$, selon que $m=0$ ou $1$, avec $m$ dépendant de $k$, mais pas les deux en même temps (ou du moins, ce n'est pas montré). Du coup, je ne vois pas ce qui justifie comment on peut apparier les entiers de $1$ à $1987$ deux par deux, par exemple, rien n'interdit $f(1)=2, f(2)=3, \dots, f(1987)=f(1)$ ?

PierreB

Pour la 2), c'est toujours parce que l'on parle d'entiers entre $1$ et $1987$. Dès qu'on utilise $f \circ f$, on dépasse $1987$.

Ce n'est donc pas un "ou bien" c'est un soit l'un soit l'autre.
Pierre.

Julia Paule

Ok, c'est soit l'un soit l'autre. J'avoue que je ne vois pas la différence avec "ou bien". C'est donc soit $f(k)=n$, soit $f(n)=k$, tous deux compris entre $1$ et $1987$. Comment $f \circ f$ intervient pour justifier l'appariement ?

Je parlerais de classes d'équivalence modulo $1987$ : si on a $f(n)=k$, alors $f(f(n))=f(k)=n+1987$, idem pour l'autre, donc $f(k) \equiv n \pmod {1987}$, et $f(n) \equiv k \pmod {1987}$, finalement on peut les apparier.

Julia Paule

Merci @dp. Je ne dispose pas de ce livre. Mais je me rends compte que les 2 lignes que je viens d'écrire dans mon message précédent suffisent à justifier l'impossibilité, sachant que les classes sont en nombre impair, et que $f(n) \ne n$ (pas la peine de parler d'orbites).

dp

Je t'ai envoyé une photo de la solution donnée dans le livre en question en message privé.

Julia Paule

Merci @dp, c'est en effet beaucoup plus court ! $f$ passe au quotient, qui devient donc $f \circ f=Id$, c'est une involution, etc... , pas mal.

dp

Et toutes les autres sont du même tonneau. C'est vraiment un bouquin qui vaut son pesant de cacahouètes. De même pour le livre concernant les OIM 2006-2021, bien que l'approche soit quelque peu différente.

Julia Paule

D'accord, à l'occasion. En tout cas, résoudre des équations fonctionnelles est très instructif (tout ne se déroule pas dans un monde parfait comme d'habitude).
Pour l'équation du fil, je ne sais pas si on arrive à ce genre de solution très simple du 1er coup : on en trouve une, qu'on simplifie, qu'on simplifie encore, ... .
Sinon, pour l'équation $f(f(n))=n+2a$, $a>0$, $f : n \mapsto n+a$ n'est pas la seule solution, on trouve des contre-exemples.

JLapin

Une jolie solution non mentionnée ici se trouve à la page 106 de ce pdf (la deuxième méthode).

https://www.cs.nmsu.edu/~cvan/Web/IMO.pdf

Julia Paule

Merci @JLapin. La 1ère solution est lourde. La 2ème est intéressante et finalement assez intuitive. On peut l'alléger en remarquant que la restriction de $f$ à $A$ est une bijection de $A$ sur $f(A)=B$, donc $B=f(\N \setminus f(\N))=f(\N) \setminus f(f(\N)$. Mais elle part de $f$ définie sur $\N$ tandis que l'énoncé est sur $\N^*$, et bien que cela ne change rien, je préfère celle du livre.

Sinon, @PierreB, je viens de comprendre la différence que tu fais entre "ou bien", et "soit, soit". Il n'y a pas de doute que "ou bien" est un "ou" exclusif (ce que j'avais supposé implicitement, car on ne peut pas avoir $f(n)=k$ et $f(k)=n$ simultanément), mais pour toi, le "soit, soit" ne l'est pas, tandis qu'il le reste pour moi.

Julia Paule

Dans le même document, la solution de l'exercice OIM 1994 en page 17 se déroule en 1 page, et je trouve la solution en quelques lignes (j'ai peut-être fait une erreur) : https://igor-kortchemski.perso.math.cnrs.fr/olympiades/Cours/Equations fonctionnelles/eqfonc.pdf

Soient $\alpha, \beta \in \R$. Trouver toutes les fonctions $f : \R^+ \to \R$ telles que, pour tous réels $x,y \geq 0, f(x)f(y)=y^{\alpha}f(\frac{x}{2})+x^{\beta}f(\frac{y}{2})$.

Dans ce document : https://www.cs.nmsu.edu/~cvan/Web/IMO.pdf, l'énoncé n'apparait dans les exercices de l'OIM 1994 ?

Quelqu'un aurait-il une autre solution, éventuellement tirée d'un livre ?

dp

Si je me souviens bien (donc à prendre avec des pincettes), les pays participants envoient des exercices à proposer aux candidats et, parmi la myriade d'exercices envoyés, seuls six sont retenus chaque année. Ce qui expliquerait pourquoi ton exercice n'apparait pas dans la liste des OIM de 1994.

Julia Paule

Merci @dp. Ah d'accord, il y a 6 exercices proposés, ce sont peut-être ceux proposés par la France.

dp

Je ne me suis pas trompé

Wikipedia: Chaque pays, excepté le pays organisateur, peut proposer des problèmes au comité de sélection qui est mis en place par le pays organisateur, qui en sélectionne certains afin d'en écourter la liste. Les chefs de délégation arrivent quelques jours avant les élèves et se regroupent alors pour choisir les 6 exercices. Étant donné qu'ils connaissent les sujets avant les épreuves, ils sont séparés des élèves jusqu'à la fin de celles-ci. Les élèves sont accompagnés avant les épreuves par les chefs de délégation adjoints.

Julia Paule

Alors les sujets sont choisis parmi ceux proposés par les pays, donc les sujets choisis peuvent être connus des élèves du pays ?

dp

De toute manière en regardant les énoncés tu remarqueras qu'ils ont majoritairement la même structure et sont finalement réduit à quelques notions pas bien compliquées (les exercices en revanche… c'est une autre histoire !) faisant appel aux mêmes méthodes.
Une grande partie de ces méthodes sont au demeurant très bien exposées dans Solutions d'Experts d'Arthur Engel (traduit, ici encore, aux éditions Cassini. ❤️ sur eux).

JLapin

@Julia Paule

Les personnes qui proposent les sujets sont tenus à la stricte confidentialité.

[Utilisateur supprimé]

Julia Paule a dit :

Sinon, pour l'équation $f(f(n))=n+2a$, $a>0$, $f : n \mapsto n+a$ n'est pas la seule solution, on trouve des contre-exemples.

Ha oui ? Par exemple ?

Julia Paule

@turboLanding Par exemple, $f(n)=m$ et $f(m)=n+2a$, sachant que $f$ est injective et est entièrement déterminée par ses images de $1$ à $2a$.

Exo : trouver toutes les solutions.

Julia Paule

@dp Je ne vois pas la différence que tu fais entre les énoncés et les exercices ?

Personne pour l'énoncé plus haut ? https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2425111/#Comment_2425111

dp

Il n’y en a pas. Désolé. C’était une tentative maladroite de ne pas faire de répétition… cette injonction somme toute artificielle est trop ancrée en moi. 

Julia Paule

Merci pour le livre. Je me rends compte qu'il y a beaucoup de livres sur le sujet, par exemple celui-là très bien noté : https://www.amazon.fr/olympiades-mathématiques-Réflexes-stratégies/dp/2729836616/ref=pd_lpo_sccl_1/262-7461997-0054227?pd_rd_w=lBF7T&content-id=amzn1.sym.1bec6179-e78a-4900-91c1-a0cbdfe0e062&pf_rd_p=1bec6179-e78a-4900-91c1-a0cbdfe0e062&pf_rd_r=H0JRSVRMB1YKVHFTME3G&pd_rd_wg=AbKeO&pd_rd_r=ff858ec4-ff61-4a70-88f5-7574ffe8d9b6&pd_rd_i=2729836616&psc=1

En fait, j'ai mieux : https://les-mathematiques.net/vanilla/index.php?p=discussion/2066012#Comment_2066012 et https://les-mathematiques.net/vanilla/index.php?p=discussion/comment/410094#Comment_410094

Madec

Bonjour ,

Je reviens sur le premier exercice .
J'ai compris  à la lecture du fil qu'en travaillant modulo 1987  on pouvait définir une involution .
je note $* $pour les classes modulo 1987
En posant par exemple  $ g(n*)= (f(n))*$
On constate effectivement que $g°g =Id$
Mais pour obtenir la contradiction sur la parité impaire de l'ensemble des classes , on apparie les classes , ce n'est possible je pense que s'il n'y a aucun point fixe pour la fonction $g$
C'est sans doute simple , mais comment montrer que $ g(n*)\neq n*$ ?
Peut être que la fonction g que je propose n'est pas l'involution invoquée dans le fil ?

LOU16

Bonjour,

@Madec

$N=1987.\:\: $Supposons: $\exists n \in\N^*, \:g(\widehat n) =\widehat n.\:\:$

Alors, $\:\:\exists a\in [\![1;N]\!] $ tel que$\:f(a) =a+kN, \:\:k\in\N,\:\:\:(1).\quad f(a)=f^{\circ 2k}(a).\:\:(2)$

Il vient: $\:a+N=(f\circ f)(a)\overset{(2)}=f^{\circ 2k+1}(a) =f^{\circ 2k}(f(a))=f(a)+kN\overset{(1)} =a+2kN, \quad N=2kN.\:\: $ C'est impossible.

Madec

@LOU16
Merci !
Mais je n'ai pas compris les deux égalités suivantes.
$f(a)=f^{\circ 2k}(a).$
de même que
$f^{\circ 2k}(f(a))=f(a)+kN$.

LOU16

Re,

@Madec

Cela résulte de $ \forall x \in \N^*, (f\circ f)(x) =x+N,\: $ qui, par récurrence, entraîne: $\forall k\in\N,\:\:f^{\circ 2k}(x) =x+kN.$

Madec

Ok merci LOU16
c'est clair !
Très bel exo je trouve !

LOU16

Bonjour

 Une question formulée par @Julia Paule concerne la détermination de  $\mathcal F_a=\Big\{ f\in (\N^*)^{\N^*}\mid \forall x\in \N^*,\:(f\circ f)(x) =x+2a\Big\},\:$ 

Il m'a semblé que $\boxed{\#\mathcal F_a =\#\mathcal I_a=\dfrac{(2a)!}{a!},}\:$ où $\:\mathcal I_a=\Big \{(A,g)\mid A\in \mathcal P_a([\![1;2a]\!]),\:g\text{ bijection } A\to[\![1;2a]\!]\setminus A\Big\}.$

Notations : $\forall x\in\N^*, \:\widehat x $ désigne l'unique élément de  $[\![1;2a]\!] $ tel que $x\equiv \widehat x \mod 2a.$

On définit alors une bijection $\mathcal I_a\to \mathcal F_a,\:\:(A,g) \mapsto f_{(A,g)}$ de la façon suivante:

$$\forall x \in\N^*, \:\:f_{(A,g)}(x) =\left\{\begin{array}{cl}g(\widehat x)+x-\widehat x& \text{ si } \widehat x\in A.\\g^{-1}(\widehat x)+x-\widehat x+2a& \text{ si } \widehat x\notin A.\end{array}\right.$$

Julia Paule

Bonjour @LOU16 De mon côté, par un autre moyen, je trouve :

On groupe les classes de $1$ à $2a$ deux par deux, sachant que si $f(k) \equiv l \pmod {2a}$, alors $f(l) \equiv k \pmod {2a}$.

Cela fait $(2a-1)(2a-3) \cdots 3.1$ possibilités de groupements deux par deux.

Alors pour chaque groupement, on a deux possibilités : $f(k)=l$ et $f(l)=k+2a$, ou bien $f(l)=k$ et $f(k)=l+2a$.

En effet, si $f(k)=l+2aq$, alors $f(f(k))=k+2a=f(l+2aq)=2aq+f(l)$, et les seules possibilités sont $q=0$ et $q=1$.

Puis $f$ est entièrement déterminée.

Cela donne $2^a {(2a-1)(2a-3) \cdots 3.1}$ applications, idem.

Je regarde ta solution.

Julia Paule

Ok pour ta solution. $g$ regroupe les classes, donc les éléments de $[\![1;2a]\!]$ deux par deux. Pour $x \in \N^*$, on prend pour $\widehat x$ le reste de la division euclidienne de $x$ par $2a$ (plus exactement celui de $x-1$ auquel on rajoute $1$), et on a $f(x)=f(2aq+\widehat x)=2aq +f(\widehat x)$.

Plus précisément, choisir $f$ revient à choisir une partie $A=\{k \in [\![1;2a]\!] \mid f(k) \in [\![1;2a]\!] \}$, et une application $g$ de $A$ dans son complémentaire dans $[\![1;2a]\!]$. Il y en a : nombre de telles parties $A$ : $\binom {2a}{a}$ x nombre de bijections d'un ensemble à $a$ éléments dans un ensemble à $a$ éléments : $a!$, cela fait bien le résultat.

Après, c'est une question de se ramener à $g$, sachant que pour $x \in A, g(x)=f(x)$, et pour $x \in [\![1;2a]\!] \setminus A$, $f(x)=g^{-1}(x)+2a$.