[ENIGME] 200 de QI uniquement SVP

Le 14 janvier 2023 à 02:40:35 :

Le 14 janvier 2023 à 02:39:04 :
Comme ça sans rien poser, je dirais qu'il ne faut pas que les deux cases soient adjacentes.

Mais je n'ai pas vérifié l'hypothèse.
Et un autre khey à l'air de dire que la condition des cases adjacentes est une condition pour pouvoir poser les dominos 2*1...

Après il y a peut être une question de bordure de l'échéquier, car celà créé peut être une contrainte ?

Il suffit* qu'elles soient adjacentes, ça c'est relativement clair.
Maintenant toute la question est de prouver qu'il le faut.

il est pas nécessaire qu'elles soient adjacentes :

Le 14 janvier 2023 à 04:44:48 :

Le 14 janvier 2023 à 02:40:35 :

Le 14 janvier 2023 à 02:39:04 :
Comme ça sans rien poser, je dirais qu'il ne faut pas que les deux cases soient adjacentes.

Mais je n'ai pas vérifié l'hypothèse.
Et un autre khey à l'air de dire que la condition des cases adjacentes est une condition pour pouvoir poser les dominos 2*1...

Après il y a peut être une question de bordure de l'échéquier, car celà créé peut être une contrainte ?

Il suffit* qu'elles soient adjacentes, ça c'est relativement clair.
Maintenant toute la question est de prouver qu'il le faut.

il est pas nécessaire qu'elles soient adjacentes :

Effectivement, donc ce n'est pas la condition.
(J'avais déjà énoncé un autre contre-exemple à la page précédente, d'ailleurs ).
Mais de toutes façons je vais vous aider un peu vu que vous galérez depuis 5 pages...

La condition nécessaire/suffisante c'est bel et bien "deux cases de couleurs différentes", mais il s'agirait de le prouver maintenant ! C'est évident* que c'est nécessaire, c'est moins évident que c'est suffisant.

(en fait il n'est pas spécialement évident que c'est nécessaire, mais disons que c'est un argument classique de coloration que des kheys ont déjà énoncé sur le topax. Cela dit, pour quelqu'un qui n'aurait jamais vu cet argument avant, ça ne doit pas être immédiat d'y penser.)

Bah je vois comment expliciter la construction du pavage en fonction des cases, mais c'est long et pas très intéressant

Y'a pas moyen de le faire en considérant juste la croix sur l'échiquier formée par les deux cases retirées par hasard ?

ça nous laisse des régions de taille 2k par m recouvrables simplement et une autre peut être plus simple à étudier non ?

Le 14 janvier 2023 à 04:50:10 :
Bah je vois comment expliciter la construction du pavage en fonction des cases, mais c'est long et pas très intéressant

Y'a pas moyen de le faire en considérant juste la croix sur l'échiquier formée par les deux cases retirées par hasard ?

ça nous laisse des régions de taille 2k par m recouvrables simplement et une autre peut être plus simple à étudier non ?

Je ne sais pas khey, je connais deux solutions, je ne prétends pas connaître toutes les méthodes de résolution
Peut-être que ton truc marche, à toi de creuser.

Oh et puis merde tu sais quoi

On se donne un damier carré de taille 2n

On retire deux cases de couleur différentes,
en posant N = (p,q) , B= (p',q') avec p+q=1 mod 2 et p'+q'=0 mod 2 (du à leur couleur)

