Bonjour tout le monde,
on dispose d'une grille de 7 lignes et 7 colonnes, régulièrement espacées.
L'objectif est de colorier certains des 49 points de cette grille de telle sorte que ces points coloriés ne forment pas de carrés dont les côtés sont horizontaux ou verticaux.
Par exemple, sur la petite grille, j'ai colorié 19 points en rouge, mais on y trouve 3 carrés (si je n'en ai pas oubliés ...). Donc un tel choix de points n'est pas acceptable.
Question : Quel nombre de points peut-on colorier au maximum ? Et lesquels ?
Pour la réponse, je veux tout d'abord le nombre de points à colorier, et aussi leurs emplacements (en image ou en utilisant le repérage des lignes et colonnes).
J'ai mis 2 étoiles pour la facilité de compréhension de l'énigme, tout le monde peut y participer, mais trouve la solution mérite peut-être 3 étoiles ...
Bonne recherche !
J'ai pas trouvé plus de 19...
1: point colorié
0: point non colorié
1 0 0 1 0 0 1
0 1 1 0 0 0 1
0 0 1 1 0 1 0
1 1 0 0 1 0 0
0 1 0 0 1 1 0
0 0 0 1 1 0 0
1 0 1 0 0 0 0
Bonne chance pour la correction
Le 20 semble être hypothétiquement possible, mais...
Oups, j'ai oublié l'image....
Tu m'en voudras pas j'espère ! (Enfin, encore faudrait-il que ce soit la bonne réponse !)
Bonjour Jamo,
L'énoncé est simple, d'accord, mais comme toutes les énigmes où il y a recherche de maximum ou minimum, on n'est jamais bien sûr d'avoir trouvé la solution demandée (sauf si le nombres de cas possibles ne dépasse pas le milliard, auquel cas on peut traiter par ordinateur, ou si il existe une méthode de résolution rigoureuse).
Ici j'ai trouvé une grille avec 26 points coloriés, et 23 non coloriés. Et trouver une grille avec 27 points coloriées, c'est choisir 22 points parmi 49 que l'on ne colorie pas, et 22 parmi 49 = 49699896548176. je ne peux donc même pas vérifier qu'il n'existe pas de grille à 27 points rouge.
Quand à une résolution rigoureuse, je ne vois pas du tout comment m'y prendre !
Donc à moins de chercher à tâtons toute l'après midi, me voici démuni. Je propose donc la première grille que j'ai trouvé, sans aucune conviction bien sûr. Alea Jacta Est.
Merci pour l'énigme
Salut jamo,
ça c'est de l'énigme!! Tu cherches une bonne partie de la journée, mais t'es toujours pas sûr de ta réponse au moment de poster...
Allez, je propose quand même, je n'ai pas trouvé mieux que 32...
Voici ma proposition :
Bonsoir, je pense qu'on peut colorier au max 29 points en rouge pour qu'il n'y ait pas de carrés.
merci pour l'énigme
Bon, à la mi aout, le poisson c'est pour maigrir.
Donc solution 2, à tête reposée du week-end, avec un raisonnement logique, et symetrique
Ma grille
1 1 1 0 0 0 0
1 0 0 1 1 0 0
1 0 0 0 0 1 1
0 1 0 1 0 1 0
0 1 0 0 1 0 1
0 0 1 1 0 0 1
0 0 1 0 1 1 0
Comment l'obtient t-on?
Objectif, 3 coloriages par ligne, en cherchant à optimiser le nombre binaire composé de 7 bits de la lignes
donc première ligne
1 1 1 0 0 0 0
ensuite, on ne peut pas commencer la deuxième ligne par 1 1, sinon, un carré, ni 1 0 1 sinon un rectangle
donc
1 0 0 1 1 0 0
Et je viens de me rendre compte que j'ai pas bien lu l'énoncé
J'ai raisonné que sur l'absence de rectangles...
Donc 21 pour les rectangles, et donc malheureusement un peu plus pour l'absence de carré...
Bref, tout tout faux sur cette enigme
Bonjour Jamo,
J'ai trouvé un maximum de 31 points.
A1 C1 E1 F1 G1
A2 B2 D2 G2
B3 C3 D3 F3 G3
A4 B4 F4
B5 E5 F5 G5
A6 B6 C6 E6 G6
A7 C7 D7 E7 F7
C'était une énigme passionnante.
Merci
Bonjour
Je trouve 30 points
par exemple
B1 C1 D1 F1 G1
A2 B2 D2 E2 F2
B3 C3 E3 G3
A4 B4 E4 F4 G4
A5 C5 F5
A6 B6 C6 D6
A7 D7 E7 G7
Bonjour,
cette enigme n'est pas facile !
Je ne sais pas si j'ai bien réussi à le traduire mathématiquement
je dirais 31 .
Bonjour,
Je trouve qu'on peut colorier au maximum points sans former de carrés.
Pour m'aider à placer les points j'ai programmé cette feuille Maple disponible sur mon site :
En fait elle permet simplement de vérifier qu'il n'y a effectivement aucun carré, mais pas que le résultat est optimal malheureusement. J'ai abandonné l'idée du bruteforce, parce qu'il y a façons de répartir 33 points dans la grille, et même en tenant compte des symétries et rotations ça reste énorme.
Je suis curieux de savoir si un membre a démontré que son résultat est optimal, et mieux encore s'il existe une formule clause pour un carré . Pour je trouve , mais cette suite n'est visiblement pas connue du site officiel . J'ai essayé aussi de me ramener à un graphe, ou utiliser le principe des tiroirs mais en vain, bref j'attends la clôture de l'énigme avec impatience
Bonjour !
Je trouve 30 points à colorier.
Ci-dessous, une figure illustrant cette solution.
Cordialement,
r2.
Ma tentative à 27 était assez pitoyable...
Voici une solution à 31 qui ne doit plus être très loin de l'optimum...
Bonjour,
a moins de tester toutes les possibilités, je ne vois pas comment être sur d'avoir trouvé la combinaison maximale.
Je tente quand même ma chance :
j'ai placé 26 points
1 A D E F
2 C D F G
3 B D
4 A B C E F G
5 D F
6 A B D E
7 B C D G
Merci pour l'énigme
J'en trouve 28 : (représentés par des A sur mon shéma)
A A A A A A A
0 A 0 A 0 A 0
0 A A 0 0 A A
0 0 A A A 0 0
0 A A 0 0 A A
0 A 0 A 0 A 0
A A A A 0 0 0
Bonjour, je trouve un maximum de 27:
1 0 0 1 1 1 1
1 1 0 0 1 0 1
0 1 1 0 0 1 1
0 0 1 1 1 1 0
1 1 0 1 0 1 1
0 1 0 0 1 1 0
0 0 0 0 0 1 1
(les 1 sont les points coloriés, les 0 sont les points non coloriés)
Bonjour Jamo
J'ai trouvé que l'on pouvait colorier 32 points sans former de carré dans la grille.
Voici la grille :
En m'aidant de l'informatique je ne suis parvenu qu'à des solutions à points au maximum comme cette configuration :
Bonjour jamo,
Maximum 32 points
1: A B C D E F
2: A _ C _ E _ G
3: A B _ _ E F G
4: _ B C _ _ _ G
5: A _ C D _ F G
6: A B _ D _ _ G
7: _ B C D E _ G
Clôture de l'énigme
Bon, arrêtons là le massacre !
J'avais bien imaginé que cette énigme serait difficile, et de plus je ne connaissais pas à l'avance le résultat !
Plusieurs m'ont proposé une solution à 32 point coloriés ... alors on va supposer que c'est le maximum !?
De plus, j'espère ne pas m'être trompé en acceptant ces solutions à 32, car je n'ai pas "d'outil" pour le faire, j'ai du contrôlé "à l'oeil". Donc si certains veulent vérifier, qu'ils nous signalent les erreurs.
Reydown >> pas de bol, ta solution à 32 n'est pas bonne, il y a un carré avec B2 F2 F6 B6.
Il y a pas mal de temps, j'avais proposé une JFF sur le même thème : JFF : Surtout pas de rectangles !! :*:
Et, pour être honnête, j'avais prévu de proposer une autre variante, qui consistait à interdire tous les carrés, même ceux qui sont "penchés". Voici ci-dessous l'image qui était déjà prête.
Mais vu la difficulté, j'ai préféré ne pas la proposer.
Cependant, si certains veulent s'y pencher, faites vous plaisir !
J'ai hésiter a participer avec 27 points. J'ai bien fait de m'abstenir car comme l'a dit jamo c'est un vrai massacre.
Oui massacre...
Moi qui esperais un faux-pas de Nofutur2... aïe aïe aïe le mois d'août...
En tout cas merci jamo pour ce genres d'énigmes !!! :)
Oh oui, quel massacre et je ne me suis pas mouillé non plus car j'avais trouvé 31 points sur le papier. Pas trouvé de moulinette pour le faire à ma place et après plusieurs heures, je n'étais vraiment pas sûr de mon résultat. Cela m'a évité un de plus ! Je sais, ce n'est pas glorieux !!
Bonjour,
Bravo à Jamo pour cette énigme et à Nofutur2 pour sa rapidité.
Quelques explications seraient nécessaires. Aux survivants du vol 214 pour ...
Merci.
Mince moi qui pensais y trouver une démonstration à me mettre sous la dent ^^
Je n'ai pas eu le temps de continuer les énigmes entre le déménagement et les cours... et j'attends un pour le batiment
Bonne continuation
Salut infophile
Peut-être pas pour le bâtiment, on sait jamais !!(enfin si...)
Si je peux te rassurer, tu attendais aussi un poisson pour celle-ci...
Bonjour à tous.
Après un mois d'août calamiteux, je suis content de m"en être bien tiré cette fois-ci.
Des comme ça, on en redemande ! Bravo, jamo !
Au fait, infophile, pour n= 4, je trouve une solution à 12 points:
X X X -
X - X X
X X - X
- X X X
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :