Exos sympas MP(*)

[GaBuZoMeu]

Cela m'importe peu.

[GaBuZoMeu]

Je corrige mon erreur (je m'étais trompé dans l'écriture de ma matrice de transition) : le nombre d'entiers naturels strictement plus petits que $ 10^{100} $ qui contiennent 1939 dans leur écriture décimale est
965641125213866529787490970661385992829357775374880527132967360853703473258751983
46748872295250001

[loupiot_berthelot]

Histoire de remettre quelques problèmes intéressants (moyennement dans l'esprit des exos MP) sur ce fil :

Combinatoire

Soit $R_s(l)$ le plus petit entier $n$ tel que pour tout coloriage en $s$ couleurs des arêtes du graphe complet $K_n$, il existe un $K_l$ monochrome.
Montrer que $R_s(3) > 2^s$

Formes quadratiques
Soit $k$ un corps fini de caractéristique différente de 2. Soient $a,b \in k$, tels que $a,b \neq 0$.
Montrer qu''il existe $x,y \in k$ tels que $ax^2 + by^2=1$.

Difficile : dénombrer le nombre de solutions.

Ce résultat permet de classifier les formes quadratiques sur un corps fini.

Matrices

Soit $\mathbb{A}$ un anneau, et $A \in \mathcal{M}_{n,m}(\mathbb{A}), C \in \mathcal{M}_{m,n} (\mathbb{A}), n<m$.
On désigne par $\mathcal{P}_{m,n}$ l'ensemble des parties à $n$ éléments de $[\![1,m]\!]$
Pour $\alpha \in \mathcal{P}_{m,n}$, on désigne par $C_{1...m, \alpha}$ la matrice $C$ dont on a gardé que les lignes d'indice dans $\alpha$, et $A_{\alpha, 1...m}$ la matrice $A$ dont on a gardé que les colonnes d'indice dans $\alpha$.

Montrer que $\displaystyle det(CA) = \sum_{\alpha \in \mathcal{P}_{m,n}} det(C_{1...m, \alpha}) det(A_{\alpha, 1...m})$


On note $\mathcal{D}_r(A)$ l'idéal de $\mathbb{A}$ engendré par les mineurs d'ordre $r$ de $A$.
Soit $A \in \mathcal{M}_{m,n}(\mathbb{A})$, montrer que $A$ est surjective ssi $\mathcal{D}_m(A) = <1>$.

[Contrexemple]

Soit $p$ entier premier, $f$ une fonction de $A=\mathbb F_p^n$ dans $\mathbb F_p$, avec $n\geq p+1$.

A-t-on pour toutes $x\in A, \sum\limits_{\sigma \in S_n} s(\sigma) \times f(x_\sigma) =0$?

$s$ la signature

[GaBuZoMeu]

Comment calculer le nombre d'entiers naturels ayant au plus k chiffres et contenant 1939 dans leur écriture décimale ?
On considère cinq états pour un entier
4 : contenir 1939 dans son écriture décimale
3 : non état 4 et terminer par 193
2 : non état 4 et terminer par 19
1 : non état 4 et terminer par 1
0 : aucun des précédents
La matrice de transition entre états quand on ajoute un chiffre à la fin est :
$
T=\begin{pmatrix} 9&1&0&0&0\\ 8&1&1&0&0\\ 8&1&0&1&0\\ 8&1&0&0&1\\0&0&0&0&10 \end{pmatrix} $
et le nombre voulu est $ T^k[0,4] $ (j'indice à partir de 0).
Ceci se programme facilement en python.

Code : Tout sélectionner

import numpy as np

T=np.zeros((5,5),dtype=object)
T[4,4]=10
T[0,0]=9
T[0,1]=1
for i in range(3) :
    T[i+1,0]=8
    T[i+1,i+2]=1
    T[i+1,1]=1

Apres100=np.linalg.matrix_power(T,100)
Apres100[0,4]

9656411252138665297874909706613859928293577753748805271329673608537034732587519
8346748872295250001

[GaBuZoMeu]

La classification des formes quadratiques sur un corps fini et la formule de Cauchy-Binet me semblent plus être des morceaux (assez classiques) de cours que des exercices.

[loupiot_berthelot]

Heureux d'apprendre que les théorèmes de Witt font intégralement partie du programme de mpsi

[Contrexemple]

Études des formes quadratique sur corps fini : https://agreg-maths.fr/developpements/28

Pour sortir du classique, on peut munir la courbe : $x^2+y^2=1$ d'une addition de point (comme pour les courbes elliptiques).

Cryptographiquement cela n'a que peu d'intérêt, en effet on peut établir un isomorphisme entre ce groupe et un sous groupe du groupe multiplicatif d'ordre $q^n-1$, pour un certain $n$ bien choisie, ce qui n'est pas, forcément, le cas des courbes elliptiques.

[Mourien]

Les formes quadratiques ne sont pas au programme des concours.

[GaBuZoMeu]

Bof, il n'est pas question de théorème de Witt pour la classification des formes quadratiques sur un corps fini ! Et je n'ai en plus jamais dit qu'il s'agissait d'un morceau de cours de MPSI.