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 - 19-08-2010 12:06:43

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

cEhecs 4

Après les Dames , les pions big_smile

Au maximum , combien peut-on placer de pions sur un échiquier de façon à ce que les centres de trois quelconques d'entre eux ne forment jamais un triangle rectangle ?

http://img266.imageshack.us/img266/2998/trianglerectangle.jpg

On peut aussi généraliser en remplaçant l'échiquier par un carré ou un rectangle aux dimensions libres tongue

Amusez-vous bien smile

Vasimolo



Annonces sponsorisées :

 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 19-08-2010 14:35:12

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 374

Echcs 4

http://www.prise2tete.fr/upload/dylasse-echec4.JPG

J'ai trouvé cette config (qui donne le résultat proposé).

 #3 - 20-08-2010 10:52:44

zikmu
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 277

Echecs

Au pif 14 ? wink

x0000000
0xxxxxxx
0xxxxxxx
0xxxxxxx
0xxxxxxx
0xxxxxxx
0xxxxxxx
0xxxxxxx

 #4 - 20-08-2010 23:13:04

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

echecq 4

Bonne réponse de dylasse et zikmu avec un exemple parfait à l'appui big_smile

Mais bon , pourquoi ne peut-on pas faire mieux hmm

Vasimolo

 #5 - 21-08-2010 11:03:22

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 374

evhecs 4

Pourquoi ne peut-on pas faire mieux ?
Parce que, si on a 15 pions sur l'échiquier, il y en a au moins 1 sur une case dont la colonne possède un autre pion ET la ligne possède un autre pion, ce qui nous fait un triangle rectangle évident.

On peut le démontrer par l'absurde :
Démontration pour un échiquier de c x l, impossible d'avoir c+l-1 pions.
Supposons que les c+l-1 pions n'aient pas simultanément un pion (ou plus) sur la même colonne et un pion (ou plus) sur la même ligne.
On a 3 catégories de pions :
P0 : ceux qui sont seuls sur leur ligne et leur colonne
P1 : ceux qui ont d'autres pions sur la même ligne mais pas sur la colonne
P2 : ceux qui ont d'autres pions sur la même colonne mais pas sur le ligne

