pied gauche

 

Sciences

Forum > Sciences > Petites enigmes

1 | ... | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21

Guest

19/03/15 (09:46)

nombre messages : 1

Visiteur

Satori[*n]9960 a écrit :

> De façon intuitive

Tout l'objectif est d'avoir une démonstration formelle. La solution tient en un seul mot (ie si vous l'avez, la démonstration est triviale).
Guest

27/03/15 (14:11)

nombre messages : 1

Visiteur

Un circuit de course est circulaire, assez long, donc il y a des postes de ravitaillement placés n'importe où sur le circuit. Chaque poste ne peut délivrer qu'une certaine quantité de carburant à votre passage (pourtant, votre réservoir n'est pas limité), pas forcément suffisante pour rallier le point suivant. En revanche, la somme des capacités de tous les postes donne exactement la bonne quantité pour faire un tour complet.

Montrer qu'on peut choisir un poste de ravitaillement à partir duquel on peut faire un tour complet.

Milvian

02/04/15 (07:37)

avatar

Citoyen

Confédération Libre

Domicile : Greffe

Satori[*n]9960 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).

[ce message a été édité par Milvian le 02/04 à 09:27]
Guest

03/04/15 (03:33)

nombre messages : 1

Visiteur

Milvian a écrit :

> 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).

C'est une borne supérieure, pas un maximum.

> Pour contaminer tout le carré, il faut que toute ligne et colonne soit entièrement contaminé.

Ce raisonnement m'a l'air faux. Tu utilises à la fois la nécessité de contaminer toutes les lignes et le fait que ce n'est pas rentable d'en contaminer 2 pour en contaminer une. Bah pourtant, ca fait que tu peux en contaminer n-1 pour en contaminer n, donc c'est utile. D'ailleurs, avec une disposition en rectangle, il est possible d'infecter un rectangle de 2n+1 par n avec 2n virus.

> Pour le circuit:

Rien compris, et pourtant une solution tient en trois lignes, mais j'ai pu mal m'exprimer. Les positions des stations ne sont pas aléatoires mais imposées, ainsi que la quantité d'essence dans chaque station.

> Je joue au go contre un ordinateur. Sur un Goban de NxN, nous avons chacun un nombre X(N²)
> pierres (X<N)

C'est peut-être parce que je ne connais pas bien les règles du go, mais je ne comprends pas :
> - 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).

Que veut dire "attaquer", quel est le "côté droit" (s'il y a plusieurs blocs connexes ?), il fera le tour dans quel sens ? Par exemple, si on suit le carre n-2 x n-2 centre, l'ordinateur va se contenter de longer ? et du coup on gagne parce qu'il se prive tout seul de liberte pendant qu'on construit un oeil, et il suffit d'une pierre pour le fermer ensuite ?

Milvian

03/04/15 (04:10)

avatar

Citoyen

Confédération Libre

Domicile : Greffe

Guest a écrit :

A minima, le raisonnement mathématique est juste.
La quantité de côtés de cases infectés ne pouvant que stagner ou diminuer, il faut que cette quantité soit suffisante dès le départ pour contaminer l'ensemble des côtés qui forme le périmètre de la grille.
Le périmètre de la grille est comptable comme étant n, le nombre de carré sur un bord de la grille, par 4, le nombre de bords de la grille.
Donc, il faut 4n côtés.
Hors, nous en avons a la base 4(n-1). Donc, un chiffre inférieur. Qui ne pourra encore une fois, que stagner ou diminuer.
Donc, c'est impossible.

Le raisonnement est logique: On cherche comment contaminer toute la grille.
Pour cela, il faut au moins ce demander quels sont les prérequis a la contamination d'une ligne ou d'une colonne.
Hors, pour contaminer une ligne ou une colonne, il faut soit qu'un contaminant soit présent sur la ligne ou la colonne a la base (aucune contamination par les diagonales n'est possible), soit qu'il y ai déjà 2 lignes contaminés entièrement qui la cernent.
Mais dire que la solution pour contaminer une ligne est d'en contaminer deux, reviens a dire que pour avoir A, il faut avoir 2A.
Nous, on cherche a obtenir les prérequis logiques a la contamination d'au moins une ligne.
Dire que le prérequis est d'en contaminer deux.. Très bien.
Quel est alors le prérequis pour en contaminer deux, qui soient, par définition, espacés d'au moins une ligne ou colonne (puisque le but est de contaminer la colonne ou ligne au départ de la réflexion toujours...)
Le prérequis est d'avoir deux contaminant, au minimum, 1 sur chaque ligne ou colonne, ou d'avoir 4 lignes ou colonnes (adjacentes, bien sur, a celles visés) qui soient contaminés a la base sur tout leurs carrés.

