Mathématiques discrètes, algorithmique

Question du jeudi #20 : Dans un damier $n \times n$, les cases peuvent être allumées ou éteintes. Ensuite, le damier évolue selon la règle suivante : les cases ne s'éteignent jamais, et une case s'allume à une étape donnée si au moins deux de des voisines sont allumées. (On appelle voisines deux cases qui ont un côté en commun. Ainsi, une case a, suivant sa position sur le damier, deux, trois ou quatre voisines).

Quel est le nombre de cases minimal qu'il faut allumer au début du processus pour aboutir à un damier complètement allumé ?

Question du jeudi #13 : $n + m$ boules se déplacent sur une droite. À l'instant $t=0$, les $n$ boules de gauche ont une vitesse $\vec v$ dirigée vers la droite, alors que les $m$ boules de droite ont une vitesse $- \vec v$ (dirigée vers la gauche, donc). On néglige tous les frottements et on suppose que les chocs sont élastiques, de telle sorte que la vitesse d'une boule à un instant donné est toujours $\pm \vec v$. Combien de collisions vont-elles se produire ?

Question du jeudi #8 : Sur le réseau social Friendface, chacun des $n$ membres peut être ami avec n'importe quel autre membre (mais pas avec lui-même). La relation est symétrique : si Moss est ami avec Roy, Roy est ami avec Moss. Montrer que deux des membres de Friendface ont exactement le même nombre d'amis.

Question du jeudi #7 : On place des pions sur un damier de taille $n \times m$. À quelle condition sur $n$ et $m$ est-il possible de les réarranger de telle sorte que chaque pion atterrisse sur une case adjacente de celle qu'il occupait précédemment ?

Question du jeudi #6 : Six nombres entiers sont inscrits dans les secteurs d'un disque. À chaque étape, vous pouvez ajouter 1 aux nombres inscrits dans deux secteurs adjacents. Si l'on part de la situation où les nombres sont 1, 0, 1, 0, 0, 0, pouvez-vous parvenir à une situation où les six nombres sont égaux ?

La géométrie d'incidence est ce qui reste de la géométrie quand on oublie les distances, les angles... et qu'on ne se concentre plus que sur les questions d'appartenance d'un point à une droite, de parallélisme, etc. Discipline à cheval entre la géométrie axiomatique et la combinatoire, elle comporte encore aujourd'hui des problèmes ouverts fondamentaux. Cet article présente ce qui est peut-être l'objet le plus basique en géométrie d'incidence : les plans (affines) finis, sur lesquels beaucoup reste encore à apprendre.