OMB - OMB 2012 Finale MAXI Question 3

OMB 2012 Finale MAXI Question 3

3415 vues | Retourner à la liste des questions

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 $n_k$ ) permettant de déterminer si une liste $(n_1, n_2, n_3, n_4,n_5, n_6, n_7, n_8,n_9, n_{10}, n_{11}, n_{12})$ est réalisable ou non.

Solution(s) proposée(s) :
	Solution de Adrien Vandenschrick

Les commentaires appartiennent à leurs auteurs. Nous ne sommes pas responsables de leur contenu.

Anonyme	Posté le : 2/5/2012 18:16 Mis à jour : 2/5/2012
a) oui pour le premier (facile pour construire) et non pour le deuxieme (vois e) b) non (vois c) c) $040404040404$ montre que $k<4$ d) $20,19,20 \cdots$ et on a une contradiction, alors $k=20$ ici? e) quand $N_i \le N_{i+1} \le N_{i+2}$ ou $N_i \ge N_{i+1} \ge N_{i+2}$ remis $N_{i+1}.$ Si $N_1<N_$ remis N_1 aussi. Si le dernier nombre n'est pas plus grand que le nombre devant cet un, on le fait pas dans la nouvelle rangee. Avec les autres nombres: fais $\sum N_{2k+1} - \sum N_{2k}$ , ca doit etre moins ou equal au $20.$

Victor Lecomte	Posté le : 2/5/2012 19:25 Mis à jour : 2/5/2012
Malheureusement au (c) tu n'as pas prouvé que toutes les suites où les nombres sont inférieurs ou égaux à 3 sont réalisable, donc tu ne réponds pas à la question, et le (e)... mériterait un peu d’éclaircissements. :p

Anonyme	Posté le : 2/5/2012 22:36 Mis à jour : 2/5/2012
Il y a quelque chose de juste dans ce qu'il a ecrit? Parce que moi j'ai pas du tout la même chose..

Anonyme	Posté le : 3/5/2012 20:56 Mis à jour : 3/5/2012
Montrer que c marche avec $3$ , on doit voir $e$ ou c'est prouvé generallement. (a2, j'ai dit ça aussi). Victor, tu as les mëme réponses, que l'autre anonyme ne me crois pas. Enfin, prouvé e est assez pour tous, que les autres choses suivent d' e. ** e: On doit ajouter $N_{2k+1}-N_{2k}$ places minimum, parce que ces places de $2k+1^{ième}$ colonne ne peut pas avoir des chaises/ sièges en commune des collones utilisé plutôt. Alors on peut prouver très facile que cette condition est nécessaire et quand c'est bon, on peut aussi faire par placer les sièges de $N_{2k}$ entre les chaises de collonne $2k-1$ et $2k+1.$

Anonyme	Posté le : 4/5/2012 0:11 Mis à jour : 4/5/2012
Ben pour moi, 0 4 0 4 04 04 04 04 ça peut marcher..