et on reboucle en augmentant les prérequis nécessaire jusqu’à avoir des chiffres supérieurs a n (dans les deux cas). Je ne compte même pas le paradoxe qui consiste a dire que pour que la ligne/colonne A soit contaminé, il faudrait contaminer les B et C qui sont ces colonnes/lignes adjacentes, et que pour contaminer B et C, il faut contaminer A qui leur est adjacente... Bref, ce prérequis n'est pas valide dans la démarche: Quels sont les prérequis a la contamination de la grille ?

En fait, sur ces deux prérequis, l'un est irréalisable car nous sommes plafonné a n-1 virus de base, alors qu'il en faut n, l'autre est impossible tout simplement parce qu'il reboucle sur lui même.
Donc, les prérequis sont impossibles. La disposition impossible.

Je sais que tu attends une propriété mathématique en deux mots qui explique toute la solution: Mais les solutions que je proposent, sont toutes deux valides.
Au passage, on ne peut pas considérer ma démonstration comme le fait que pour contaminer n lignes/colonnes, il faut contaminer n-1 lignes/colonnes. Car dans la grille, toutes les lignes et colonnes n'ont pas deux lignes ou colonnes adjacentes (les colonnes et lignes qui sont en position 1 et en position n, soient les bords de la grille).
Ces colonnes là ne répondent pas au prérequis de base de cette proposition: Elle n'ont pas assez de lignes ou colonnes adjacentes pour que ma proposition s'applique.


Pour le circuit:
Oui, très bien, les positions des stations sont imposés, la quantité d'essence aussi...
Mais est ce qu'on les a, ces positions ? Non.
Alors, comme on a pas de disposition précise, et qu'il n'y a aucune règle de disposition particulière de posé (n'importe ou n'est pas une règle mathématique, ou alors si, mais c'est l'aléatoire), on doit raisonner en envisageant toutes les possibilités pour intégrer la bonne par défaut. Pour ça, il faut donc prouver que peu importe le placement des points et les dispositions du carburant, la solution est possible.

Pour mon énigme: je pense que je donne la réponse en disant cela mais... Toutes les questions que tu te pose sont inutiles a sa résolution optimale. Promis.
Comme je l'ai dit, c'est pas une vraie énigme mathématique.
En fait, tu n'est pas très loin dans ta supposition de la résolution optimale. Mais comme je l'ai demandé, la résolution optimale est capable de vous dire combien de pierres sont nécessaire pour le vaincre.
Pour le score, on compte simplement qu'une pierre prise a l'ennemi vaux un point.
Mais en effet, je suis d'accord sur un point: Il vaux mieux connaitre les règles du go pour bien comprendre l'enigme. Quoi que mon explication des règles est pour ainsi dire, presque exhaustive, tant les règles de ce jeu sont simples.

[ce message a été édité par Milvian le 03/04 à 04:19]

Elune Jumper

04/04/15 (17:48)

avatar

Membre

Pour le circuit une simple récurrence marche bien:

n = 1 : trivial, une station qui a assez d'essence pour faire le tour

car n+1, en considérant n qui fonctionne.
On a somme des distances = somme des réserves de carburant. Il existe donc au moins 1 réserve de carburant supérieur ou égal à une distance. En partant de ce point, on peut donc arriver à un point suivant.
Partant de ce point, on peut donc considérer que la réserve de carburant est la somme des deux, et la distance à parcourir aussi. On revient alors à un cas n.

Milvian

04/04/15 (22:18)

avatar

Citoyen

Confédération Libre

Domicile : Greffe

Elune Morningwood[§o]Jumper a écrit :

Sauf que s'il existe un nombre suffisant de points de ravitaillement, on a pas 1, mais peut être 2, 3, voir 4 stations qui ont une réserve supérieure a la quantité nécessaire pour le trajet jusqu’à la station suivante.
Et on a donc aussi le cas contraire. Des stations avec moins de carburant que nécessaire.
La question est donc: Quel point de ravitaillement assure un excédent suffisant pour qu'il soit possible d'atteindre le point d'excédent suivant et ce jusqu’à faire le tour.

