Bonjour, y aurait-t-il moyen de voir la démonstration d'Adrien qui lui a valu le prix d'élégance ? MErci : )

Bonjour,

Je n'ai plus l'originale, mais je peux néanmoins recopier la version reprise dans le livret qu'on a reçu a la proclamation : (il s'agit de la réponse à la troisième question de l'olympiade MAXI)

L'énoncé :

Dans une salle de spectacle se trouvent 20 rangées de 12 fauteuils chacune, les fauteuils formant aussi 12 colonnes. Lorsqu'ils prennent place, les spectateurs s'assoient toujours de sorte à former dans chaque rangée un intervalle (c'est-à-dire que les sièges d'une rangée entre deux sièges occupés sont eux-mêmes tous occupés). Une fois les spectateurs assis, on compte pour chaque colonne le nombre de sièges qui y sont occupés, ce qui fournit une liste de 12 naturels. Les listes de 12 nombres naturels qui sont obtenues de cette manière sont dites réalisables.

(a) La liste (5,5,5,5,2,1,0,2,3,6,7,5) est-elle réalisable ? Et la liste (1,2,8,1,7,4,1,6,1,1,4,1) ?

(b) Toute liste de 12 nombres naturels tous inférieurs à 5 est-elle réalisable ?

(c) Quel est le plus grand nombre naturel k tel que toute liste de 12 nombres naturels tous compris entre 0 et k est réalisable ?

(d) Quel est le plus petit nombre naturel k tel que toute liste de 12 nombres naturels tous compris entre k et 20 est réalisable ?

(e) Donner un test (portant uniquement sur les 12 nombres ) permettant de déterminer si une liste est réalisable ou non.

La réponse inspirée de la mienne : (je réponds d'abord à la cinquième partie de la question)

Introduisons d'abord la notion de partie positive d'un réel (et la notation pour la désigner) :


Remplissons les colonnes les unes après les autres en commençant par une extrémité. Pour remplir la première colonne, nous utilisons rangées.
Pour la deuxième, si , nous réutilisons des rangées parmi celles-là (car il faut les économiser) ; si , en plus de réutiliser ces rangées, nous devons en utiliser nouvelles. Ainsi nous aurons utilisé, dans tous les cas, nouvelles rangées.
Pour la troisième colonne, si , nous réutilisons des rangées parmi les rangées dont le deuxième siège est occupé ; si , en plus de réutiliser ces rangées, nous devons en utiliser nouvelles (il est interdit de réutiliser des rangées dont le premier siège est occupé mais pas le deuxième car cela créerait des «trous»). Ainsi nous aurons utilisé, dans tous les cas, nouvelles rangées.
Nous procédons de la même manière pour les colonnes restantes. Ceci montre que pour placer tous les spectateurs,

rangées sont nécessaires, mais aussi suffisantes. Or nous en avons 20. Il faut et il suffit donc que soit inférieur à 20. Remarquons que ce nombre s'exprime encore


En utilisant ce critère, les autres questions se résolvent de manière immédiate :

Je laisse cet exercice au lecteur (je n'ai pas envie de les recopier ).