Victor Lecomte	Posté le : 4/5/2012 17:28 Mis à jour : 4/5/2012
Voici en tout cas mes réponses finales (je n'ai pas le temps de justifier, mais je peux le faire plus tard) : (a) La première liste est réalisable, la seconde non (b) Non, exemple : 040404040404 (c) k=3 (d) k=20 (e) Il faut et il suffit que la somme de toutes les augmentations dans la suite (0, n1, n2, n3, ..., n12) soit inférieure ou égale à 20.

Anonyme	Posté le : 4/5/2012 18:06 Mis à jour : 4/5/2012
Ah, je suis content, ce sont les mêmes choses que moi. Si, c'est déja prouvé avec des autres mots.

Anonyme	Posté le : 4/5/2012 21:36 Mis à jour : 4/5/2012
101010101010 101010101010 000000000000 000000000000 101010101010 101010101010 000000000000 000000000000 000000000000 000000000000... Pourquoi cette configuration ne marche pas?

Victor Lecomte	Posté le : 4/5/2012 22:04 Mis à jour : 4/5/2012
Si tu regardes un peu l'énoncé, tu vois "les sièges d'une rangée entre deux sièges occupés sont eux-mêmes tous occupés"... Ce serait trop facile sinon !

Anonyme	Posté le : 4/5/2012 22:09 Mis à jour : 4/5/2012
Ben la, il n'y pas de rangé entre deux sièges occupés... Je ne comprends pas bien l'énnoncé

Victor Lecomte	Posté le : 4/5/2012 22:36 Mis à jour : 4/5/2012
Je ne sais pas pourquoi tout le monde a du mal avec cet énoncé... xD En gros ça veut dire que tous les sièges occupés d'une rangée sont côte à côte, il y a pas de trou entre deux sièges de la même rangée.

Anonyme	Posté le : 4/5/2012 22:56 Mis à jour : 4/5/2012
Ah ok ^^ C'est quand même plus clair comme ça.. On pourrait aussi le comprendre de cette manière : Si il y a une rangé dont un siège de la rangé supérieur et un siège de la rangé inférieur à celle-ci sont occupés alors tous les sièges de cetterangé sont occupés... Ça donnerait ça, 000100000000 111111111111 000000100000

Victor Lecomte	Posté le : 4/5/2012 23:02 Mis à jour : 4/5/2012
Ah oui j'avoue ! Comme quoi, il faut toujours mieux exprimer les choses avec le langage mathématique, comme ça pas moyen d'être ambigu.

Anonyme	Posté le : 6/5/2012 20:13 Mis à jour : 6/5/2012
(e) Voici le test que je propose. On calcule la fonction $f$ de la façon suivante : - $f(1)=20-n_1$ ; - $f(i)=f(i-1)-max\{0;n_i-n_{i-1}\}$ pour tout $i\in\{2,3,\ldots,12\}$ . Si $f(12)\geq 0$ , alors la liste $(n_1,n_2,\ldots,n_{12})$ est réalisable. Sinon, elle ne l'est pas. Preuve que ce test fonctionne. Imaginons qu'on essaie de placer les personnes colonne par colonne à partir de la première colonne en fonction de la liste $(n_1,n_2,\ldots,n_{12})$ en respectant la règle des intervalles décrites dans l'énoncé. En fait, tant que le nombre $f(i)$ est positif ou nul, il représente le nombre de rangées dans lesquelles aucune personne n'est assise sur les $i$ premiers sièges, si on économise au maximum le nombre de ces rangées en ne clôturant pas les intervalles entamés dans d'autres rangées quand cela n'est pas nécessaire. Si le nombre $f(i)$ est strictement négatif, c'est qu'on ne dispose pas d'assez de rangées pour que la liste soit réalisable jusque la colonne $i$ incluse. Si $f(12)$ est positif ou nul, on a pu asseoir tout le monde.

Anonyme	Posté le : 6/5/2012 20:43 Mis à jour : 6/5/2012
(a) Appliquons le test ci-dessus à la liste $(5,5,5,5,2,1,0,2,3,6,7,5)$ . Il vient successivement $f(1)=15$ , $f(2)=15$ , $f(3)=15$ , $f(4)=15$ , $f(5)=15$ , $f(6)=15$ , $f(7)=15$ , $f(8)=13$ , $f(9)=12$ , $f(10)=9$ , $f(11)=8$ , $f(12)=8$ . La liste est donc réalisable (et on n'a même pas besoin des huit dernières rangées). Appliquons le test ci-dessus à la liste $(1,2,8,1,7,4,1,6,1,1,4,1)$ . Il vient successivement $f(1)=19$ , $f(2)=18$ , $f(3)=12$ , $f(4)=12$ , $f(5)=6$ , $f(6)=6$ , $f(7)=6$ , $f(8)=1$ , $f(9)=1$ , $f(10)=1$ , $f(11)=-3$ . La liste n'est donc pas réalisable (il manque $3$ rangées car $f(12)=-3$ ). (b) Non car la liste $(5,0,5,0,5,0,5,0,5,0,0,0)$ n'est pas réalisable. Cela se vérifie directement avec le test donné ci-dessus. (c) La réponse est $k=3$ . D'une part, on vérifie directement à l'aide du test donné ci-dessus que la liste $(k,0,k,0,k,0,k,0,k,0,k,0)$ n'est pas réalisable pour $k\geq 4$ . D'autre part, on peut prouver au moyen du test que $f(12)\geq f(10)-k\geq f(8)-2k\geq f(6)-3k\geq f(4)-4k\geq f(2)-5k\geq 20-6k\geq 2\geq 0$ si $k\leq 3$ (ce qui implique que toute liste est réalisable pour $k\leq 3$ ). (d) La réponse est $k=20$ . En effet, la liste $(20,k,20,20,20,20,20,20,20,20,20,20)$ est réalisable si et seulement si $k=20$ , comme le montre le test ci-dessous.

Anonyme	Posté le : 6/5/2012 20:52 Mis à jour : 6/5/2012
NB : Pour le point (c), on a utilisé le fait que le nombre $f(i-2)=f(i)+max\{0;n_i-n_{i-1}\}+max\{0;n_{i-1}-n_{i-2}\}\leq f(i)+k$ . Cette inégalité est évident si un des deux maximums vaut $0$ . De plus, si aucun des deux maximums ne vaut $0$ , alors on a $f(i+2)=f(i)+n_i-n_{i-2}$ , ce qui rend l'inégalité évidente aussi.