L'intuition voudrais qu'on dise: Le point qui en a le plus grand excédent. Sauf que les stations suivantes peuvent parfaitement avoir un déficit encore plus grand.

Au passage, si on part du principe qu'il y a un excédent quelque part, il va falloir considérer qu'il y a un déficit ailleurs. C'est mathématique.

[ce message a été édité par Milvian le 04/04 à 22:21]

Elune Jumper

04/04/15 (23:16)

avatar

Membre

La récurrence s'intéresse juste à réduire le nombre de station pour revenir à un cas connu dont on sait que la solution marche.

On va prendre le cas suivant avec tous les points avec 10 d'écart.

A-B-C-D-E-F-A

On a un total de carburant de 60.
A a 11
B a 10
C a 9
D a 9
E a 11
F a 10

On fait le cas n = 6
De A, j'arrive à B. On réduit alors le cas à n = 5. Avec le cas suivant:
A-C-D-E-F-A
Toutes les distances valent 10 sauf A-C qui vaut 20
Et la station A a maintenant le carburant de A et B soit 21

On est dans le cas n = 5 (dont on a déjà déterminé que c'était bon - principe de la récurrence)
En continuant, de A on arrive a C.
On a donc plus que A-D-E-F-A.
Avec d(AD) = 30, Carburant(A) = 11 + 10 + 9 = 30

Sur ce nouveau cas, de A on arrive a D. On réduit donc
A-E-F-A
Avec d(AE) = 40, Carburant(A) = 11 + 10 + 9 + 9 = 39

Sur ce nouveau cas, de E on arrive à F. On réduit donc:
A-E-A
Avec d(EA) = 20, Carburant(E) = 11 + 10 = 21

On est donc au cas a 2 points, de E on peut arriver à A et comme la somme de l'essence est suffisante pour faire le tour et qu'on est aller à toutes les stations, on a fait le tour en partant de E.

A partir du moment ou tu supprimes une station en la considérant absorbée par la station précédente qui parvient à l'atteindre, tu passes au cas n-1 que dont tu as déjà démontré que c'était réalisable car n=1 et n=2 sont trivial pour démarrer la récurrence.

[ce message a été édité par Elune Jumper le 04/04 à 23:18]
Guest

05/04/15 (19:57)

nombre messages : 1

Visiteur

Elune Morningwood[§o]Jumper a écrit :

> La récurrence s'intéresse juste à réduire le nombre de station pour revenir à un cas connu
> dont on sait que la solution marche.

Et le raisonnement est juste.

Le mien pour cette énigme était un peu différent : tu pars de n'importe quel point, tu comptes en algébrique (positif ou négatif) ton carburant pendant un tour. La quantité d'essence atteint un minimum en une station. Il suffit de partir de cette station.

Milvian

10/04/15 (16:32)

avatar

Citoyen

Confédération Libre

Domicile : Greffe

Bon, alors déjà, ça, non.
Juste non.
Rien que si on prends l'exemple d'Elune, la quantité d'essence sur son exemple atteint son minimum en E. Hors, si tu part du point E, tu n'arrivera même pas au point suivant.

Quand a la démonstration d'Elune... Elle a prouvé qu'on pouvait faire un tour complet.
Pas qu'on pouvait choisir un poste de ravitaillement à partir duquel on peut faire un tour complet.

Bien évidemment, dans son exemple, on sait instinctivement quel point choisir au départ.
Mais ça reste un exemple. Et d'ailleurs, un exemple ou les stations sont uniformément réparties le long du circuit. Alors que l'énoncé du problème ne nous indique absolument pas que cette répartition est uniforme.

En réalité, il faut partir du point suivant au point ou ton carburant atteint le minimum algébrique, parce que c'est uniquement en faisant d'abord tout le reste du circuit que tu peut espérer faire le tour complet au moment de passer ce point.
Mais ça revient a faire ce que j'ai fait: pondérer les quantités de carburant des stations par les distances qu'elles doivent couvrir, afin de faire apparaitre les déficits et bénéfices de carburant de chaque station, puis, absorber les déficits des stations en les répercutant sur les bénéfices des stations précédentes jusqu’à n'avoir plus qu'une station bénéficiaire.

je pourrais re-copier coller mon message précédent, mais je pense qu'on pourrait faire ça longtemps.

[ce message a été édité par Milvian le 10/04 à 16:34]

Forum > Sciences > Petites enigmes

1 | ... | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21