On a card(P0) + card(P1) + card(P2)=c+l-1. (rem : card(E) = nombre d'éléments de E).
Donc soit card(P1) + card(P0) > c-1 soit card(P2) + card(P0) > l-1 (démo simple par l'absurde).
A une symétrie près entre les colonnes et les lignes, on a donc au moins c pions qui sont seuls sur leur colonnes. Comme celà couvre toutes les colonnes, on ne peut avoir que c pions en tous, ce qui contredit qu'il y en a c+l-1 (létant supérieur à 2 pour les puristes !!!).

Donc c'est impossible d'avoir c+l-1 pions ne formant pas de triangle rectangle sur un échiquier de c colonnes sur l lignes.

 #6 - 21-08-2010 11:31:55

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

ecjecs 4

Je note tout d’abord que deux points sont sur une même ligne, les colonnes ne peuvent être utilisées car un triangle rectangle serait créé.

http://www.prise2tete.fr/upload/franck9525-echec4d.png


A/ Triangle rectangle plat ok (trois points alignés)
14 pions max (diag 2), 7 sur une ligne et 7 sur la derniere colonne libre
Pour un plateau contenant m x n cases, le max de pion est (m + n -2)

B/ Pas de triangle plat => 2 pions max sur un même alignement
Ne prenant en compte dans ce premier raisonnement que les alignements sur ligne et colonne,
2 pions sur une même ligne => reste libre 7 lignes, 6 colonnes
2 pions sur une autre ligne => reste libre 6 lignes, 4 colonnes
2 pions sur une autre ligne => reste libre 5 lignes, 2 colonnes
2 pions sur une colonne libre => reste libre 3 lignes, 1 colonne
2 pions sur une colonne libre => reste libre 1 ligne, 0 colonne
Max 10 pions sous réserve qu’une solution existe. Celle-ci-diag 3 semble être OK
je laisse le plaisir a quelau'un d'autre de generaliser a m x n cases.  tongue


The proof of the pudding is in the eating.

 #7 - 21-08-2010 12:07:35

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

echecq 4

Deux démonstrations de dylasse pour le cas général et franck pour l'échiquier classique 8X8 .

J'en ai une bien plus courte ( si on pouvait m'épargner les : Ah oui hmm on s'en doutait ... lollol ) en cherchant simplement à éviter les triangles rectangles dont les côtés de l'angle droit sont parallèles aux bords de l'échiquier puis ...

Vasimolo

 #8 - 23-08-2010 10:19:57

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

Echec s4

Quand tu dit "les centres de trois quelconques d'entre eux ne forment jamais un triangle rectangle", tu entends quoi par centre ? le milieu du segment formé par deux pions ? ou bien chaque pion est un sommet du triangle ?
Edit:
Bon partant du principe qu'un pion est un sommet, je trouve un maximum de 14 pions, une démonstration par analyse informatique exhaustive de tous les cas possibles étant une démonstration tout de même smile Il s'agit d'un des 4 plateaux suivants: la 1ere (ou 8ème) colonne remplie, la 1ere (ou 8ème) ligne remplie et on retire le pion à l'intersection des 2 (pas d'autre solution à 14)

 #9 - 23-08-2010 17:25:33

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Echec s4

Tout le monde a trouvé la bonne réponse souvent par épuisement des cas . Je vous laisse quand même regarder la démonstration de dylasse pour le cas général .

J'avais procédé d'une façon un peu différente .

Oublions dans un premier temps les triangles rectangles dont les côtés sont de "travers" comme dans le dessin que je vous ai proposé et cherchons le maximum de pions sans triangles rectangles dont les côtés de l'angle droit sont parallèles aux lignes de l'échiquier . Plaçons nous dans le cas de m lignes et n colonnes . Hormis le cas ou il y a une seule ligne ou une seule colonne le maximum de pions qu'on peut poser est m+n-2 ( sinon c'est m ou n ) . La position proposée par dylasse et zikmu convient avec m+n-2 pions il reste à montrer qu'on ne peut pas faire mieux . Il est clair que si m ou n est égal à 2 on ne peut pas faire mieux . Maintenant si on pouvait faire mieux on pourrait choisir un cas avec m+n minimum pour m lignes et n colonnes et m+n-1 pions . La première ligne contiendrait alors au moins 2 pions sinon en l'enlevant on trouverait un contre-exemple plus petit . Une colonne contenant un de ses pions ne pouvant pas en contenir d'autre on obtiendrait un nouveau contre-exemple plus petit donc encore impossible en supprimant cette colonne . La suppression de cette colonne ne marcherait pas bien si on tolèrait les triangles de "travers" . Si on revient maintenant au cas général , il est clair que le maximum qu'on peut atteindre avec des triangles possiblement "penchés" est inférieur ou égal au maximum précédent et comme l'exemple cité ne contient aucun triangle rectangle c'est fini .

Merci à tous pour la participation smile

Vasimolo

 

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
P2T
Echecs 20 par Vasimolo
11-11-2012 Enigmes Mathématiques
P2T
Echecs 9 par Vasimolo
15-03-2011 Enigmes Mathématiques
P2T
Echecs 22 par Vasimolo
20-08-2013 Enigmes Mathématiques
P2T
Echecs 16 par titoufred
05-10-2012 Enigmes Mathématiques
P2T
Echecs 3 (bis) par gasole
08-03-2011 Enigmes Mathématiques
P2T
Echecs 3 par Vasimolo
16-08-2010 Enigmes Mathématiques
P2T
Echecs 13 par Vasimolo
26-08-2012 Enigmes Mathématiques
P2T
Echecs 6 par Vasimolo
11-09-2010 Enigmes Mathématiques
P2T
Echecs 8 par Vasimolo
05-03-2011 Enigmes Mathématiques
P2T
Echecs 17 ( lombrics ) par Vasimolo
09-10-2012 Enigmes Mathématiques

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