Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 15-11-2011 03:18:19

Azdod
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 763
Lieu: In this universe ... !!

L eRoi ... Poulet !

Dans toute paire de poulets, il y a exactement un dominant et un dominé.
Un poulet R est appelé roi si, pour tout autre poulet X, le poulet R domine le poulet X ou bien R domine un poulet Y qui lui même domine X. (Un poulet ne se domine pas lui même).

a. Prouver que dans tout poulailler qui contient un nombre fini non nul de poulets, il y a toujours un roi. A quelle condition nécessaire et suffisante celui-ci est-il unique ?
b. Est-il possible d'avoir exactement 2 rois ?
c. Pour n [latex]\ge[/latex] 1 fixé, quels sont les entiers k pour lesquels il existe un poulailler de n poules ayant exactement k rois ?
Bonne chance wink

Spoiler : Éléments de réponse



Annonces sponsorisées :

"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"
  • |
  • Répondre

#0 Pub

 #2 - 16-11-2011 17:24:37

Azdod
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 763
Lieu: In this universe ... !!

le rpi ... poulet !

Un poulet R est appelé roi si, pour tout autre poulet X, le poulet R domine le poulet X ou bien R domine un poulet Y qui lui même domine X.

il se peut que R ne domine pas X dans le 2eme cas, mais domine un Y qui domine X.

un exemple de 4 rois dans un poulailler à 5 poulets :
http://www.prise2tete.fr/upload/Azdod-roi.PNG


"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"

 #3 - 17-11-2011 12:19:29

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

le roi ... pouket !

Question 1: démonstration par récurrence.
- Pour N=2 poulets, il y a un dominant et un dominé, le dominant est roi par définition
- Supposons que pour N poulets, il y en a un qui est roi
- Rajoutons un N+1ème poulet.

On va découper l'ensemble initial de N poulets (sauf le roi) en 2 catégories: D pour ceux que le roi domine directement, et D' pour ceux que le roi ne domine pas (et donc qui dominent le roi), mais qui sont dominé par un poulet de D.
Par définition, tous N-1 les poulets sont dans D ou (exclusif) dans D'
Trois cas se présentent:

Cas 1: Le nouveau poulet est dominé par le roi => le roi reste roi

Cas 2: Le nouveau poulet domine le roi.
Cas 2.1: le nouveau poulet est dominé par un poulet de D => le roi reste roi
Cas 2.2: le nouveau poulet domine tous les poulets de l'ensemble D. Par conséquent, il "domine au second degré" tous les poulets de l'ensemble D' et il domine aussi le roi => le nouveau poulet est donc le roi.

CQFD


Question 1 bis:
Soit un ensemble E de poulets, avec un roi unique R, et un ensemble D de poulets dominés par le roi et un autre D' de poulets qui dominent le roi.
Si D' est non vide, c'est un ensemble de poulet. Il comporte donc un roi "local" sur D' noté R'.
Du coup, R' est:
- dominant au premier ou au second degré sur tous les membres de D'
- dominant sur R puisqu'il fait partie de D'
- dominant au second degré sur tous les poulets de D vu qu'il domine R
R' est donc roi aussi, ce qui est absurde, le roi étant unique par définition. D' est donc nécessairement vide.
Plus clairement, cela signifie qu'un groupe de poulets admet un unique roi si et seulement si ce roi domine directement tous les autres poulets.


Question 2:
Soit un ensemble de poulets à exactement deux rois R1 et R2, qui dominent respectivement les ensembles D1 et D2 de poulets; et qui sont dominés par les poulets des ensembles D'1 et D'2

On remarquera que l'ensemble de tous les poulets vaut au choix {R1} U D1 U D'1 ou bien {R2} U D2 U D'2
Cela signifie que tout roi local de D'1 domine D'1 par définition, R1 directement et D1 au second degré et qu'il est donc roi global. Pareil pour tout roi local de D'2.
Parmi R1 et R2, il y a un dominant. On va dire R1 domine R2.
R2 n'est donc pas membre de D'1; et R1 non plus. D'après ce qu'on a vu, soit D'1 est vide, soit il admet un poulet et donc un roi local qui sera roi global.
Si D'1 n'est pas vide, ça nous fait un troisième roi. S'il est vide, aucun roi de domine R1 qui est donc roi unique. Les deux cas sont absurdes.
Conclusion: il est impossible d'avoir 2 rois


Pour la dernière question, j'ai pas de démo, mais je dirais que si n est impair, tout k <= n différent de 2 est bon, et si n est pair tout k < n différent de 2 est bon. Peut être une récurrence pourra en venir à bout

 #4 - 17-11-2011 14:26:00

Azdod
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 763
Lieu: In this universe ... !!

Le Roi ... Pouet !

Un grand Bravo à Scarta smile


"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"

 #5 - 17-11-2011 15:36:43

