Enigme Remplissage d'un carré @ Prise2Tete

nodgim · #1

Bonjour à tous,
Une énigme que je viens juste de lire, je la pose avant même d'y avoir réfléchi:
Vous disposez d'un carré de n cases par n cases. Démontrez que, quelles que soient les cases que vous allez colorier, vous trouverez toujours soit 1 ligne et 1 colonne, soit 2 lignes, soit 2 colonnes qui auront le même nombre de cases coloriées.
Je nous souhaite un bon amusement

nodgim · #2

Bon, je l'ai. Trop facile pour ce site...

gwen27 · #3

si aucune ligne n'a le même nombre de cases coloriées il y a donc la possibilité de colorier 0 1 2 ...n-1 n cases dans chaque ligne en excluant un seul de ces résultats.

Idem pour les colonnes.

Il y aura donc des nombres communs de cases coloriées en ligne et en colonne.

Si on ne compte pas les lignes ou les colonnes non coloriées (0 ne serait pas un nombre de cases coloriées) On peut les éliminer du problème et construire un rectangle n1 x n2 avec en ligne 1 à n1 cases coloriées et en colonne 1 à n2 cases coloriées. Cela revient au même.

Donc, pour éviter d'avoir 2 lignes ou deux colonnes ayant le même nombre de cases coloriées, il faut qu'une ligne et une colonne aient le même nombre de cases coloriées.

nodgim · #4

C'est ça Gwen, il me semble qu'on peut faire plus court comme démo.

Nombrilist · #5

Il y a 2n lignes et colonnes contre seulement n possibilités de colorier un nombre de case dans une ligne ou une colonne. Voilà.

titoufred · #6

On suppose que l'on a un carré de côté $n$ dont toutes les lignes et les colonnes ont des nombres de cases coloriées différents. Cela fait $2n$ nombres différents parmi $[0..n]$ , c'est-à-dire $n+1$ possibilités. Donc $2n \leq n+1$ et donc $n=1$ . Mais dans ce cas, on aboutit à une contradiction.

nodgim · #7

OK pour Titou et Nombrilist qui ont fait on ne peut plus court.

Question subsidiaire:
Combien de relations "égalité" au minimum existe t il ?

godisdead · #8

Pour un carré n, vous avez 2n lignes/colonnes.
Et seulement n+1 façon différentes de remplir la ligne / colonne.
Pour n>1; 2n > n+1
Donc il y aura toujours au moins 2 lignes et/ou colonnes identiques.

nodgim · #9

En fait, on ne peut à la fois se servir des n+1 possibilités offertes. En effet, si on ne met rien dans une ligne, on ne peut colorier n cases dans une colonne, ce sera au maximum n-1 cases. De même, si on colorie n cases d'une ligne, aucune colonne n'aura 0 case coloriée.
Au final, il y a toujours au minimum n relations d'égalités.

C'était un problème proposé dans le journal Le Monde et présenté sur le site Chronomath. C'est une application simple du principe dit "des tiroirs".

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 02-06-2013 09:17:11

Remplissage d'un carr

#0 Pub

#2 - 02-06-2013 09:22:20

remplissage d'un careé

#3 - 02-06-2013 09:27:49

remplisdage d'un carré

#4 - 02-06-2013 10:53:40

remplisqage d'un carré

#5 - 02-06-2013 11:01:55

Remplissgae d'un carré

#6 - 02-06-2013 11:17:33

remplissage d'un varré

#7 - 02-06-2013 12:05:36

Remlpissage d'un carré

#8 - 02-06-2013 12:47:42

Remplissage d'uun carré

#9 - 05-06-2013 18:54:59

remplissage d'un czrré

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums