Track / Stage 4 / 68 of 340 #328 of 2000

Problem 328

AMC 12 late, AIME early

Combinatorics Difficulty 4.7 Prove it OFM 2013-2014 Envoi 2 · France · 2013

Problem:

Montrer que tout polyèdre a deux faces qui ont le même nombre de sommets.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Solution:

Soit $n$ le nombre de faces du polyèdre, et soit $F$ une face fixée : les arêtes de $F$ séparent $F$ de faces toutes différentes, donc le nombre d'arêtes de $F$ est inférieur ou égal au nombre de faces autres que $F$ . De plus, $F$ a au moins 3 arêtes. Chaque face a autant d'arêtes que de sommet, donc toute face a un nombre de sommets compris entre 3 et $n-1$ , soit $n-3$ possibilités. D'après le principe des tiroirs, il existe donc deux faces qui ont le même nombre de sommets.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.