Onawa a écrit :

C'est plus les problématiques de Zénon qui m'inquiètent

Onawa a écrit :

> Erf. Je viens de voir qu'on ne peut pas vraiment additionner des réels, c'est un "ensemble
> infini non dénombrable".

On peut additionner tous les nombres positifs qu'on veut. Par contre ça peut faire l'infini. Il s'agit simplement de prendre la borne supérieure des sommes finies.

sum_{a in A} x_a = sup {sum_{a0 in A0} x_a0 , A0 parcourt les parties finies de A}

Par contre, on a le résultat suivant : si la somme est finie, alors il n'y a qu'une quantité dénombrable de x_a qui soit non nulle.

Ca se montre ainsi (en résumé) : on prend A_n = {a in A tq a > 1/n} ; si la somme totale est finie, alors A_n est fini (pour tout n). On réuni tous les A_n, ça donne A_infini = {a in A tq a > 0}, qui est alors dénombrable en tant que réunion dénombrable d'ensembles dénombrables (et même finis).


Bref, tu peux additionner autant de nombres positifs que tu veux, par contre étudier les sommes finies est en gros identique à étudier les sommes finies d'une quantité dénombrable de nombres positifs (... ce qui revient en gros à étudier les séries convergentes à termes positifs).


Ceci étant, je comprends quand même pas ta question initiale : est-ce qu'il s'agit d'avoir tous les chèques d'une valeur de chacun des réels entre 0 et 1? ou juste un infini dénombrable de chèques, de valeurs décidées par l'interlocuteur ?

On part d'une grille de 3×3 (genre un pavé numérique), toutes les cases sont initialement blanches sauf la case en haut à gauche qui est noire (le 7, quoi).

À chaque tour, on peut choisir une ligne, une colonne ou une diagonale et on inverse la couleur de toutes les cases dessus.

Est-il possible d'atteindre une situation où seul le 8 est noir ? Où seul le 9 est noir ?

Uncurieux a écrit :

> On part d'une grille de 3×3 (genre un pavé numérique), toutes les cases sont initialement blanches
> sauf la case en haut à gauche qui est noire (le 7, quoi).
>
> À chaque tour, on peut choisir une ligne, une colonne ou une diagonale et on inverse la couleur
> de toutes les cases dessus.
>
> Est-il possible d'atteindre une situation où seul le 8 est noir ? Où seul le 9 est noir ?

