Petites enigmes > Réponse Sciences sujet

Satori9960 a écrit :

> En les posant en diagonale tu va convertir tout le carré en question

Absolument pas.
Tu a n-1 virus, pour des colonnes et lignes de n cases.
Il te manque fatalement un trou sur ta diagonale qui ne pourra pas être contaminé, car tu n'aura aucun virus de base sur cette ligne colonne d'où contaminer.*
A moins que le carré dont tu parle soit le carré n-1, la oui. Mais comme j'espère le montrer, ce ne sera absolument pas la disposition mathématiquement optimale.

Bien évidemment, c'est le n-1 qui pose problème.
Avec les mathématiques:
On a n-1 cases infectés dans la situation de départ. ces cases sont des carrés de 4 côtés. On a donc 4(n-1) côtés de cases infectés au départ.
Pour qu'une case soit infecté, elle doit être en contact avec deux côtés infectés.
Toute infection ne peut donc se produire que si une case a 2 côtés infectés, et toute case nouvellement infecté consommera ces deux côtés (côté consommé: côté ne pouvant infecter de nouvelles cases) et créera au maximum 2 côtés nouvellement infectés.
Mais pas obligatoirement. Les côtés extérieurs des cases infectés seront obligatoirement des côtés qui seront consommés sans aucun pouvoir d'infection (ils ne touchent qu'une case puisqu'ils forment le périmètre, et cette case doit être infecté a la base pour infecter le côté).
par conséquent, le nombre de côtés de cases infectés ne peut que rester stable ou diminuer.
Le nombre de côtés de cases infectés, pour remplir tout le carré, doit pouvoir couvrir tout les côtés de cases périphériques (celles consommés sans pouvoir d'infection).
Hors, ce nombre est connu; Pour un carré de nxn, il est de 4n.
Hors, le nombre de côtés de cases infectés de départ est, au mieux, 4(n-1).

Trois conclusions:
Ce nombre de virus, n-1, est insuffisant.
Le nombre maximum de carrés possiblement infectés est de n²-4 (puisque le potentiel d'infection maximal de départ est de 4n-4, et le potentiel nécessaire pour une infection totale est de 4n, toutes les cases peuvent être infectés, sauf 4).

PS: Pardonc, ma seconde conclusion est fausse je pense. En fonction de la taille du carré.

J'aurais tendance a croire que la disposition optimale nécessite qu'aucune case infecté de départ ne touche le bord du cadre. Mais je me demande comment contaminer alors, les cases du bord du cadre.
En fait, la contamination du bord du cadre au départ est indispensable et en même temps, voué a l'échec.

Ce qui fait qu'on a une démonstration bien plus évidente et plus rapide a effectuer, peut être:
Ou en tout cas, plus logique:
Pour contaminer tout le carré, il faut que toute ligne et colonne soit entièrement contaminé.
Pour contaminer une ligne ou colonne entière: Il faut soit que deux lignes ou colonnes entières soient contaminés (et tiennent la colonne ou ligne en question en étau, donc, adjacentes), soit qu'une case soit contaminé sur la ligne ou la colonne a la base (car la contamination ne peut être diagonale, donc, pour contaminer une ligne ou colonne, il faut un contaminant original).
On élimine la première solution, qui consiste a dire: Pour contaminer une colonne ou une ligne, il faut déjà en contaminer 2. Si on peut en contaminer 2, on peut a fortiori en contaminer entièrement une.

Or:
En estimant que chaque virus peut contaminer une ligne et une colonne, et qu'on a n lignes et n colonnes, il faut n virus. Nous avons n-1 virus. Il est donc impossible de s'assurer d'avoir un virus sur chaque ligne et colonne.
Et donc, impossible de contaminer toute ligne et colonne du carré.
Et donc, impossible de recouvrir le carré.

Pour le circuit:

On considère N nombre de points aléatoirement répartis sur un cercle. On appelle X le trajet du point A au point A+1 et X+1 le trajet de A+1 à A+2.
On a donc A, A+1,... A+N la liste des points répartis.
Et X, X+1,... X+N la liste des distances entre ces points.
Le total des distances entre ces points est égal a 360° (tour complet du cercle).

On considère des valeurs Y, Y+1,... Y+N ou le total de ces valeurs est de 360°.
On réparti aléatoirement ces valeurs aux points de A à A+N.

On effectue ensuite un calcul, en soustrayant a chaque Y la valeur Y-1, soit la valeur du point précédant le leur.
On associe chaque résultat, R obtenu, au point correspondant sur le cercle, soit le point auquel est associé Y.
On note Ar le résultat associé au point A, et Ar+1 le résultat suivant. On note Ar+X un résultat parmi l'ensemble, et (Ar+X)+1 le résultat du point suivant.
Si Ar+X est positif, cela signifie que le point A est atteignable a l'aide du carburant du point A-1. Ar est le gain de carburant supplémentaire effectué durant le trajet (indépendamment du carburant nécessaire au trajet)
Si Ar+X est négatif, cela signifie que le point A n'est pas atteignable a l'aide du seul carburant du point A-1. Ar est la perte de carburant supplémentaire effectué durant le trajet (indépendamment du carburant nécessaire au trajet)

Pour chaque Ar+X > 0, on remplace Ar+X par la valeur (Ar+X)+((Ar+X)+1). On remplace (Ar+X)+1 par la valeur 0.
On recommence l'opération a chaque valeur Ar+X supérieure a 0, jusqu'à ce qu'il ne reste que 2 valeurs Ar+X différentes de 0.
La valeur positive sera placé au point de départ optimal.


Bon, j'avoue, c'est beaucoup plus fouilli ici, parce que c'est toujours un truc dans lequel je me perds, les questions d'ensemble et de calculs d'ensemble.
En gros, on pondère chaque quantité de carburant de chaque point en fonction de la distance séparant le point pondéré du point suivant. On obtient un circuit avec des gains et des pertes de carburant net (dont le total fait 0). On élimine les valeurs négatives en les soustrayant au premières valeurs positives trouvés dans le sens inverse du parcours du circuit. On applique ces nouvelles valeurs pondérés au point détenant la valeur positive a laquelle on a soustrait. Le résultat peut être négatif.
On continue a éliminer les valeurs négatives en les associant aux valeurs positives trouvés aux points rencontrés en remontant le circuit, jusqu'à n'avoir que 2 valeurs, une positive et une négative (car le total de toutes les valeurs pondérés est de 0, il n'y a ni surplus, ni déficit de carburant au total sur la piste). La valeur positive donne l'emplacement de départ optimal.

C'est vrai, là, c'est la résolution a la Brutus. Il y a probablement un truc mathématique. Mais bon, je vais pas donner deux solutions dans le même post, c'est sale.
Faut bien que d'autres s'amusent.

D'ailleurs

Fausse énigme:

Fausse, parce qu'elle est idiote et simpliste. Mais on sais jamais, vous pourriez tomber dans l'énorme chausse-trappe que je vais tendre.
Je joue au go contre un ordinateur. Sur un Goban de NxN, nous avons chacun un nombre X(N²) pierres (X<N).
L'ordinateur va jouer comme ceci:
- Il cherchera toujours d'abord a prendre mes pierres. Il attaquera toujours par mon côté droit (sa gauche) et fera le tour de mes pierres dans un sens horaire (gauche, haut, droite, bas selon mon point de vue). Il abandonnera s'il vois que mes pierres ne sont plus prenables (règle des deux yeux).
- S'il ne peut pas effectuer la première directive, il mettra une pierre dans le coin supérieur gauche, puis, une pierre a côté, puis, une pierre a côté, et ainsi de suite, tant qu'il ne peut pas remplir le premier ordre.
- Il ne passera jamais son tour.
Je joue comme bon me semble.
Combien de pierres me faut il pour le vaincre ? Avec quel score ?

Comme je l'ai dit, ce n'est pas une vraie énigme, et pas une vraie énigme de maths. La solution est bien évidemment, évidente, mais bon, ça fera au moins faire 10 secondes de triturage. Je suis très mauvais pour me souvenir des énigmes, bien plus pour me souvenir des solutions.
(bon, je précise: Au Go, si vous vous demandez, vous posez des pierres sur des intersections de lignes. Vous perdez un groupe de pierres reliés entre elles si l'ennemi occupe toutes les libertés de votre groupe. Une liberté, c'est une intersection de ligne adjacente sur le côté ou la hauteur. Quand avec un groupe de pierre, vous formez deux "yeux", c'est a dire, des pierres en cercle autour d'une liberté laissé non prise, le groupe est imprenable, car on ne peut poser qu'une pierre par tour).