On considère la zone rectangulaire délimitée par N et B, sans perte de généralité on suppose que N est en bas à gauche de B (On peut retourner et pivoter le plateau c'est la même chose à recouvrir)

le rectangle est de taille s=(p'-p) par k=(q'-q)

si p' est impair , p impair , alors s est pair , k est impair
si p' est impair, p pair , alors s est impair, k est pair
si p' est pair , p impair, alors s est impair, k est pair
si p' est impair, p impair; alors s est pair, k est impair
-> tout ça pour dire que le rectangle est de taille pair:impair
Il se recouvre très simplement , on remplit les bords des côtés impairs ( on peut car on a retiré une case, nous laissant une ligne de longueur paire) et ensuite c'est juste un rectangle de côtés impairs x pair à remplir, ce qui est trivial à paver.

Maintenant on doit s'occuper de la région extérieure au rectangle, là c'est assez simple aussi, on étent les côtés pairs du rectangle jusqu'au bord, ce qui fait qu'on a pavé de (p,0) à (p',2n) (ou les coordonnées inverses osef) et après il reste juste à étendre les côtés de ce rectangle de longueur 2n jusqu'au bords, on a bien pavé tout le damier.

Ah ok bah écoute ta solution est la même que celle que j'avais utilisé. Tu parlais de croix tout à l'heure donc j'avais pas pigé, mais oui moi aussi j'avais bien considéré le rectangle dont les deux cases retirées forment deux coins opposés.

La preuve plus courte part du constat suivant : il existe un circuit hamiltonien dans l'échiquier.
Autrement dit, si on part du coin en haut à gauche de l'échiquier, il est possible de faire un parcours qui passe par toutes les cases de l'échiquier exactement une fois et qui termine à nouveau en haut à gauche. (Il n'est pas franchement difficilement d'en trouver un, d'ailleurs)
En retirant deux cases, on coupe ce circuit en deux chemins disjoints. Si ces chemins sont tous deux de longueur paire, alors ils seront tous deux couvrables par des dominos. Or lorsque les deux cases retirées sont de couleurs distinctes, les deux chemins sont bien de longueur paire. Donc voilà, ça prouve la suffisance.

A priori ça s'adapte à n quelconque.

Celle ci n'est pas ma solution donc je la connais un peu moins. Et clairement telle que je l'ai écrite là je pense qu'elle est incomplète, faudrait que je la détaille un peu plus mais je ferais ça demain Disons que c'est un brouillon de preuve.

en fait ça marche pas dans le cas ou t'as une surface isolée de forme

BNB_
_BNB

, mais si ça se trouve le cas là est impossible

Apres y avoir reflechi un moment voila la solution que je propose.
Je précise que je n'ai pas regardé les reponses sur le topic.

Deja il faut forcement que les 2 cases soient de couleur differentes. En effet, un "domino" est une paire de cases adjacentes. Donc forcement chaque domino aura un côté noir et un côté blanc. Si on enleve 2 cases de meme couleur, on ne peux plus compléter la grille.

Voila pour la condition necessaire, est elle suffisante ?
Elle l'est, voila pourquoi :
On compte le nombre de cases vides sur chaque ligne. Si le nombre est pair, on compléte avec des domino horizontaux et on passe a la suivante.
Si le nombre est impair (ou si une case bloquante empeche de placer un domino horizontal) on met un domino vertical et on reporte -1 au total de la ligne d'en dessous.
On finit forcement avec un nombre pair sur la derniere ligne.

Voila, par A+B, et j'ai pas 200 de QI (mais nettement plus que 100 certainement)

Le 14 janvier 2023 à 07:30:08 :
Et si quelqu'un desaprouve ma theorie, merci de me prouver mon erreur en me proposant un echiquier "impossible" a completer avec 2 cases de couleurs differentes bloquées

Tu pourrais avoir raison pour de mauvaises raisons.
Si en jouant à pile ou face je dis "la pièce va tomber sur pile parce qu'elle est truquée", même si la pièce tombe bel et bien sur pile ça ne prouve pas que la pièce était truquée.
Dans ton cas, c'est précisément ce qui se passe : la condition que tu donnes est correcte, mais ta preuve est fausse. Donc je ne peux pas donner de contre-exemple, mais ta réponse est quand même erronée/incomplète.

Quel est le souci avec ta preuve ?
Il est ici :

On compte le nombre de cases vides sur chaque ligne. Si le nombre est pair, on compléte avec des domino horizontaux et on passe a la suivante.

Imaginons que l'une des deux cases retirées soit celle ligne 1, colonne 2 et celle ligne 1, colonne7.
Il y a un nombre pair de cases vide ligne 1, pourtant tu ne peux pas la remplir avec des dominos horizontaux.

Le 14 janvier 2023 à 13:07:21 :
ChatGPT ?

Il a lamentablement échoué

Le 14 janvier 2023 à 07:27:49 :
Apres y avoir reflechi un moment voila la solution que je propose.
Je précise que je n'ai pas regardé les reponses sur le topic.

Deja il faut forcement que les 2 cases soient de couleur differentes. En effet, un "domino" est une paire de cases adjacentes. Donc forcement chaque domino aura un côté noir et un côté blanc. Si on enleve 2 cases de meme couleur, on ne peux plus compléter la grille.

Voila pour la condition necessaire, est elle suffisante ?
Elle l'est, voila pourquoi :
On compte le nombre de cases vides sur chaque ligne. Si le nombre est pair, on compléte avec des domino horizontaux et on passe a la suivante.
Si le nombre est impair (ou si une case bloquante empeche de placer un domino horizontal) on met un domino vertical et on reporte -1 au total de la ligne d'en dessous.
On finit forcement avec un nombre pair sur la derniere ligne.

Voila, par A+B, et j'ai pas 200 de QI (mais nettement plus que 100 certainement)

La construction du pavage est pas explicite

Le 14 janvier 2023 à 13:02:03 :

Le 14 janvier 2023 à 07:30:08 :
Et si quelqu'un desaprouve ma theorie, merci de me prouver mon erreur en me proposant un echiquier "impossible" a completer avec 2 cases de couleurs differentes bloquées

Tu pourrais avoir raison pour de mauvaises raisons.
Si en jouant à pile ou face je dis "la pièce va tomber sur pile parce qu'elle est truquée", même si la pièce tombe bel et bien sur pile ça ne prouve pas que la pièce était truquée.
Dans ton cas, c'est précisément ce qui se passe : la condition que tu donnes est correcte, mais ta preuve est fausse. Donc je ne peux pas donner de contre-exemple, mais ta réponse est quand même erronée/incomplète.

Quel est le souci avec ta preuve ?
Il est ici :

On compte le nombre de cases vides sur chaque ligne. Si le nombre est pair, on compléte avec des domino horizontaux et on passe a la suivante.

Imaginons que l'une des deux cases retirées soit celle ligne 1, colonne 2 et celle ligne 1, colonne7.
Il y a un nombre pair de cases vide ligne 1, pourtant tu ne peux pas la remplir avec des dominos horizontaux.

Faut lire jusqu'au bout, je parle de ce cas aussi.

Si le nombre est impair (ou si une case bloquante empeche de placer un domino horizontal)