Enigmo 72 : Pas de place pour le thé

Posté par jamo jamo

Bonjour,

voici un petit jeu tout simple, accessible à tout niveau. Par contre, trouver la réponse me semble plutôt difficile (et j'avoue ne pas la connaître, donc celui ou ceux qui me donneront le minimum gagneront).

Dans la grille ci-dessous, j'ai noirci des cases de telle sorte qu'il soit impossible de placer la pièce rose en forme de T sur les cases jaunes.

La question est très simple : combien faut-il noircir de cases au minimum pour réaliser cette impossibilité ?
Vous me donnerez le nombre de cases noires, ainsi que leurs positions, en image ou sous une autre forme.

Bonne recherche !

Posté par PloOf PloOf

14 minimum:

On noirci une case sur deux, puis remet jaune celles autour.

Posté par Eric1 Eric1

je propose 18

Posté par lo5707 lo5707

Bonjour,

Sans certitude, je dirais 14.



Merci pour l'énigme.

Posté par Nofutur2 Nofutur2

J'ai trouvé plusieurs solutions avec 14 cases minimum.
Aucune certitude que ce soit la meilleure ..
En voici une.

Posté par akub-bkub akub-bkub

Bonjour à tous,

Sans conviction, je répond 16 cases à colorier.

Bien à vous. A+

Posté par Daniel62 Daniel62

Bonjour Jamo,

solution par intuition: 14 cases noires

Posté par plumemeteore plumemeteore

bonsoir
je trouve quatorze cases à remplir
soit le rectangle intérieur 2*5 entouré d'une bande de deux cases de large et ses quatre coins extérieurs

Posté par Poldenys Poldenys

Enigmo 71

Posté par Francois86 Francois86

Je propose cette figure, avec 16 cases noircies.

Posté par Youpi Youpi

Bonjour Jamo.

En tâtonnant je trouve plusieurs solutions avec 14 cases noires et je n'arrive pas à faire moins.

Merci pour l'énigme.

Posté par yoyodada yoyodada

Salut jamo.
Mon minimum est 13, et voici l'image :

Posté par Labo Labo

Bonjour jamo,
plusieurs solutions à 14...
notation  horizontale A,B,C,D,E,F,G,H,I
notation verticale 1;2;3;4;5;6.
cases noircies
   C2          G2
B3   D3 E3 F3    H3
B4   D4 E4 F4    H4
   C5          G5

Posté par Corrhan Corrhan

Après avoir tésté multitude de possibilités, je pense que le minimun est 13 afin de garantir cette impossiblité.

Posté par dpi dpi


Bonjour,
on observe que laisser une croix de trois cases sur trois cases empêche de nombreuses positions de T :
Aux  symétries près ,je propose 13 cases noircies en allant de A1 à I1

E1 I1 B2 F2 C3 G3 D4 H4 A5 E5 I5 B6 F6

Posté par jonjon71 jonjon71

Bonjour !

Allez va pour 16 cases noires. Il y a certainement mieux que cela.

Merci pour le joli !

Posté par Daniel62 Daniel62

Bonjour Jamo,

juste pour dire qu'il y a deux Enigmo 71

Posté par kurtgodel kurtgodel

Bonjour.

Je pense que la réponse est 13 cases minimum.

Posté par masterfab2 masterfab2

ça sent le poisson tellement c facile


14

Posté par cycyne54 cycyne54

B/B/B/B/N/B/B/N/B/
B/N/B/N/B/B/N/B/B/
B/B/N/B/B/N/B/B/B/
B/N/B/B/N/B/B/N/B/
B/B/N/B/B/N/N/B/B/
B/B/B/N/B/B/B/B/B/

14 CASSE NOIR

Posté par programaths programaths

Voici les différentes solutions auxquelles je suis arrivé.
Au début, je pensais que la solution devait être symétrique puisque le problème en lui même offre plusieurs symétrie.
Le plateau est symétrique, le T est symétrique.

Ensuite, j'ai fait quelques tests et suis arrivé à quelques résultats dont vous pouvez en avoir un aperçu ci-dessous.
Si l'on observe bien, on peut obtenir un résultat à partir d'un autre en effectuant une symétrie locale, c'est à dire en retournant une partie du plateau.
Le cas le plus simple est le passage de la première solution à la seconde puisqu'il s'agit d'effectuer deux retournements par rapport à des axes horizontaux.
En guise d'amusement, vous pouvez essayer de trouver les autres, voire dénombrer le nombre de solution en 14 cases

Vous remarquerez qu'aucune case n'est inutilement noircie.

En résumé, il faut 14 cases minimum.

Posté par GusGusGus GusGusGus

1/3 des cases devraient suffir

Posté par Pseud Pseud

Tout d'abord, Nous avons les carrés de T, nous grisons donc les cases clés qui stoppent le plus de T. (Voir première image)

Ensuite, nous pouvons encore placer tout les T rouges et bleus de la seconde image.

Ma solution est donc la troisième image postée et comprend 12 Cases Noires.

Posté par Pseud Pseud

Evidemment, il faut prendre en compte l'image qui est l'appui de ma démarche et non le nombre 12 puisqu'il y a 14 Cases Noires ...


Donc la solution se trouve dans la 3ème image avec 14 Cases Noires Evidement

C'est pas croyable tous ces gens qui ne savent pas compter...

Posté par Youpi Youpi

Je sais pas pourquoi mais je le sentais pourtant....il y a bien une solution meilleur que 14 cases avec 13 cases noires.

Décidément ce mois ci ne me réussi pas ...

pourtant maintenant que je l'ai sous les yeux je me dis qu'elle était pas si dure à trouver.

Posté par veleda veleda

bonsoir jamo,
je n'ai pas eu beaucoup de temps pour chercher ,je ne trouve pas moins que 14avec plusieurs dispositions possibles,en voici une

000000000
0x00000x0
00xxxxx00
00xxxxx00
0x00000x0
000000000

les croix représentent les cases noircies
merci pour ce petit jeu

Posté par 1emeu 1emeu

Bonjour,

voici ma solution en image avec 13 carrés noirs.


J'ai une preuve qu'on ne peut pas faire mieux que 13 et que donc ma solution est minimale.
Je la rédigerai dès que j'aurai le temps ; elle est basée sur le fait que si on décompose le rectangle en 6 carrés 3*3, on a le résultat suivant : si un carré 3*3 ne contient qu'une case noire, alors les carrés 3*3 adjacents en contiennent au moins 3.
Supposons qu'on ait une solution avec 11 cases noires, alors au moins un des carrés 3*3 contient une seule case noire, ses carrés adjacents en ont alors au moins 3, et on trouve une contradiction.
Pour le cas 12, il faut travailler un peu plus. On peut d'abord par des arguments similaires montrer que nécessairement chaque carré 3*3 contient exactement 2 cases noires, puis énumérer des cas et trouver une contrdiction

Merci pour l'énigme

1emeu

Posté par rezoons rezoons

Bonjour ,
je propose 14 avec:

Posté par rim93 rim93


j'ai trouvé 16 cases noirs.
[table]
  [tr]
  [/tr]
[/table]

Posté par Hugalov Hugalov

Bonjour,
Voilà ma réponse :

Posté par pol316 pol316

N = case noir
J =case jaune


JJNJJJNJJ
JNJJNJJNJ
NJJNJJNJJ
JJNJJNJJN
JNJJNJJNJ
JJJNJJNJJ

Posté par 0rion 0rion

Bonsoir tout le monde !

J'ai résolu l'énigme. Bonne chance à tous !



  

Posté par jugo jugo

Bonjour,

J'ai trouvé pas mal de solutions avec 13 cases noires, mais je n'ai pas réussi à faire mieux.
Par exemple :

Posté par Nokturnus Nokturnus

Premier message!
Je trouve 13 cases noires:

Posté par jandri jandri

Le minimum de cases noires est 13.
Voici une solution:

Posté par Jau Jau

Nombre de cases à noircir : 16.

Posté par FitzChevalerie23 FitzChevalerie23

Bonjour Jamo !
J'ai trouvé un minimum de cases noircies.

Merci pour cet Enigmo !

Posté par FitzChevalerie23 FitzChevalerie23

Je voulais dire 13 cases noircie...

Posté par FitzChevalerie23 FitzChevalerie23

*noircies

Posté par link224 link224

Salut jamo.
Je propose un minimum de 14 cases noirs.

@+ et merci pour l'énigme

Posté par Wasiwasa1729 Wasiwasa1729

Merci pour cette énigme

Je pense qu'il faut noicir 13 cases au minimum pour qu'il soit impossible de placer un T.Il y a plusieurs façon de placer ces 13 cases noires. En voici une :

Posté par rogerd rogerd

Bonjour Jamo!

Vraiment dur ce mois de novembre.

Je trouve:

IL FAUT NOIRCIR AU MOINS 13 CASES

Par exemple:

Sur la première  ligne:   la 3
       deuxième  ligne:   la 2, la 5, la 8
       troisième ligne:   la 3, la 6, la 7
       quatrième ligne:   la 3, la 7
       cinquième ligne:   la 2, la 4 , la 8
       sixième   ligne:   la 5

Posté par gloubi gloubi

Bonjour,

Une proposition avec treize cases noires:



A+

Posté par Minidunf Minidunf

Voilà réussi en 15. m*****@h*****l.fr je peux vpous donnez le .paint si vous le voulez ^^

Edit jamo : pas d'adresse e-mail visible dans les messages. (voir : )

Edit jamo : et pour placer une image, voir :

Posté par totti1000 totti1000

Bonjour Jamo,

Posté par torio torio

13 cases !
A+
Torio

Posté par Abenmoussa Abenmoussa

Le nombre est 17

	X			X			X
		X			X			X
X			X			X
	X			X			X
		X			X			X
			X			X

Avec X = Les cases noires

Posté par soufni soufni

salut tout le monde .

bon malheureusement j ai pas trouve une démonstration mathématique pour l énigme mais j ai essaye de le faire avec les maths tout de même , alors j ai trouve 13 .

Posté par _Michel _Michel

Bonjour.
J'ai trouvé une solution pour 13 cases, et je crois qu'elle est unique à la symétrie près :
-X---X---
--X---X--
---X---X-
X---X---X
-X---X---
--X---X--

Preuve : j'ai fait un petit programme en C qui "brute force" le problème en testant (presque) tous les tableaux d'un nombre fixé de cases noircies. Puisqu'il ne me donne aucune réponse pour 12 cases, j'en déduit qu'il n'existe pas de solution pour moins de 13 cases.

Voila le code source, que j'ai voulu à la fois clair et rapide (il l'est : il ne met que 3h30 sur mon P4 !), bien que je ne soit doué ni pour l'un ni pour l'autre):


