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 - 02-06-2013 09:17:11

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Remplissage dd'un carré

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

  • |
  • Répondre

#0 Pub

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

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

rzmplissage d'un carré

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

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

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,896E+3

remolissage d'un carré

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.

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

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

remplissage d'un czrré

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

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

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 568

Remplissage 'dun carré

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à.

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

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

rzmplissage d'un carré

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

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

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

remolissage d'un carré

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

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

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

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 747

remplissage s'un carré

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.

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

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Rempilssage d'un carré

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".

 

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 ?

Mots clés des moteurs de recherche

Mot clé (occurences)

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