Premièrement, chaque opération est son propre symétrique (de manière triviale)
Deuxièmement, les opérations sont commutatives (Si je change la première colonne puis la première ligne, c'est égal à si je change la première ligne puis la première colonne). Ca pourra être prouvé en utilisant le modèle mathématique utilisé plus tard.

Par conséquent on ne "peut pas" effectuer la même opération deux fois (ce serait équivalent à ne pas l'effectuer du tout), même si on la sépare par d'autres opérations. Il est évident que la répéter 3 fois sera équivalent à ne la faire qu'une fois, la répéter 4 fois à ne pas la faire etc...
Il y a 8 opérations (3 colonnes, 3 lignes et 2 diagonales), il y a par conséquent au maximum 2^8 états qu'on peut obtenir à partir de l'état initial. (au maximum, parce que potentiellement des états peuvent se répéter)

Le plateau a 2^9 états.
Il est donc impossible d'obtenir tous les états du plateau à partir de n'importe quel état de base.

Mais est-ce que l'état initial permet d'obtenir l'un des deux états finaux que l'on souhaite?

Il serait trivial d'implémenter un programme qui effectue les 256 opérations possibles et d'épuiser les possibilités. Mais on est pas là pour ça.


Utilisons un modèle mathématique.
On peut modéliser le plateau par une matrice 3x3 où chaque case vaut 0 si elle est blanche et 1 si elle est noire.
Chacune des 8 opérations peut être modélisée par une autre matrice qu'on ajoute à la première. Il conviendra d'appliquer un modulo 2 pour ramener le résultat de l'addition à un résultat binaire.
Notez que ce modèle mathématique nous fournit immédiatement la commutativité des opérations (par commutativité de l'addition). Ainsi que l'associativité.

La matrice que l'on ajoute à la matrice initiale peut être exprimée de la sorte :
C1 + L1 + D1 C2 + L1 C3 + L1 + D2
C1 + L2, C2 + L2 + D2 + D1 C3 + L2
C1 + L3 + D2 C2 + L3, C3+ L3 + D1

Il suffit donc de résoudre un système d'équations :
C1 + L1 + D1 = 1 (Rappelons que la 7° case doit changer d'état)
C2 + L1 = 1 (et la 8° aussi)
C3 + L1 + D2 = 0
C1 + L2 = 0
C2 + L2 + D2 + D1 = 0
C3 + L2 = 0
C1 + L3 + D2 = 0
C2 + L3 = 0
C3 + L3 + D1 = 0

Pour simplifier l'écriture j'omets l'égalité à modulo 2, mais elle est bien présente partout.
A + B congru à 0 modulo 2 est équivalent A est congru à B modulo 2 (trivialement). (*)

Notre système devient donc:
C1 + L1 + D1 = 1
C2 + L1 = 1
C3 + L1 + D2 = 0
C1 = L2
C2 + L2 + D2 + D1 = 0
C3 = L2
C1 + L3 + D2 = 0
C2 = L3
C3 + L3 + D1 = 0

en remplaçant tous les C par des L:
C1 = L2
C2 = L3
C3 = L2

L2 + L1 + D1 = 1
L3 + L1 = 1
L2 + L1 + D2 = 0
L3 + L2 + D2 + D1 = 0
L2 + L3 + D2 = 0
L2 + L3 + D1 = 0

En ajoutant la ligne 4 et la ligne 6, on obtient:
D2 = 0

L2 + L1 + D1 = 1
L3 + L1 = 1
L2 + L1 = 0
L2 + L3 = 0
L2 + L3 + D1 = 0

En ajoutant 1 et 3, on obtient:
D1 = 1

L3 + L1 = 1
L2 + L1 = 0
L2 + L3 = 0
L2 + L3 + 1 = 0

La ligne 3 et la ligne 4 provoquent une contradiction (1=0).

Par conséquent il est impossible à partir de l'état initial d'obtenir uniquement la 8° case noircie.

La même méthode s'applique pour la 9° case. (Mais je n'ai pas calculé le résultat).

Note: On ne m'a jamais accusé de subtilité pour trouver des solutions.

[code]
C1 + L1 + D1 C2 + L1 C3 + L1 + D2
C1 + L2, C2 + L2 + D2 + D1 C3 + L2
C1 + L3 + D2 C2 + L3 C3+ L3 + D1
[/code]

La matrice initiale.
Désolé j'avais oublié la suppression des espaces

Lem a écrit :

> Le plateau a 2^9 états.
> Il est donc impossible d'obtenir tous les états du plateau à partir de n'importe quel état
> de base.

Tiens, c'est rigolo ça !

> Il serait trivial d'implémenter un programme qui effectue les 256 opérations possibles et d'épuiser
> les possibilités. Mais on est pas là pour ça.

C'est ce que j'avais fait, moi

> Note: On ne m'a jamais accusé de subtilité pour trouver des solutions

L'argument subtil, c'est de trouver un invariant (et en fait, il y a un invariant pour la première question est un autre pour la deuxième qui donnent le résultat pour chaque en une phrase).

Sans faire de maths. Parce qu'il est tard !

Non, et non. Intuitivement : Parce qu'il n'y a pas 1 millions de façons de rendre le 7 noir en blanc. Il y en a 2, la ligne et la colonne, et si je change la ligne, je n'ai aucun moyen de ne retourner que 8 ou que le 9, ça implique d'inverser la colonne correspondante, et donc devoir inverser 5/2, ce qui implique d'inverser les 2 lignes pour les changer de couleur et ainsi de suite.

Le minimum de flips qu'on puisse faire c'est 3, càd une ligne ou une colonne. Et si tu permutes une colonne dans le meilleur des cas, tu passe de 3 à 4. Tu n'as aucune permutation qui descende en dessous de 3 changement. Chaque permutation unique ne fait qu'ajouter au nombre de changements. Tu ne peux faire que 3 permutations maximales, aussi, de façon intuitive, avant de répéter une position qui est déjà possible avec 2 permutations.
Donc on dispose de L/L+L/L+L+L/L+C/L+C+C et le reste tu le retrouves en faisant une rotation à 90°, donc ce sont les même permutations.

Et donc on peut faire 3/6/9/4/5 Changer plus ou moins de valeurs que ça est impossible. Et pas des positions au hasard non plus. Tu peux pas flip 3 si c'est pas sur la même ligne, ou 4 si c'est sur 3 lignes/colonnes différentes. On le voit avec les permutations possibles, très rapidement, ce qui est faisable ou non.

Maintenant pour le prouver mathématiquement gl&hf, comme disait mon prof de math à la fac "C'est trivial" avant de se barrer de la salle de td.

___

The seagull / wonder if she is sad / left alone without being touched / by the blue of the sky / or the blue of the sea.

Satori9960 a écrit :



Il y a aussi la diagonale.
Sans les diagonales ça paraît assez évident en effet que c'est pas possible.

S'il y en a que ça amuse, le site Advent of code publie un problème d'informatique par jour jusqu'au 25 décembre. Les problèmes peuvent être faits n'importe quand (ils sont publiés à 6h du matin en France, mais aucune obligation de les faire si rapidement). Ça nécessite d'avoir un compte (pour avoir les fichiers d'input et soumettre vos réponses). Généralement les premiers jours nécessitent surtout une connaissance relative du langage (ouvrir un fichier, le lire ligne par ligne, utiliser 2-3 variables et des gestions de chaines de caractère), tandis que plus tard l'algorithmique devient prépondérante (l'an dernier, un jour particulièrement difficile nécessitait une exploration exhaustive d'un graphe d'états un peu touffu).

Notez que la réussite aux problèmes de l'AOC est tout à fait valorisable sur un CV, et également une bonne occasion d'apprendre un nouveau langage (même si je recommanderais plutôt de le faire avec votre langage de prédilection la première année).