omb
Menu principal
Sujets d'articles
OMB 2012 Finale MAXI Question 3 Informations | BxMO 2017 | SBPM  
OMB 2012 Finale MAXI Question 3
2071 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 nombres naturels qui sont obtenues de cette manière sont dites réalisables.

(a) La liste est-elle réalisable ? Et la liste ?

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

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

(d) Quel est le plus petit nombre naturel tel que toute liste de 12 nombres naturels tous compris entre 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.



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) montre que
d) et on a une contradiction, alors ici?
e) quand ou remis
Si 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 , ca doit etre moins ou equal au
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 , on doit voir 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 places minimum, parce que ces places de 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 entre les chaises de collonne et
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 de la façon suivante :
- ;
- pour tout .
Si , alors la liste 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 en respectant la règle des intervalles décrites dans l'énoncé. En fait, tant que le nombre est positif ou nul, il représente le nombre de rangées dans lesquelles aucune personne n'est assise sur les 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 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 incluse. Si 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 . Il vient successivement , , , , , , , , , , , . 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 . Il vient successivement , , , , , , , , , , . La liste n'est donc pas réalisable (il manque rangées car ).

(b) Non car la liste n'est pas réalisable. Cela se vérifie directement avec le test donné ci-dessus.

(c) La réponse est . D'une part, on vérifie directement à l'aide du test donné ci-dessus que la liste n'est pas réalisable pour . D'autre part, on peut prouver au moyen du test que si (ce qui implique que toute liste est réalisable pour ).

(d) La réponse est . En effet, la liste est réalisable si et seulement si , 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 . Cette inégalité est évident si un des deux maximums vaut . De plus, si aucun des deux maximums ne vaut , alors on a , ce qui rend l'inégalité évidente aussi.
Membres
Prénom :

Nom :

Mot de passe : 

Conserver la connexion

Récupérer mot de passe
Recherche
Le site officiel de l'Olympiade Mathématique Belge
Contact webmasters :
Référencement