Petites enigmes

• Choubnig

  Membre

  modifié 28/03/14 (04:37)

  +0 -0      

  Spoiler

  En fait, comme je viens d'écrire a mouton, je viens de me rendre compte que je peux au moins démontrer que pour n=3 et m supérieur ou égal a 9, aucune grille ne marche.
  Karmina dit dans son message que c'est évident, mais ça n'a rien d'évident pour tout a chacun, et ça demande je crois une petite explication. Je vais donc écrire la démonstration qui me semble la bonne. Celle ci étant faite non pas sur une valeur précise, mais comme une recherche de taille maximale de grille sans ligne répétitive, sous peine d'avoir par principe un rectangle et donc une grille invalide selon nos critères de recherche.
  
  On pose comme base qu'une grille qui dispose de deux lignes identiques contient par définition un ou plusieurs rectangles.
  Or, toute grille ne peut avoir qu'un nombre limité de lignes différentes puisque limité dans la taille par la valeur m, un nombre fini.
  Donc, on cherche pour un n donné, le nombre de lignes différentes maximales, qui sera donc la limite de m au delà duquel un rectangle est forcément présent.
  
  Sachant que n correspond au nombre de carré de la ligne.
  Sachant qu'un carré ne peut avoir que deux valeurs: noir ou blanc.
  
  On peut dire que chaque carré peut avoir deux valeurs, et donc, que pour N carré, on a 2 x 2 x ... 2 valeurs possibles et cela N fois, soit 2^n lignes possibles différentes.
  Donc, une grille pour laquelle m>=2^n contient forcément un rectangle.
  
  Et comme pour ma part, je ne vois pas ce qui nous permet de postuler que n>m (après tout il s'agit d'une grille de carrés, mais rien ne nous dit qu'elle doit disposer de plus de lignes que de colonnes), je dirais qu'une grille de n>=2^m donne également forcément un rectangle.
  
  Pour une grille n=3, on obtient 2^3 soit 8, et on vois donc que pour m=9 ou m>9, un rectangle existe par définition, bien sur.
  
  Et au passage, ces petites grilles de carrés noirs et blancs me font bien penser a des matrices de graphes pleines de 0 et de 1, sans que je sache trop pourquoi d'ailleurs...
• Mouton

  Visiteur

  posté 28/03/14 (18:34)

  +0 -0      

  Milvian a écrit :
  
  

  Spoiler

  La propriété "2 lignes identiques => rectangle" n'est vraie que s'il y a 3 colonnes ou plus"
  
  Si une grille de taille nxm contient forcément un rectangle, toute grille de taille m×n en contient un aussi.
  Si une grille de taille nxm contient forcément un rectangle, toute grille de taille n' × m' (n' ≥ n et m' ≥ m) contient un rectangle.
  
  Toute grille de taille 3×9 contient un rectangle (tu l'as démontré), donc toute grille de taille supérieure aussi. Idem pour toute grille de taille 9×3 (ou plus).
  
  Toute grille de taille 2×n ou n×2 peut ne pas contenir de rectangle. Les cas qu'il reste donc à chercher sont :
  3×3
  3×4
  3×5
  3×6
  3×7
  3×8
  4×5
  4×6
  4×7
  4×8
  5×5
  5×6
  5×7
  5×8
  6×6
  6×7
  6×8
  7×7
  7×8
  8×8

  
  
  --
  Mouton
• Choubnig

  Membre

  modifié 28/03/14 (19:40)

  +0 -0      

  Mouton a écrit :
  
  

  Spoiler

  La propriété "2 lignes identiques => rectangle" n'est vraie que s'il y a 3 colonnes ou plus"
  
  J'imagine donc que des configurations comme celles ci:
  
  11
  11
  
  ou
  
  11
  00
  01
  11
  10
  
  avec 1 blanc ou noir, et 0 l'autre couleur, ne sont pas des configurations valides pour un rectangle, bien que je vois pas trop pourquoi, même si je pense que ça tiens a la définition du rectangle.
  
  
• Karmina [62§o]

  Membre

  posté 28/03/14 (20:14)

  +0 -0      

  Spoiler

  S'il y a deux colonnes, tu peux prendre ça par exemple :
  
  10
  10
  
  Les deux lignes sont identiques mais il n'y a pas de rectangle. L'implication est fausse mais ça ne veut pas dire que si deux lignes sont identiques il n'y a pas de rectangle. Ca veut juste dire que cette donnée n'est pas suffisante.
• Mouton

  Visiteur

  posté 29/03/14 (00:20)

  +0 -0      

  Karmina Duxion[62§o]Old$chool a écrit :
  
  Précisément
  
  --
  Mouton
• Mouton

  Visiteur

  posté 08/04/14 (13:26)

  +0 -0      

  Le jeu de Set se joue avec 81 cartes.
  
  Chaque carte comporte 1, 2 ou 3 symboles qui sont des losanges, des rectangles ou des cercles. Ils sont rouges, bleus ou verts, et sont remplis, hachurés ou vides (il y a une carte de chaque combinaison.
  
  Un "set" est un ensemble de trois cartes telles que pour toute caractéristique (nombre, type, couleur, remplissage), les trois cartes prennent soit trois valeurs identiques, soit trois valeurs différentes.
  
  Par exemple :
  3 losanges rouges hachurés
  2 rectangles verts hachurés
  1 cercle bleu hachuré
  est un set.
  
  En revanche :
  2 losanges verts hachurés
  3 rectangles verts rempli
  1 cercle vert hachuré
  n'en est pas un (le remplissage pose problème).
  
  Si vous voulez vous entrainer, il y a un challenge où il faut trouver des sets ici.
  
  L'énigme de la semaine est de déterminer le nombre maximum de cartes qu'on peut aligner qui ne comporte pas de set.
  
  --
  Mouton
• Karmina [62§o]

  Membre

  modifié 08/04/14 (16:03)

  +0 -0      

  C'est marrant, j'avais un projet d'info au dernier trimestre qui était de coder cet exact jeu sur Androïd en version solo et multijoueur.
  
  Pour l'énigme :
  
  

  Spoiler

  Je dirais 20.
• Éric Steam

  Membre

  posté 08/04/14 (23:27)

  +0 -0      

  Mouton a écrit :
  
  > L'énigme de la semaine est de déterminer le nombre maximum de cartes qu'on peut aligner qui ne comporte pas de set.
  
  J'arrive à construire un ensemble de 16 cartes, mais je pense qu'on doit pouvoir monter plus haut.
  
  

  Spoiler

  
  Pour chacune des 4 caractéristiques des cartes, on en interdit une possibilité.
  Puis on considère l'ensemble formé par les cartes construites à partir des deux possibilités restantes, il y en a 2^4 = 16.
  
  On est certain que cet ensemble ne comporte pas de set : il est impossible d'y faire des groupes avec 3 valeurs différentes pour une même caractéristique, donc un set serait composé de 3 fois la même carte, ce qui n'est pas possible.
  
• Karmina [62§o]

  Membre

  modifié 10/04/14 (13:33)

  +0 -0      

  Indice :
  
  

  Spoiler

  Sans y aller à tatonnement, on peut voir une carte comme un élément de (Z/3Z)^4 si on veut montrer les choses mathématiquement.
• Mouton

  Visiteur

  posté 29/04/14 (14:14)

  +0 -0      

  Karmina Duxion[62§o]Old$chool a écrit :
  
  >

  Spoiler

  Je dirais 20.

  
  
  Peux-tu le prouver ? (ou au moins donner un exemple)
  
  On dispose d'une barre de fer infiniment fine d'un mètre, et de 26 fourmis ponctelles (une espèce injustement déconsidérée par les biologistes). On peut les placer comme on veut au départ (position et sens), et elles avancent d'un mètre par heure. Quand deux fourmis se rencontrent, elles font demi-tour (elles bumpent, quoi). Comment placer les fourmis pour qu'il reste des fourmis sur la barre le plus longtemps possible ?
  
  --
  Mouton