//Le tableau de 9*6 est représenté par un long long : les 9*6 premiers bits représentent les 9*6 cases.
//Les 112 exemplaires du T sont rangés dans des masques appliqués à chaque tableau candidat pour déterminer s'il est une solution.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Initialise le premier tableau à NbrCroix croix.
void InitialiseTableau ();

// Remplace le tableau par le tableau suivant selon un algorithme qui présente toutes les tableaux possibles.
// Initialisation avec InitiliseTableau() nécessaire.
// Retourne -1 si tous les tableaux ont été testés, 0 sinon.
// Attention : comportement indéterminé sur un tableau de 0 croix ou plus de 54.
long IncrementeTableau ();

// Informations sur le tableau
unsigned long long Tableau;
int DerniereCroix;
int TailleBloc;
int AvantDerniereCroix;
int NbrCroix;



int main()
{
    int i, j;
    unsigned long long ProtoT;
    unsigned long long T[112];
    clock_t cDebut, cFin;

    int SolutionTrouvee;

    // *** Initialisation des masques T : détermine les 112 formes de T ***
    // Note : les bits de poids fort ne sont pas utilisés.

    // Rotation de 0°
    // 111
    // 010
    // 010 => 000000111 000000010 000000010 => ...000 00011100 00000100 00000010
    ProtoT = 0x1C0402;
    for (i=0; i<4; i++) {
        for (j=0; j<7; j++) {
            T[(i*7)+j] = ProtoT<<((9*i)+j);
        }
    }

    // Rotation de 90°
    // 100
    // 111
    // 100 => 000000100 000000111 000000100 => ...000 00010000 00001110 00000100
    ProtoT = 0x100E04;
    for (i=0; i<4; i++) {
        for (j=0; j<7; j++) {
            T[(4*7)+(i*7)+j] = ProtoT<<((9*i)+j);
        }
    }

    // Rotation de 180°
    // 010
    // 010
    // 111 => 000000010 000000010 000000111 => ...000 00001000 00000100 00000111
    ProtoT = 0x080407;
    for (i=0; i<4; i++) {
        for (j=0; j<7; j++) {
            T[(2*4*7)+(i*7)+j] = ProtoT<<((9*i)+j);
        }
    }

    // Rotation de 270°
    // 001
    // 111
    // 001 => 000000001 000000111 000000001 => ...000 00000100 00001110 00000001
    ProtoT = 0x040E01;
    for (i=0; i<4; i++) {
        for (j=0; j<7; j++) {
            T[(3*4*7)+(i*7)+j] = ProtoT<<((9*i)+j);
        }
    }


    // *** Test de tous les tableaux possible avec un nombre croissant de croix ***
    SolutionTrouvee = 0;
    cDebut = clock ();
    for (NbrCroix = 12; (NbrCroix<13)&&(SolutionTrouvee==0); NbrCroix++) {
        // Teste tous les tableaux à NbrCroix croix : 54!/(NbrCroix!*(54-NbrCroix)!) tableaux

        printf ("*** Test des tableaux contenant %d croix.\n", NbrCroix);

        SolutionTrouvee = 0;
        InitialiseTableau(NbrCroix);
        do {
            long boolSolution;

//// Affichage pour le débuggage
//printf ("Test du tableau : \n");
//for (i=0; i<6; i++){
//    for (j=0; j<9; j++) {
//        if ((Tableau>>(53-((i*9)+j))&1) == 0) {
//            printf ("X");
//        } else {
//            printf ("-");
//        }
//    }
//    printf ("\n");
//}

            // Teste le tableau candidat.
            boolSolution = 1;
            for (i=0; i<112; i++) {
                if ((Tableau&T[i])==T[i]) {
                    boolSolution = 0;
                    break;
                }
            }

            if (boolSolution == 1) {
                SolutionTrouvee += 1;
                printf ("Solution trouvée !\n");
                for (i=0; i<6; i++){
                    for (j=0; j<9; j++) {
                        if ((Tableau>>(53-((i*9)+j))&1) == 0) {
                            printf ("X");
                        } else {
                            printf ("-");
                        }
                    }
                    printf ("\n");
                }
            }

        } while (IncrementeTableau () == 0);    

        printf ("\n");
    }

    cFin = clock ();
    printf ("Fin des tests.\n");
    printf ("Nombre de solutions trouvées : %d.\n", SolutionTrouvee);
    printf ("Temps = %f.\n", (float)(cFin-cDebut) / CLK_TCK);

    system ("PAUSE");
}