TiLapiot
Expert de Prise2Tete
Enigmes résolues : 16
Messages : 851
Lieu: au terrier ;^)

lr roi ... poulet !

J'ai essayé de transposer la notion de poulet dominant / dominé / roi
en celle plus mathématique de nombre supérieur / inférieur / majorant
et transitivité aidant, ça répond à pas mal de questions. Mais ce n'est pas une démonstration big_smile

 #6 - 17-11-2011 16:19:09

Azdod
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 763
Lieu: In this universe ... !!

Le Roi .... Poulet !

ok, donne moi tes résultats smile


"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"

 #7 - 17-11-2011 16:28:24

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

le toi ... poulet !

2 petites affirmations et leur démo, pour montrer que
- si on peut faire k rois avec n poulets, on peut aussi avec plus de n poulets
- avec un nombre impair de poulets, on peut ne faire que des rois

il ne me reste plus qu'à montrer qu'on peut faire 2n rois avec 2n+1 poulets et pas avec 2n poulets


Affirmation 1:
Si on peut avoir k rois parmi n poulets, on peut aussi en avoir k parmi n+1.
Démonstration par récurrence, on ajoute 1 poulet dominé par tout le monde

Affirmation 2:
On peut avoir 2k+1 rois parmis 2k+1 poulets.
Démonstration par l'exemple: les poulets sont notés P0, P1, ..., P2k
Si i est pair, le poulet Pi domine tous les poulets Pj avec j>i et j impair ou j<i et j pair
Si i est impair, le poulet Pi domine tous les poulets Pj avec j>i et j pair ou j<i et j impair
On n'a pas de problème avec ça:
- si i<j et que le poulet Pi domine le poulet Pj, alors i et j n'ont pas la même parité et comme j>i, Pj ne domine pas Pi vu qu'il faudrait une parité différente
- si i>j et que le poulet Pi domine le poulet Pj, alors i et j ont la même parité et comme j<i, Pj ne domine pas Pi vu qu'il faudrait une parité différente
Les poulets que Pi ne domine pas directement le sont au second degré, en effet:
- si i<j et Pi ne domine pas Pj, alors ils ont la même parité et donc Pi domine Pj-1, qui lui domine Pj vu que j-1<j et que j-1 et j sont de parité différente
- Si i>j>0 et Pi ne domine pas Pj, alors ils sont de parité différente et donc Pi domine Pj-1 qui lui domine Pj
- enfin si i>0 et Pi ne domine pas P0, alors i est impair et donc il est inférieur à 2k et du coup Pi domine P2k qui lui domine P0
Pour tout i, Pi est donc roi.

 #8 - 18-11-2011 15:37:43

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Le Roi ... Poule t!

Une démo plus simple pour le fait qu'on puisse faire 2n+1 rois parmi 2n+1 poulets, mais aussi 2n rois parmi 2n+1 poulets pour n>1: par récurrence.

Pour 2n+1=5, on peut avoir 4 rois (cf le dessin d'Azdod) ou 5:
P0 domine P1 et P3, qui dominent entre autres P2 et P4
P1 domine P2 et P4, qui dominent entre autres P0 et P3
P2 domine P3 et P0, qui dominent entre autres P4 et P1
P3 domine P4 et P1, qui dominent entre autres P0 et P2
P4 domine P0 et P2, qui dominent entre autres P1 et P3


Supposons que pour 2n+1 poulets (n>1) on puisse avoir 2n (resp. 2n+1) rois
- Ajoutons un poulet P que tout le monde domine: on a toujours nos 2n (resp. 2n+1) rois
- Ajoutons un poulet P' que P domine, mais qui domine nos 2n+1 poulets initiaux: on a toujours nos 2n (resp. 2n+1) rois car P' est dominé par P qui est dominé par nos 2n (resp. 2n+1) rois, mais P est aussi roi vu qu'il domine P' qui domine tous les autres; et P' aussi vu qu'il domine tout le monde sauf P mais que tous ceux là dominent P. On a donc 2n+2 (resp. 2n+3) rois.

Conclusion générale:
- pour n=1 ou 2, on a un roi
- pour n=3, on a un roi ou trois
- pour n=2k+1>3, le nombre de rois peut prendre toutes les valeurs comprises entre 1 et 2k+1 excepté 2; et aucune autre
- pour n=2k, le nombre de rois peut prendre toutes les valeurs comprises entre 1 et 2k-1 excepté 2

La seule chose qu'il me reste à démontrer est: pour n=2k, peut-on avoir 2k rois

 #9 - 19-11-2011 17:30:52

Azdod
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 763
Lieu: In this universe ... !!

LLe Roi ... Poulet !

Merci à tous et spécialement à Scarta qui a résolu une grande partie du problème !
Éléments de réponse ajoutés au poste initial !


"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 63 pommes et que vous en prenez 23, combien en avez-vous ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete