Les dattes à Dattier

Un problème, une question, un nouveau théorème ?

Messages : 6

Inscription : 30 avr. 2017 01:48

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par oty20 » 17 juin 2018 09:26

matmeca_mcf1 a écrit :
14 juin 2018 15:31
Posons $ A $ la matrice symétrique définie positive de taille $ n $ qui vaut 2 sur la diagonale et 0 ailleurs. Posons $ \vec{b} $ le vecteur colonne de taille $ n $ et dont la $ i $eme composante vaut $ i $. On pose la fonctionnelle:
$$
\psi:\mathbb{R}^n\to\mathbb{R}\\
\vec{x}\mapsto \frac{1}{2}\vec{x}^\top A\vec{x}-\vec{b}^{\top}\vec{x}.
$$
Le problème revient à trouver le minimum de $ \psi $. On vérifie aisément que $ \psi $ est continue sur $ \mathbb{R}^n $, et que $ \psi(x) $ tend vers $ +\infty $ quand $ \lVert\vec{x}\rVert $ tend vers $ +\infty $. Donc $ \psi $ admet au moins un minimum. De plus $ \psi $ est strictement convexe donc ce minimum est unique. En calculant la différentielle de $ \psi $, on obtient
$$
\mathrm{d}\psi(\vec{x})(\vec{h})=\vec{h}^\top(A\vec{x}-\vec{b})
$$
Au point où le minimum de $ \psi $ est atteint, cette valeur s'annule pour tout $ \vec{h} $. Donc, le minimum est atteint en $ \vec{x}=A^{-1}\vec{b} $.

Revenons au cas particulier. On a donc ue le minimum est atteint quand $ x_i=i/2 $. Et le minimum est $ -\frac{1}{4}\sum_{i=1}^{n}i^2 $.


Bonjour, n'est ce pas la forme différentiel de la méthode du multiplicateur de Lagrange ?
''L’ennemi du savoir , n'est pas l'ignorance , mais l'illusion du savoir '' .

Messages : 0

Inscription : 29 mai 2018 14:26

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par alvaare » 20 juin 2018 08:47

Dattier a écrit :
19 juin 2018 21:59
Bonsoir,

énoncé 148 : dénombrement
On prend une urne pleine de k boules blanches indiscernables et n boules noires indiscernables.
On tire toutes les boules une à une sans remise.
Combien y-a-t-il de tirages possible, avec pour dernière boule tirée, une boule noire ?

Bonne soirée.
Par symétrie, cet exercice revient à trouver les tirages possibles qui commencent par une boule noire. On peut alors enlever cette boule de l'urne et chercher tous les tirages possibles avec k boules blanches et n-1 boules noires: $ {n+k-1}\choose{k} $
2016-2017: MPSI LLG
2017-2018: MP* LLG
2018-2019: DI ENS Ulm

Messages : 0

Inscription : 08 mars 2018 21:42

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par 1sala23 » 02 juil. 2018 00:16

Dattier a écrit :
14 juin 2018 14:51
Salut,

énoncé 145 : minimisation
Trouver le minimum de : $ \sum \limits_{i=1}^n (x_i^2-i\times x_i) $.

Bonne journée.
$ \sum \limits_{i=1}^n (x_i^2-i\times x_i) = \sum \limits_{i=1}^n (x_i\times (x_i - i)) $

L'extremum de la fonction $ f(x_i) = x_i^2 -ix_i $ est $ -\frac{-i}{2\times 1} $ soit $ \frac{i}{2} $. Donc le minimum de $ \sum \limits_{i=1}^n (x_i^2-i\times x_i) $ s'obtient avec $ x_i = \frac{i}{2} $.

Et $ \sum \limits_{i=1}^n ((\frac{i}{2})^2-i\times \frac{i}{2}) $
$ = \sum \limits_{i=1}^n (-\frac{i^2}{4}) $
$ = -\frac{1}{4} \times \sum \limits_{i=1}^n i^2 $
$ = -\frac{1}{4} \times \frac{n(n+1)(2n+1)}{6} $
$ = -\frac{n(n+1)(2n+1)}{24} $
[2015 - 2018] Lycée à Metz
[2018 - 2019] MPSI2 Lycée Louis-Le-Grand
[2019 - 2020] MP* Lycée Louis-Le-Grand

Messages : 294

Inscription : 27 oct. 2017 10:55

Profil de l'utilisateur : Professionnel

Re: Les dattes à Dattier

Message par Hibiscus » 02 juil. 2018 02:54

C'est pas des maths, mais vu l'ambiance du fil, je me suis dit, pourquoi ne pas le proposer :
(peut-être est-il mieux placé dans la rubrique des rentrées en mpsi...)