void InitialiseTableau ()
{
    // Coche les NbrCroix cases (bits) de poids fort du tableau
    if (NbrCroix == 0) {
        exit (-1);        // pour éviter un problème avec IncrementeTableau()
    } else if (NbrCroix == 54) {
        Tableau = 0ULL;

        DerniereCroix=0;
        AvantDerniereCroix=54;
    } else {
        Tableau = (~0ULL)>>(NbrCroix+10);

        DerniereCroix=54-NbrCroix;
        TailleBloc = 1;
        AvantDerniereCroix=DerniereCroix+1;
    }
}

long IncrementeTableau ()
{
    // Determine si la case suivante de la case contenant la dernière croix existe.
    if (DerniereCroix != 0)
    {
        // On déplace la croix d'une case.
        Tableau = (Tableau | (1ULL<<DerniereCroix)) & ~(1ULL<<(DerniereCroix-1));
        DerniereCroix -= 1;
    } else {
        int AvantDerniereCroixTmp;
        int i;

        // optimisation de 28% du temps d'execution !!!
        if (TailleBloc == NbrCroix-1) {
            if ((AvantDerniereCroix == 45) && ((Tableau>>45) == 0x01FE)) {
                return -1;}    // Plus de solution pour un tabbeau avec NbrCroix < 14
        }

        // Il faut déplacer un bloc ...

        if (AvantDerniereCroix == 54) {
            return -1;}                    // Plus de tableau

        // Decoche la case
        Tableau = Tableau | (1ULL<<AvantDerniereCroix);
        for (i=AvantDerniereCroix+1; (i<54)&&(((Tableau>>i)&1) != 0); i++) {}
        AvantDerniereCroixTmp = i;

        // Coche le bloc de TailleBloc+1 cases suivantes et décoche la fin.
        DerniereCroix = AvantDerniereCroix-TailleBloc-1;
        if (DerniereCroix==0) {
            Tableau = Tableau & ~((~0ULL)>>(63-TailleBloc));
            TailleBloc += 1;
            AvantDerniereCroix = AvantDerniereCroixTmp;
        } else {
            Tableau = Tableau & ~(((~0ULL)>>(63-TailleBloc))<<DerniereCroix);
            Tableau = Tableau | ((~0ULL)>>(64-DerniereCroix));
            TailleBloc = 1;
            AvantDerniereCroix = DerniereCroix+1;
        }

        // optimisation de 23% du temps d'execution !!!
        if ((Tableau & 0x01FF) == 0x1FF) {    // On sait que ces tableaux ne sont pas des solution pour moins de 14 croix.
            Tableau = (Tableau | (1ULL<<DerniereCroix)) & ~(1ULL<<8);
            DerniereCroix = 8;
        }
    }

    return 0;
}

Note : on ne pourrait pas définir la balise [code][/code] sur le forum pour les fous qui comme moi présentent des programmes?

Posté par kioups kioups

On va dire 17...