forked from Open-CT/openct-tasks
140 lines
11 KiB
HTML
140 lines
11 KiB
HTML
<!doctype html>
|
|
<html>
|
|
<head>
|
|
<meta charset="utf-8">
|
|
<title>2016-FR-05</title>
|
|
<link class="module" rel="stylesheet" href="../../../_common/modules/pemFioi/taskStyles-0.1.css" id="http://www.france-ioi.org/modules/pemFioi/taskStyles-0.1.css">
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/ext/jquery/1.7/jquery.min.js" id="http://code.jquery.com/jquery-1.7.1.min.js"></script>
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/ext/jquery-ui/jquery.ui.touch-punch.min.js" id="jquery.ui.touch-punch.min.js"></script>
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/ext/raphael/2.2.1/raphael.min.js" id="http://cdnjs.cloudflare.com/ajax/libs/raphael/2.2.1/raphael.min.js"></script>
|
|
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/ext/json/json2.min.js" id="https://github.com/douglascrockford/JSON-js"></script>
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/pemFioi/beav-1.0.js" id="http://www.france-ioi.org/modules/pemFioi/beav-1.0.js"></script>
|
|
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/pemFioi/beaver-task-2.0.js" id="http://www.france-ioi.org/modules/pemFioi/beaver-task-2.0.js"></script>
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/pemFioi/simulation-2.0.js" id="http://www.france-ioi.org/modules/pemFioi/simulation-2.0.js"></script>
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/pemFioi/raphaelFactory-1.0.js" id="http://www.france-ioi.org/modules/pemFioi/raphaelFactory-1.0.js"></script>
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/pemFioi/delayFactory-1.0.js" id="http://www.france-ioi.org/modules/pemFioi/delayFactory-1.0.js"></script>
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/pemFioi/simulationFactory-1.0.js" id="http://www.france-ioi.org/modules/pemFioi/simulationFactory-1.0.js"></script>
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/pemFioi/grid-1.0.js" id="http://www.france-ioi.org/modules/pemFioi/grid-1.0.js"></script>
|
|
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/pemFioi/graph-1.0.js" id="http://www.france-ioi.org/modules/pemFioi/graph-1.0.js"></script>
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/pemFioi/visual-graph-1.0.js" id="http://www.france-ioi.org/modules/pemFioi/visual-graph-1.0.js"></script>
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/pemFioi/graph-mouse-1.0.js" id="http://www.france-ioi.org/modules/pemFioi/graph-mouse-1.0.js"></script>
|
|
|
|
<script class="remove" type="text/javascript" src="../../../_common/modules/integrationAPI.01/installationAPI.01/pemFioi/installation.js" id="http://www.france-ioi.org/modules/integrationAPI.01/installationAPI.01/pemFioi/installation.js"></script>
|
|
<script class="remove" type="text/javascript" src="../../../_common/modules/ext/jschannel/jschannel.js"></script>
|
|
<script class="proxy module" type="text/javascript" src="../../../_common/modules/integrationAPI.01/official/platform-pr.js" id="http://www.france-ioi.org/modules/integrationAPI.01/official/platform-pr.js"></script>
|
|
<script class="stdButtonsAndMessages module" type="text/javascript" src="../../../_common/modules/integrationAPI.01/installationAPI.01/pemFioi/buttonsAndMessages.js" id="http://www.france-ioi.org/modules/integrationAPI.01/installationAPI.01/pemFioi/buttonsAndMessages.js"></script>
|
|
<script class="remove" type="text/javascript" src="../../../_common/modules/integrationAPI.01/official/miniPlatform.js" id="http://www.france-ioi.org/modules/integrationAPI.01/official/miniPlatform.js"></script>
|
|
<script>
|
|
var stringsLanguage = 'fr';
|
|
</script>
|
|
<script class="remove" type="text/javascript">
|
|
var json = {
|
|
"id": "http://castor-informatique.fr/tasks/2016/2016-FR-05-red-and-blue/",
|
|
"language": "fr",
|
|
"version": "fr.01",
|
|
"authors": "Arthur Charguéraud, Mathias Hiron, Nir Lavee, France-ioi",
|
|
"translators": [],
|
|
"license": "CC BY-SA 3.0",
|
|
"taskPathPrefix": "",
|
|
"modulesPathPrefix": "",
|
|
"browserSupport": [],
|
|
"fullFeedback": true,
|
|
"acceptedAnswers": [],
|
|
"usesRandomSeed": false
|
|
};
|
|
</script>
|
|
<script type="text/javascript">
|
|
var taskStrings = {
|
|
tooFew: "Il vous reste un ou plusieurs cercles à marquer en bleu.",
|
|
tooManyEasy: "Vous avez marqué en bleu des cercles qui ne permettent pas de rejoindre le cercle rouge.",
|
|
tooMany: "Vous avez marqué en bleu des cercles qui ne permettent pas de rejoindre tous les cercles rouges.",
|
|
wrong: "Certains cercles ne sont pas coloriés correctement.",
|
|
close: "Vous y êtes presque ! Moins de 3 cercles sont mal coloriés.",
|
|
cannotSelect: "Vous ne pouvez pas sélectionner les cercles rouges.",
|
|
success: "Bravo, vous avez réussi !"
|
|
};
|
|
</script>
|
|
<script type="text/javascript" src="task.js"></script>
|
|
<style>
|
|
#anim_container {
|
|
text-align: center;
|
|
}
|
|
#anim {
|
|
display: inline-block;
|
|
}
|
|
#feedback {
|
|
height: 1em;
|
|
margin-top: 0.3em;
|
|
margin-bottom: 0.3em;
|
|
text-align: center;
|
|
font-weight: bold;
|
|
color: #CC8844;
|
|
}
|
|
#control, #control table {
|
|
text-align: center;
|
|
margin: 20px auto;
|
|
}
|
|
#control table td {
|
|
width: 120px;
|
|
}
|
|
</style>
|
|
</head>
|
|
<body>
|
|
<div id="task">
|
|
<h1>Points de départ</h1>
|
|
<div id="tabsContainer"></div>
|
|
<div id="taskContent">
|
|
<p id="difficultyWarning" class="hard"></p>
|
|
<p>Depuis quels cercles peut-on aller <span class="easy" style="font-weight:bold">au cercle rouge</span> <span class="medium hard" style="font-weight:bold">à tous les cercles rouges</span> en suivant les flèches ? Cliquez dessus pour les marquer de bleu.</p>
|
|
|
|
<p class="hard">Vous pouvez <strong>cliquer sur les flèches pour les colorier</strong> afin de mieux visualiser les chemins.</p>
|
|
|
|
<div id="anim_container">
|
|
<div id="anim"></div>
|
|
<div id="feedback"></div>
|
|
</div>
|
|
<img src="icon.png" style="display:none">
|
|
</div>
|
|
</div><!-- task -->
|
|
<div id="solution">
|
|
|
|
<h2>Solution</h2>
|
|
|
|
<div class="easy">
|
|
<p>Une manière naïve de résoudre le sujet est de se demander, pour chaque cercle, s'il existe un chemin permettant d'aller au cercle rouge.</p>
|
|
<p>Une manière plus astucieuse de résoudre le sujet consiste à partir du cercle rouge, et à remonter les flèches à l'envers, en coloriant en bleu tous les cercles que l'on peut atteindre ainsi.</p>
|
|
<p><img src="sol_easy.png"></p>
|
|
</div>
|
|
<div class="medium">
|
|
<p>Une manière naïve de résoudre le sujet est de se demander, pour chaque cercle, s'il existe un chemin permettant d'aller à chacun des deux cercles rouges.</p>
|
|
<p>Une manière plus astucieuse de résoudre le sujet consiste à d'abord repérer que, pour pouvoir rejoindre les deux cercles rouges, il faut forcément passer par le cercle central (le cercle bleu du milieu). Ensuite, il suffit de remonter les flèches à l'envers en partant de ce cercle bleu central, en coloriant en bleu tous les cercles que l'on peut atteindre ainsi.</p>
|
|
<p><img src="sol_medium.png"></p>
|
|
</div>
|
|
<div class="hard">
|
|
|
|
<p>On peut simplifier le problème en étudiant la structure générale de la figure. Si l'on enlève les cercles du milieu qui ne servent à rien, et si l'on "compresse" les groupes de 4 noeuds situés sur chacun des 4 bords, on se ramène à un petit problème sur lequel il est relativement aisé d'identifier les cercles qui permettent d'accéder aux 4 noeuds rouges.</p>
|
|
<p><img src="sol_hard_a.png"></p>
|
|
<p>Les chemins noirs de la figure simplifiée ci-dessus correspondent aux chemins coloriés en verts sur la figure d'origine ci-dessous :</p>
|
|
<p><img src="sol_hard_y.png"></p>
|
|
|
|
<p>On peut alors revenir au problème de départ, et se demander quels sont les cercles qu'il reste à colorier en bleu. On peut faire l'observation suivante : si une flèche part d'un cercle gris et pour rejoindre un cercle bleu, alors on peut colorier le cercle gris en bleu. En effet, de ce cercle gris on peut aller au cercle bleu en utilisant cette flèche, puis ensuite du cercle bleu on peut aller à tous les cercles rouges (puisque c'est la propriété des cercles bleus).</p>
|
|
<p>Du coup, on va répéter l'opération suivante : pour chaque cercle gris, regarder s'il y a une flèche vers un cercle bleu. Si oui, on colorie le cercle gris en bleu (et on peut aussi colorier la flèche correspondante en vert). Sinon, on cherche un autre cercle gris. On répète le processus jusqu'à ce qu'on ne puisse plus rien colorier en bleu. On a alors terminé.</p>
|
|
<p><img src="sol_hard_2.png"></p>
|
|
<!---<p>Comment peut-on être certain d'avoir terminé (sans appuyer sur le bouton "essayer") ? On peut remarquer que si d'un cercle on peut rejoindre les 4 cercles rouges, alors en particulier on peut rejoindre le cercle rouge en haut à gauche, et donc on peut rejoindre le cercle bleu en haut à gauche. Du coup, on sait que depuis tout cercle bleu, il existe un chemin vers le cercle bleu en haut à gauche. Or, s'il existe un tel chemin, alors forcément avec la méthode décrite ci-dessous, on a du colorier en bleu tous les cercles de ce chemin. En conclusion : avec la méthode que l'on a appliqué, tous les cercles qui permettent de rejoindre les 4 cercles rouges ont été coloriés en bleu.</p>-->
|
|
</div>
|
|
|
|
|
|
<h2>C'est de l'informatique !</h2>
|
|
|
|
<p>Les cercles et les flèches représentent une structure très fréquente en information, appelée <strong>graphe</strong>. Des graphes peuvent décrire des structures concrètes, comme par exemple des réseaux routiers ou des réseaux informatiques. Ils peuvent également décrire des structures abstraites, comme par exemple, un réseau social sur lequel chaque cercle représente une personne et chaque flèche représente le fait qu'une personne suit le fil d'actualité d'une autre personne.</p>
|
|
|
|
<p>La question que posait ce sujet porte sur la propriété <strong>d'accessibilité</strong> : quels sont les cercles à partir desquels on peut accéder à un ensemble d'autres cercles. Il existe des algorithmes très performants permettant à des ordinateurs de répondre de manière entièrement automatique à cette question et de traiter des cas avec des milliards de cercles et de flèches.</p>
|
|
|
|
|
|
</div> <!-- task-solution -->
|
|
</body>
|
|
</html>
|