Soit A le langage constitué de la seule chaîne s, telle que

$ s= \begin{cases} 0 &\text{Si Dieu n'existe pas} \\
1 & \text{Si Dieu existe}\\
\end{cases} $

Est-il décidable ? Pourquoi ?
Masséna (PC*) -- X15 -- Spatial.

Messages : 0

Inscription : 08 mars 2018 21:42

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par 1sala23 » 02 juil. 2018 10:21

Hibiscus, je ne comprends pas la question, que veux dire "Est-il décidable" ?
[2015 - 2018] Lycée à Metz
[2018 - 2019] MPSI2 Lycée Louis-Le-Grand
[2019 - 2020] MP* Lycée Louis-Le-Grand

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par siro » 02 juil. 2018 10:33

Une notion d'info théorique, tu verras ça normalement en 1A/L3 dans une école qui enseigne l'info théorique.

https://fr.wikipedia.org/wiki/D%C3%A9cidabilit%C3%A9

En gros, pour faire simple, une question décidable est une question à laquelle on peut répondre "oui ou non". Par exemple "pour p donné, p est-il premier ?" est décidable. Par contre, "pour X un programme informatique, X va-t-il se terminer" est a priori indécidable.

(Je reste flou sur le sens précis des termes. En général on enseigne ça avec les machines de Turing.)

@Hibiscus : t'es sûr que c'est au programme de MPSI (ou même de prépa), la décidabilité ? Moi pas...
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Messages : 0

Inscription : 19 avr. 2015 00:08

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par darklol » 02 juil. 2018 11:28

Même si la chaîne $ s $ de Hibiscus avait un sens mathématique, la question serait triviale étant donné que tout langage fini est décidable.

Pour formaliser, on suppose qu’il existe un théorème (prédicat sans variables libres) $ P $ de la théorie ZF qui exprime l’existence de Dieu. L’ensemble de Hibiscus est bien défini par un axiome de compréhension:
$
A = \{ \{ x \in \{\emptyset\} | P \} \}
$ en utilisant évidemment la construction de Von Neumann pour les entiers: $ 0 = \emptyset $, $ 1 = \{ \emptyset \} $. Alors comme je l’ai dit: $ A $ est de cardinal 1 donc décidable.

Pour mieux comprendre pourquoi c’est vrai: impossible de savoir a priori si $ P $ ou $ \lnot P $ est prouvable dans ZF. Mais dans un modèle de ZF donné, le langage $ A $ est égal soit à $ \{0\} $, soit à $ \{1\} $ et est dans chaque cas trivialement décidable. La propriété « $ A $ est décidable » étant vraie dans tout modèle de ZF, elle est prouvable dans ZF d’après le théorème de complétude.

Maintenant, on est sur un forum de classes prepas donc ça serait pas mal que les énoncés:
- aient un sens
- soient au moins compréhensibles par des gens en prépa (« rubrique des rentrées en MPSI » lol)
Si la preuve d’un énoncé est de surcroit accessible en prépa, ça devient un bon énoncé. Notons que l’énoncé d’Hibiscus ne vérifie aucun des précédents critères, en plus d'être absolument trivial (preuve en 5 mots).
ENS Lyon
Ingénieur de recherche

Messages : 109

Inscription : 18 avr. 2018 19:17

Profil de l'utilisateur : Enseignant (CPGE)

Re: Les dattes à Dattier

Message par Simon Billouet » 02 juil. 2018 13:33

siro a écrit :
02 juil. 2018 10:33
@Hibiscus : t'es sûr que c'est au programme de MPSI (ou même de prépa), la décidabilité ? Moi pas...
Non non, ce n'est pas même au programme de l'option informatique. C'est une tentative d'humour, je dirais. :)
Professeur de mathématiques et d'informatique en PCSI au lycée Champollion.

Messages : 0

Inscription : 08 juin 2016 21:39

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par Zetary » 02 juil. 2018 13:37

Ou plutôt un aperçu de logique intuitionniste…

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par siro » 02 juil. 2018 14:10

Pas besoin de logique intuitionniste pour parler de décidabilité (et vice-versa).
Simon Billouet a écrit :
02 juil. 2018 13:33
siro a écrit :
02 juil. 2018 10:33
@Hibiscus : t'es sûr que c'est au programme de MPSI (ou même de prépa), la décidabilité ? Moi pas...
Non non, ce n'est pas même au programme de l'option informatique. C'est une tentative d'humour, je dirais. :)
La vache, il est abyssal cet humour... (et si c'est moi qui dit ça faut s'inquiéter)
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Verrouillé