Bonjour,

dans le démineur classique le décompte n'est pas le même ...



les cases en diagonale comptent, et au départ on ne voit même pas les nombres du tout (une case vide correspond à 0)

en tout cas je proposerais d'examiner des "constellations" autorisées de cases noires sur une grille (infinie)
en particulier il sera impossible d'avoir des zones totalement blanches (contenant des 0 qui est pair)
une ligne isolée de cases noires est impossible aussi car il y aurait des 2 à ses extrémités



etc

Bonsoir,
pour les grilles on peut noircir toutes les cases et on a des 3 dans toutes les cases.

euh .. pas d'accord



les cases marquées 4 ont bien trois voisines noircies mais avec elles mêmes ça fait 4.

les 2 x (2n+1) sont une extension évidente de l'exemple initial

 Cliquez pour afficher

toutes les cases valant 1

2 x 2n ne marche pas ainsi.

les 3 x (6n+3)

 Cliquez pour afficher

les cases non indiquées valant toutes 1

Joli mathafou, nous voilà déjà avec plein de grilles !

Après une erreur grossière, un résultat pour les grilles .

 Cliquez pour afficher

On peut répéter le motif

pour obtenir toutes les grilles .
En supprimant les colonnes de 1 aux extrémités on obtient  toutes les grilles  

Voici où j'en suis




Le cas 1 x n est résolu. En effet le bloc couvre les cas n=3k, n=3k-1 et n=3k-2.

Le cas 2 x n est résolu. Le premier bloc couvre les cas n=4k, n=4k-1 et n=4k-2. Le second couvre les cas n=2k+1.

Le cas 3 x n n'est pas encore résolu, il manque le cas 6k+4. Le premier bloc couvre les cas n=6k, n=6k-1, n=6k-2. Le second couvre les cas n= 2k+1

edit : réponse à verdurin
et même 2n+1
LittleFox ayant dit entre temps les 2 x (2n+1)

une disposition assez semblable donne les 4 x (5n+2) et 4 x (5n+4)

Pardon, c'est le cas 3 x (6k+2) que je n'ai pas encore résolu. Et non 3 x (6k+4) qui est couvert par le premier bloc.

Comme d'habitude j'ai fait un petit programme
Ça m'a fait réaliser un point clé: Tout le schéma est déterminé par la première colonne! Ainsi il devient facile de tester les différentes permières colonnes et de voir les blocs possibles.

 Cliquez pour afficher

# https://www.ilemaths.net/sujet-demineur-revisite-877247.html

from itertools import product


def solve(m):
    for start in product((True, False), repeat=m):
        grid = [start]

        valid_lengths, current_length = [], 1
        while True:
            count = [(grid[-1][i]
                      + (grid[-2][i] if current_length > 1 else 0)
                      + (grid[-1][i - 1] if i > 0 else 0)
                      + (grid[-1][i + 1] if i < m - 1 else 0))
                     for i in range(m)]

            if all(c % 2 == 1 for c in count):
                valid_lengths.append(current_length)

            next_column = tuple(c % 2 == 0 for c in count)
            if next_column == start and all(c == 0 for c in grid[-1]):
                break

            grid.append(next_column)
            current_length += 1

        show_grid(grid)
        print(current_length, valid_lengths)


def show_grid(grid):
    m, n = len(grid[0]), len(grid)
    print('\n'.join(''.join('#' if grid[j][i] else ' ' for j in range(n)) for i in range(m)))


def main():
    # solve(3)
    # solve(4)
    solve(5)


if __name__ == "__main__":
    main()

m   longueurs
1   3
2   4
3   6, 12
4   5, 10
5   24
6   9, 18
7   12, 24
8   28
9   30, 60
10  31, 62
11  48
12  63, 126

Juste pour le fun, un bloc 63x96

 Cliquez pour afficher

[img1

Oops, j'ai pas fermé mon tag

verdurin a joliment complété les grilles entamées mais j'adore le programme de LittleFox, j'ai bien fait de poser la question !!!
Sa dernière grille est magnifique, j'aurais été incapable de la sortir, je peux juste dire qu'il en existe une, tant pis pour le constructivisme...

J'ai l'impression que c'est toujours possible de remplir une grille m x n de façon valide.
Mais même si je sais générer plein de grilles, je n'ai pas le début d'une preuve générale. Et si tu dis que ta preuve est non constructiviste, je ne suis pas dans la bonne direction.

En fait, on va essayer de faire mieux :
Un nœud peut être blanc ou noir, a des relations de voisinage avec d'autres nœuds et a pour poids le nombre de nœuds noirs qu'on compte parmi lui et ses voisins.
Une coloration consiste à changer la couleur d'un ensemble de nœud
Une coloration gagnante est une coloration qui partant d'une situation où tous les nœuds sont blancs rend impair le poids de chaque nœud. Donc si on l'applique en partant d'une situation quelconque, cette coloration va changer la parité de tous les poids des nœuds présents.

Raisonnons sur le nombre de nœuds, si n=1 c'est trivial puisqu'il suffit de le colorier en noir.
Par récurrence, supposons qu'on arrive à trouver une coloration gagnante pour chacun des sous-ensemble de n nœuds parmi les n+1 nœuds sans s'occuper du nœud retiré.

- si une de ces colorations donne un poids impair au nœud retiré, c'est gagné
- sinon
cas n+1 pair :
En partant de tous les nœuds blancs, on va appliquer successivement toutes les n+1 colorations identifiées en retirant un unique nœud à chaque fois. A chaque coloration, tous les nœuds vont voir la parité de leur poids changer sauf le nœud retiré (en effet si c'était le cas, il aurait obtenu un poids impair avec l'une des colorations et on aurait déjà gagné précédemment).
Chaque nœud va voir son poids changer de parité n fois or n est impair donc c'est gagné.

cas n+1 impair :
On commence par montrer qu'il existe au moins un nœud qu'on appellera N avec un nombre pair de voisins.
En effet, si tous les nœuds ont un nombre impair de voisin, comme il y a un nombre impair de nœud, en sommant le nombre de voisins de chaque nœud, on aurait une somme impair. Mais au final, on a compté 2 fois chaque relation de voisinage, cette somme se doit d'être pair, ce n'est pas possible.

En partant de tous les nœuds blancs, on va appliquer successivement les colorations identifiées en retirant un unique nœud parmi N et ses voisins (dont le nombre est pair).
Les nœuds en dehors de N et ses voisins ont donc subit un nombre impair de coloration, ils ont donc maintenant un poids impair
N et ses voisins ont subit un nombre pair de coloration (pour la même raison que précédemment, le nœud retiré ne peut pas changer de parité sinon on aurait gagné dès le début avec la coloration correspondante), ils ont donc tous un poids pair. Il ne reste plus qu'à changer notre nœud N de couleur ce qui fera changer la parité de son poids mais aussi celui de ses voisins.

En théorie je pourrai construire n'importe quelle grille avec ce raisonnement mais en pratique... je ne me vois pas le faire

C'est un raisonnement constructif mais plutôt lent

Si je ne me trompe pas, O((mn)!) contre un O(n2^m) pour mon algo. Et je trouvais mon algo déjà très lent

Mais il est plus générique (on peut l'appliquer à n'importe quel graphe) et grâce à la récursivité on démontre pour tous les graphes.
Joli

À LittleFox et Vassillia : bravo.