Dans cet exercice, le symbole
désigne un entier naturel, avec
; tous les ensembles considérés sont non vides, finis et constitués de nombres réels distincts ; de plus, on conviendra d’écrire tout ensemble fini
à
éléments réels distincts en ordonnant toujours
si bien que
En particulier, lorsque
et donc
est un singleton,
.
On dit que l’ensemble
est à sommes toutes distinctes (en abrégé que
est STD) quand, pour toutes parties non vides distinctes
et
de
,
. Cela revient à demander aux
sommes que l’on peut former avec des éléments de
d’être toutes distinctes.
Par exemple,
est STD parce que les nombres
sont tous distincts. En revanche,
n’est pas STD parce qu’en prenant
et
, on a
, bien que
.
Partie 1 - Exemples et contre-exemples simples
1.Expliquer pourquoi le nombre de sommes à envisager pour étudier le caractère STD de
vaut
.
2.Montrer que l’ensemble
est STD mais que l’ensemble
ne l’est pas.
3.Quel(s) ensemble(s)
contenant
est (sont) STD ?
4.Soit
et
deux ensembles non vides et finis de réels distincts, avec
(c’est-à-dire que
est un sous-ensemble de
).
a.Si
est STD, justifier que
l’est aussi.
b.L’ensemble
peut-il être STD si
ne l’est pas ?
5.Soit
un ensemble non vide et fini de réels distincts. On suppose que
n’est constitué que de nombres entiers et qu’il est STD. Justifier que
puis que
sont aussi STD.
Partie 2 - Construction d’une suite
On considère la suite
définie par
et par la relation de récurrence, valable pour tout
,
6.Vérifier que
et
. Calculer
.
7.Rédiger sur votre copie un programme en langage Python qui renverrait
(qu’on ne calculera pas).
8.Étudier le sens de variation de la suite
.
9.Montrer que, pour tout
, l’ensemble
est STD.
10.Montrer que
est en fait une suite géométrique que l’on déterminera.
Partie 3 - Suites STD
Une suite
est diteSTD lorsqu’elle est strictement croissante, qu’elle est composée d’entiers strictement positifs et que, pour tout
, l’ensemble
est STD.
Par exemple, la suite étudiée dans la partie 2 est une suite STD.
11.Soit (𝑢𝑛) une suite STD quelconque.
a.Montrer que pour tout
:
.
b.En déduire que pour tout
:
.
12.Le but cette question est d’affiner la minoration obtenue à la question précédente. Pour ce faire, nous aurons recours aux probabilités, et nous dirons qu’une variable aléatoire
à valeurs dans un ensemble réel fini non vide
à
éléments distincts suit une loi uniforme quand toutes les valeurs qu’elle peut atteindre sont équiprobables. Ainsi,
.
a.Soit
une suite STD quelconque. Pour
, on considère les variables aléatoires indépendantes
qui suivent la loi uniforme sur la paire
: ainsi, pour chacun des indices
.
On pose
.
On admet que
et que
.
Après avoir justifié que
et
, calculer l’espérance
et exprimer la variance
en fonction de
.
b.Montrer que
suit une loi uniforme sur un ensemble de
entiers relatifs, symétrique par rapport à
, et dont les éléments sont non nuls et de la même parité.
c.En déduire que pour
,
.
d.Proposer une valeur de
pour laquelle cette inégalité fournit un minorant plus grand qu’en11.b.
Plus fort ! - Olympiades 2023 Exercice 1
Dans tout ce problème,
désigne un entier naturel supérieur ou égal à
.
Un joueur dispose de
cartes numérotées de
à
. Il les mélange puis note dans l’ordre la suite des numéros des cartes obtenue. On appellelistela suite des numéros ainsi observés.
Le nombre
sera appelélongueurde la liste.
Par exemple, avec
, une liste possible est
.
Avec une liste donnée, le joueur marque un point chaque fois que le numéro d’une carte est supérieur à celui de la carte précédente.
Par exemple avec la liste
, le joueur marque
points.
On appellescorele nombre de points marqués par le joueur. Le score précédent est donc
.
1. Quelques exemples
a.Donner un autre exemple de liste de longueur
et de score
.
b.Donner toutes les listes de longueur
possibles ainsi que les scores correspondants.
2.Écrire sur votre copie la syntaxe d’une fonction Python qui, prenant en argument une liste
et sa longueur
, renvoie le score de la liste
.
On revient au cas général ainsi qu’à des considérations théoriques.
3.Démontrer que tout score est compris entre
et
. Donner une liste dont le score vaut
et une liste dont le score vaut
.
4.Soit
un entier compris entre
et
.
a.Démontrer qu’il existe une liste de longueur
et de score
.
b.Peut-on trouver deux listes de longueur
et de score
?
On note désormais
le nombre de listes de longueur
et de score
.
5.Déterminer
et
.
6. Une relation de récurrence
a.Déterminer
,
et
. Comment insérer dans la liste
la carte portant le numéro
pour obtenir une liste dont le score vaut encore
?
b.Comment insérer dans la liste
la carte portant le numéro
pour obtenir une liste dont le score reste nul ?
c.Vérifier que
.
d.Montrer que pour tout entier naturel
,
.
e.Pour tout
et pour tout entier naturel
non nul, exprimer
à l’aide de
et
.
f.Dresser un tableau des valeurs de
pour \(n\in \{3,4,5\}\)et
.
Étiquetage gracieux d'une figure - Olympiades 2022 Exercice 1
On considère un ensemble fini de points. On relie certains de ces points par des segments. L’ensemble ainsi constitué est appeléfigure.
On effectue l’étiquetaged’unefigurecomportant
segments en associant à chaque point un entier compris entre
et
, ces entiers étant distincts deux à deux.
On attribue à chaque segment la valeur absolue de la différence des entiers associés à ses extrémités. Cet entier est appelépondérationdu segment.
On dit que l’étiquetagede la figure estgracieuxsi les
pondérations obtenues sur les segments sont exactement tous les entiers de
à
.
On donne ci-dessous un exemple d’étiquetagegracieuxd’une figure comportant
points et
segments :
Figure étiquetée.
Figure étiquetée avec indication des pondérations/
A. Des exemples
1.Pour chacune des figures ci-dessous, préciser si l’étiquetage proposé est un étiquetage gracieux.
2.Compléter l’étiquetage de la figure ci-dessous pour obtenir un étiquetage gracieux.
B. Cas des lignes
Pour tout entier naturel non nul
, on considère la figure
constituée de
points alignés et des
segments joignant des points voisins.
On propose ci-dessous l’étiquetage gracieux des points de la figure
.
1.Montrer qu’on peut trouver un étiquetage gracieux pour chacune des figures
,
et
.
2.On admet qu’on peut trouver un étiquetage gracieux pour la figure
tel que le point le plus à gauche soit étiqueté avec
. Décrire cet étiquetage.
C. Cas des polygones
1.Montrer que tout triangle et tout quadrilatère peut être muni d’un étiquetage gracieux.
2.On a représenté ci-dessous un polygone à
côtés muni d’un étiquetage gracieux.
En déduire un étiquetage gracieux pour un polygone à
côtés.
3.Déterminer la parité de la pondération d’un segment lorsque les étiquettes de ses extrémités sont :
a.de parités différentes ;
b.de même parité.
4.En déduire qu’on ne peut pas trouver un étiquetage gracieux pour les pentagones.
D. Une très grande figure
On note
la figure constituée de
points telle que tout couple de points est relié par un unique segment.
1.Montrer que
est constituée de
segments.
2.On suppose qu’il existe d’un étiquetage gracieux de
.
a.Quel est le nombre de segments dont la pondération est un nombre impair ?
b.On note
le nombre de points étiquetés avec un nombre pair. Exprimer en fonction de
le nombre de segments dont la pondération est un nombre impair.
3.Montrer finalement que
ne peut pas être muni d’un étiquetage gracieux.
Addition du cancre, suites de Farey et cercles de Ford - Olympiades 2020 Exercice 1
Dans tout l’énoncé,
,
,
,
désignent des entiers naturels, avec
et
.
Partie A - L’addition du cancre
Le bon élève sait que, pour additionner deux fractions
et
, il faut d’abord réduire ces fractions au même dénominateur.
Toutefois, pour
et
deux fractions irréductibles, on définit « l’addition du cancre », notée
par :
.
Ainsi, si avec l’addition standard,
, on aura avec « l’addition du cancre »
.
1.Calculer
puis
. Pourquoi est-il important de supposer
et
irréductibles ?
2.Justifier que
et que
. Que dire de la nécessité des parenthèses ?
On dit que l’addition des cancres n’est pas associative.
3.Justifier que
et calculer
. Que dire de la nécessité des parenthèses ?
On dit que l’addition des cancres n’est pas distributive.
4.Justifier que si
et
sont des fractions irréductibles, alors
.
Partie B - Suites de Farey
Pour tout entier
, on appellesuite de Fareyd’ordre
, notée
, la liste, rangée dans l’ordre croissant, des fractions irréductibles comprises entre
et
, dont le dénominateur ne dépasse pas
.
Par exemple, en remarquant que
et
, on a :
etc.
Le diagramme ci-dessous permet alors de représenter les différents termes des suites de Farey :
1.Recopier et compléter le schéma précédent, et déterminer
,
,
.
2.Justifier que, pour tout
, les termes d’une suite
sont aussi des termes de
.
3.Montrer que, pour tout
, si
et
sont deux fractions consécutives de
, avec
, alors l’une au moins de ces deux fractions appartient à
.
4.Soit
et
deux fractions consécutives dans cet ordre d’une suite de Farey.
On admettra pour toute la suite de l’énoncé que dans ce cas, on a
.
Montrer qu’alors
.
Un candidat attentif remarquera que, plus précisément,
est la première fraction qui apparaît entre
et
dans la suite de Farey d’ordre supérieur. Ce résultat ne sera pas démontré ici.
5.Voici un algorithme écrit dans le langage Python
. Si
est un réel entre
et
, que représentent les valeurs
,
,
et
renvoyées ?
Partie C - Cercles de Ford
On appelle cercle de Ford associé à une fraction irréductible
le cercle de centre le point de coordonnées
et de rayon
. On peut alors représenter les différentes suites de Farey avec ces cercles de Ford.
Par exemple, la suite
se représente par les différents cercles ci-dessous :
L’objectif de cette partie est de démontrer la propriété suivante : « Les cercles de Ford associés à deux termes consécutifs d’une même suite de Farey sont tangents entre eux. »
1.Préciser les coordonnées des points 𝐴 et 𝐵, centres des cercles de Ford respectivement associés à
et
, où
et
sont deux fractions consécutives d’une même suite de Farey.
2.Montrer alors que
.
3.Conclure.
(***)image Olympiades 2019 - Somme de carrés
Un nombre entier
étant donné, on cherche dans cette partie à estimer
.
Sur la photo, on a représenté une pyramide de boulets de pierre, à base carrée, avec
étages qui contiennent
boulets. Le nombre de boulets qui la composent est
.
1.Dans le cas
, le puzzle présenté ci-dessous permet d’estimer
. Comment ? Quelle valeur obtient-on par cette méthode ?
2.Les exemples précédents inspirent la formule
.a.Montrer que l’entier
est bien un multiple de
et de
.b.Si on suppose que, pour un certain
, sur lequel on ne fait aucune autre hypothèse,
, quelle formule obtient-on pour
? On peut donc décider que la formule de
est vraie pour tout entier
.
3.Montrer que
, somme des
premiers carrés, est un carré.