Défis du calendrier mathématique Retour à la rubrique

Un défi par semaine

Avril 2021, 3e défi

Le 16 avril 2021 - Ecrit par Ana Rechtman Voir les commentaires (7)
Lire l'article en

Nous vous proposons un défi du calendrier mathématique chaque vendredi et sa solution la semaine suivante.

Le calendrier 2021 est en vente ! Il s’intitule : « Le ciel dans tous ses états ».

De janvier à décembre, à travers 12 textes superbement illustrés, découvrez l’histoire des équations cachées dans les trajectoires des planètes et des étoiles ainsi que le développement des grandes théories qui ont accompagné cette aventure.

Semaine 16

Combien peut-on construire de triangles (non-plats) dont les trois sommets sont placés sur des points de la même couleur ?

Solution du 2e défi d’avril :

Enoncé

La réponse est $(1,1,1)$, $(1,1,2)$ et $(1,2,3)$.

Comme $a\le b\le c$, on a $a+b\le 2c$.

De plus, $a+b$ est un multiple de $c$ donc, ou bien $a+b=c$, ou bien $a+b=2c$.

Si $a+b=2c$, comme on a $a\le c$ et $b\le c$, cela implique nécessairement que $a=c$ et $b=c$, donc $a=b=c$.

Comme ces trois nombres ne doivent pas avoir de diviseur premier en commun, on a nécessairement $a=b=c=1$.

Considérons maintenant le cas où $a+b=c$.

Les trois entiers $a$, $b$ et $c$ sont alors deux à deux premiers entre eux, car tout diviseur commun à deux de ces entiers est diviseur du troisième en utilisant la relation $a+b=c$.

Mais chacun des entiers $a$, $b$ et $c$ divise la somme $a+b+c$, donc le produit d’entiers premiers entre eux $abc$ aussi.

On obtient donc que $abc$ divise $a+b+c\le 3c$ et donc $ab\le3 $.

Si $a=b=1$, comme $c$ doit diviser $a+b=2$, $c$ peut prendre les valeurs $1$ ou $2$.

Si $a=1$ et $b=2$, alors seul $c=3$ convient.

Si $a=1$ et $b=3$, il n’y a pas de solutions possibles (car $c$ divise $4$, donc ne peut prendre que la valeur $4$, mais alors $b=3$ ne divise pas $a+c=5$).

Finalement, seuls les triplets $(1,1,1)$, $(1,1,2)$ et $(1,2,3)$ conviennent.

Post-scriptum :

Calendrier mathématique 2021 - Sous la direction d’Ana Rechtman,

Commentaire sur l'article

Avril 2021, 3e défi

le 16 avril 2021 à 09:42, par Al_louarn

Il y a $6$ points violets et $10$ points oranges, donc ça nous donne $\binom{6}{3} + \binom{10}{3} = 20 + 120 = 140$ triplets monochromes, dont il faut retrancher les triplets de points alignés.
J’en compte $2$ violets ($1$ vertical et $1$ en diagonale) et $9$ oranges ($2$ horizontaux, $5$ verticaux et $2$ en diagonale). Donc sauf erreur il y a $140 - 2 - 9 = 129$ triangles monochromes non plats.
Répondre à ce message
Avril 2021, 3e défi

le 16 avril 2021 à 11:09, par Christophe Boilley

La question qui vient juste après, bien sûr, c’est le nombre de triangles non plats avec des sommets sur les points colorés qui ne sont pas monochromes.
Répondre à ce message

Avril 2021, 3e défi

le 17 avril 2021 à 12:38, par Blaxapate

Il suffit de compter tous les triangles, de retirer les triangles plats, puis de retirer les triangles monochromes :

$\binom{16}{3}-44-129=387$
Répondre à ce message

Avril 2021, 3e défi

le 17 avril 2021 à 12:43, par Christophe Boilley

D’où la question à laquelle je n’ai pas encore de réponse : comment colorier les 16 sommets pour maximiser ce nombre de triangles bicolores ?
Répondre à ce message

Avril 2021, 3e défi

le 21 avril 2021 à 21:23, par drai.david

Bonsoir,
si je n’ai pas fait d’erreur, voici la réponse à votre problème :
$ $
• Il doit y avoir 8 points de chaque couleur.
$ $
• Il existe alors 16 dispositions possibles :
type 1 :
– 6 telles que chaque ligne est monochrome ;
– 6 telles que chaque colonne est monochrome ;
$ $
type 2 : 4 de la forme :
$ $
$ $ 1000
$ $ 1101
$ $ 1011
$ $ 0001
$ $
À partir de celle-ci, on en obtient une autre par symétrie d’axe horizontal (ou vertical) ;
On obtient les deux dernières en échangeant les 0 et les 1 des deux précédentes.
$ $
• Dans ces 16 configurations, on peut tracer 420 triangles bicolores.
Répondre à ce message

Avril 2021, 3e défi

le 23 avril 2021 à 11:48, par Christophe Boilley

Bravo ! La répartition 8-8 minimise effectivement le nombre de triplets monochromes, et pour faire au moins aussi bien avec une répartition déséquilibrée, il faudrait augmenter le nombre d’alignements monochromes.

Avec la répartition 5-11 ou un déséquilibre supérieur, le nombre de triades monochromes devient trop grand (≥ 175) pour qu’on puisse espérer descendre en dessous de 100 triangles monochromes.

Et même avec une répartition 6-10, pour réduire suffisamment les 140 triades monochromes, il faudrait arriver à garder 40 alignements monochromes, ce qui est impossible avec une répartition polychromatique. En effet, étant donnés deux sommets de couleur différente sur des lignes et colonnes différentes, au moins deux lignes ou colonnes ne sont plus monochromes ce qui supprime au moins 6 alignements.

Pour éliminer les répartitions 7-9, il suffit montrer qu’on ne peut conserver 20 alignements monochromes dans ce cadre.

Je ne vois pas pour l’instant de raisonnement simple pour terminer cette démonstration justifiant l’optimum annoncé. On peut bien sûr écrire un algorithme en force brute pour tester tous les cas (après tout, il n’y a que 12870 répartitions 8-8 sans même chercher à réduire par symétrie), mais je cherche ci-dessous une piste plus élégante. Avez-vous mieux ?

Chaque sommet appartient à au moins 7 alignements. Deux sommets ont au maximum deux alignements en commun, donc la perte de 2 sommets fait perdre au minimum 12 alignements. Trois sommets de côté ne peuvent appartenir deux à deux à des alignements sans qu’il y en ait un dans un coin, donc la perte de 3 sommets fait perdre au minimum 17 alignements. En retirant un quatrième sommet il peut avoir jusque quatre alignements communs avec deux des précédents, ce qui ne fait perdre au total que 20 alignements. Je pense qu’avec 5 sommets perdus on perd au moins 26 alignements, mais les sous-cas commencent à se multiplier.

De l’autre côté, je suis convaincu qu’avec 7 sommets on ne peut pas faire plus de 8 alignements, mais l’étude de cas est fastidieuse.
Répondre à ce message

Avril 2021, 3e défi

le 23 avril 2021 à 15:22, par drai.david

Non, honnêtement, je n’ai pas mieux : j’ai écrit un algorithme de force brute qui teste les 65 536 coloriages possibles... Enfin non, j’ai quand même eu la présence d’esprit d’exclure les deux carrés monochromes !!! 😄
Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexion | s’inscrire | mot de passe oublié ?

L'auteur

Ana Rechtman

Un défi par semaine

Avril 2021, 3e défi

Solution du 2e défi d’avril :

Commentaire sur l'article