Caribou in Covid: Contests are running online as usual. Check out the FAQ for further questions.
300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt
| 0 | |||
| 0 | |||
| 0 | |||
| 0 |
An abbreviation
- Instead of saying a digit "is occurring in the solution" we will just say this digit "is hot" and instead of saying it "is not occurring in the solution" we will just say it "is cold".
How could one break up the whole problem into sub-goals?
- A general strategy is to find
- A) first all hot digits and
- B) then their position.
What could be very general principles for formulating the next guess?
- In the guidelines below, we will follow two principles by trying to
- 1) maximize the information gain with each guess and
- 2) obtain information which is easy to use.
- Both principles contradict each other somewhat. For example, the less one guess is modified to submit the next guess, the easier it is to interpret the result but the more guesses are needed. The guidelines below will try to follow both principles.
Useful tools:
For the first phase A) it is useful to make a note of all possible digits, why?
- The list will allow us to cross out cold digits and underline hot ones.
For phase B) it is useful to have an elimination table, how and why?
- If the solution has N digits and if M digits (1,2,...,M) can appear then it is helpful to draw an elimination table (e.g. with pencil on paper) with N columns (one for each position in the solution) and M rows (one for each possible digit). Whenever a digit is known not to be at a certain position then a field in the table is crossed out. On the other hand, if a digit is known to be at a certain position then all other fields in that column can be crossed out. And if each digit can occur only once then also all other fields in that row can be crossed out.
A) How can one try to find all hot digits?
-
After submitting a guess, which outcomes (replies) would be very useful?
- We are lucky if it turns out that all or most guessed digits are hot, but we gained also much information if the two returned numbers are both 0 because then none of the guessed digits is occurring in the solution, i.e. all guessed digits are cold. In that case, we can cross out N digits from the list of possible digits or N rows in the elimination table.
-
If we are not so lucky, what is a possible strategy to find more hot digits?
- Let us assume that solutions have 4 digits and that digits 1,..,9 may come up at most once (otherwise modify the next 3 sentences). With the solution containing 4 digits we will guess 1,2,3,4 and then 5,6,7,8 and will automatically know about 9 by counting how many digits of 1,..,8 are hot. If there were four hot digits then 9 is cold else it is hot. If we are lucky and 1,2,3,4 are already hot then we will not try the other digits as they are cold.
- Let us assume we did a number of guesses, say 7, after which we know for each digit whether it is hot or cold.
-
Does it matter whether these 7 guesses contained mostly hot digits or cold digits?
- It seems to be equally useful to guess and know all hot digits or to guess all cold digits because knowing one set, one knows the other set too. But that is not the case. If our guesses contain many hot digits then we collect on the side also additional information about correct or incorrect positions of these hot digits. We will not collect this information if our guesses contain mostly cold digits.
-
Which principle do we follow when submitting guesses with many hot digits?
- Principle 1) because we in addition, collect information on positions which will be useful later when we know all hot positions.
-
Can you think of formulating guesses that follow principle 2)? In other words, which kind of guesses give replies that are easily usable?
- To follow principle 2) we could take a guess and modify it by taking one digit out, say 5, and another digit in, say 3. If the new guess has fewer hot digits then 5 is hot and 3 is cold. If the new guess has more hot digits then 5 is cold and 3 is hot. Otherwise 5 and 3 are both hot or both cold. To sort out between these two cases one could have both, 5 and 3 in the next guess. When deciding which guess to modify by one digit, we follow an earlier hint and pick a previous guess that had the most hot digits in order to collect also information about positions and follow principle 1).
- Let us assume you followed the earlier hint and submitted a guess where you only swapped one digit, say 7 by 3, and you learned from the outcome that the new digit 3 is hot and 7 is cold.
-
Is that all you learned from this guess?
- No. You now can go back to earlier guesses and use the knowledge that 3 is hot and 7 is cold to deduce more information from previous guesses. For example, an earlier guess included the 3 and had only one hot digit then the other digits in the that guess are cold. The fact that they are cold might give you a clue which other digits are hot from other guesses and so on.
-
If you decided which digits should be in the next guess, does it matter in which order to put them?
- We always want to follow principles 1) and 2). As long as we do not know which digits are hot or do not know the correct positions of hot digits we should put digits always at different positions and thus collect information about positions which will be useful later. In doing this we follow principle 1).
Once we know all hot digits we also know all cold digits and can cross out their rows in the elimination table.
B) How can we find the position of each hot digit?
-
Now that we know all hot digits, what feedback would be very useful?
- If all guessed digits are at the right position then, of course, we are lucky and solved the problem. Another lucky outcome is when none of the guessed digits is at the correct position. Then we learned a lot and can cross out N fields in the elimination table.
-
Recall, how we can use the elimination table in this final stage of the solution.
- If all rows of cold digits are crossed out and if there is a row or a column with only one field that is not crossed out then this tells us which digit has this position in the solution and the remaining free fields in this column can be crossed out. If each digit can occur only once then also all fields in this row can be crossed out.
-
How many numbers can be formed from the hot digits?
- Each such sequence of digits is called a permutation. So the question is: How many permutations are there for N objects, here N digits?
- If all digits are different then for the first digit there are N options. For each one of these N there are N−1 options for the second digit. For each of these N×(N−1) combinations there are N−2 options for the 3rd digit and so on, in total N×(N−1)×...×2×1 = N! (called N factorial) many.
- If not all digits are different then we could have, for example, N=4 and the 4 hot digits are 2,2,2,5. Then the product N! = 4! has to be divided by 3! because the ordering between the three 2's does not matter. We will get 4!/3! = 24/6 = 4 (or more elegantly 4!/3! = 4×3! / 3! = 4).
-
How many are that for N=3 or N=4?
- If each digit comes up only once we get 3! = 3×2×1 = 6 and 4! = 4×3! = 24 permutations (sequences). These are not many.
-
What does that mean for finding the solution?
- One could write down all numbers (permutations of N hot digits) and check them one by one with respect to all earlier guesses. Usually just one or two of these numbers remain possible which one can try as the next guess.
Please note: After a guess, we might know what the solution must be but we still need to submit the solution in order to prove the computer that we found it.
How often does one have to guess on average if the above hints are followed?
- The table below shows for different N (number of digits in solution), M (number of allowed digits) the average number G of guesses that we needed when following the hints above. Can you match or even improve on it and solve problems faster?
| N | M | G |
|---|---|---|
| 3 | 6 | 5 |
| 3 | 9 | 7 |
| 4 | 9 | 6 |
Une abréviation
- Pour faire plus court, quand on veut dire qu’un chiffre "figure dans la solution", on dira tout simplement que ce chiffre "est chaud". Au lieu de dire qu’un chiffre "ne figure pas dans la solution" on dira qu’il "est froid ".
Comment est-ce qu’on peut simplifier le problème en le divisant en sous-objectifs?
- Une stratégie générale consiste à trouver
- A) d’abord tous les chiffres chauds
- B) et ensuite leurs positions.
Sur quels principes pourrait-on baser sa proposition après avoir joué un coup?
- Dans les conseils suivants, on appliquera deux principes, c’est-à-dire en se tâchant d’
- 1) optimiser les informations gagnées à chaque coup
- 2) et d’obtenir des informations qui soient faciles à utiliser.
- Les deux principes se contredisent légèrement. Moins on modifie une proposition pour le prochain coup, plus le résultat sera facile à interpréter -- mais plus il faudra, aussi, de coups pour trouver la solution. Ceci dit, les recommandations ci-dessous se basent sur ces deux principes.
Des outils utiles:
Pour atteindre le premier sous-objectif A, pourquoi sera-t-il utile de dresser une liste de tous les chiffres possibles?
- Cette liste nous permettra de raturer les chiffres froids et de souligner les chiffres chauds.
Pour atteindre le deuxième sous-objectif B, comment et pourquoi pourrait-on créer une table d’élimination?
- Si la solution comprend N chiffres et si un nombre M de chiffres peuvent y figurer, il sera utile de tracer une table d’élimination qui fait N colonnes (une colonne pour chaque position dans la solution) par M rangées (une rangée pour chaque chiffre possible). Lorsqu’on déduit qu’un certain chiffre ne figure pas dans une position donnée, on rature ce champ. Or, si on déduit qu’un certain chiffre figure dans une position donnée, on rature tous les autres champs. En plus, si chaque chiffre ne peut apparaître qu’une seule fois dans la solution, on peut raturer tous les autres champs de cette rangée.
A) Comment trouver tous les chiffres chauds?
-
Quand on soumet une proposition, quels résultats nous seront les plus utiles?
- Certes, nous avons de la chance si tous ou la plupart des chiffres de notre proposition sont chauds, mais il est presqu’aussi utile de voir deux 0 car ceci veut dire qu’aucune des chiffres proposés ne figure dans la solution, c.-à-d. tous les chiffres proposés sont froids. Dans ce dernier cas, on peut raturer N chiffres de la liste des chiffres possibles ou N rangées de la table d’élimination.
-
Quelle est une stratégie pour trouver plus de chiffres chauds si nous sommes moins chanceux?
- Disons que nous jouons selon les paramètres par défaut (il y a donc 4 chiffres dans la solution et les chiffres 1..9 ne peuvent y figurer qu’une seule fois). Si la solution comprend 4 chiffres nous proposons 1,2,3,4 et puis 5,6,7,8 : on saura si 9 est chaud en dénombrant les chiffres chauds entre 1…8. C’est-à-dire, s’il y a 4 chiffres chauds entre 1 et 8, 9 est froid; sinon, il est chaud. Si du premier coup on sait que 1,2,3,4 sont chauds, il sera inutile de deviner les autres chiffres car ils doivent être froids.
- Supposons qu’on a proposé un nombre de solutions, disons 7, et qu’on sait quels chiffres sont chauds et lesquels sont froids.
-
Est-ce qu’il est important que ces 7 solutions proposées soient majoritairement chaudes ou majoritairement froides?
- On pourrait croire qu’il soit aussi utile de trouver tous les chiffres chauds ou de trouver tous les chiffres froids parce qu’en connaissant une des séries, on connaît l’autre aussi. Mais ce n’est pas le cas. Si nos propositions contiennent beaucoup de chiffres chauds, elles contiennent aussi des informations concernant les bons ou mauvais placements de ceux-ci. Ces informations ne sont pas présentes dans des propositions contenant beaucoup de chiffres froids.
-
Quel principe doit-on suivre en créant des propositions qui contiennent beaucoup de chiffres chauds?
- Le principe 1) car on recueille aussi des informations concernant les placements qui serviront lorsqu’on connaît tous les chiffres chauds.
-
Pouvez-vous voir comment on formule des propositions suivant le principe 2) ? C’est-à-dire, quelles sortes de propositions retourneront des résultats qui soient faciles à utiliser?
- Pour suivre le principe 2) on peut modifier une proposition déjà jouée en retirant un chiffre, disons 5, et en y insérant un autre chiffre, disons 3. Si la nouvelle proposition a moins de chiffres chauds, ceci veut dire que 5 est chaud et 3 est froid. Si la nouvelle proposition a plus de chiffres chauds, ceci veut dire que 5 est froid et 3 est chaud. Sinon 5 et 3 sont soit tous les deux chauds, soit tous les deux froids. Pour distinguer entre ces deux derniers cas, on pourra inclure les deux, 5 et 3, dans la proposition suivante. Pour choisir quelle proposition précédente à modifier d’un chiffre, on choisit celle qui avait le plus de chiffres chauds. Ce faisant, on recueille aussi des informations concernant les bons placements et on suit le principe 1).
- Supposons que vous avez suivi les conseils ci-dessus et que vous avez donc soumis une proposition où vous n’avez modifié qu’un chiffre, disons 7 remplacé par 3. Les résultats vous montrent que le nouveau chiffre 3 est chaud et que 7 était froid.
-
Est-ce toutes les informations que cette proposition vous a apportées?
- Non. Maintenant vous pouvez utiliser ces nouvelles informations, c.-à-d. que 3 est chaud et que 7 est froid, pour déduire plus d’informations des propositions précédentes. Par exemple, vous avez soumis une proposition qui comprenait un 3 et qui ne contenait qu’un chiffre chaud. Vous en déduit que tous les autres chiffrent doivent être froids, et le fait qu’ils sont froids peuvent servir à mieux interpréter d’autres propositions précédentes, et ainsi de suite.
-
Si on sait quels chiffres on veut mettre dans la prochaine proposition, est-ce qu’il est important qu’on les mette dans un certain ordre?
- On veut toujours suivre les principes 1) et 2). Tant qu’on ne sait pas quels chiffres sont chauds ou qu’on ne connaît pas les bons placements des chiffres chauds, il est mieux qu’on mette constamment les chiffres dans de nouveaux placements afin de recueillir des informations sur les placements qui serviront plus tard. Ce faisant, on suit le principe 1).
Une fois qu’on connaît tous les chiffres chauds, on connaît donc aussi tous les chiffres froids, et on peut raturer leurs rangées dans la table d’élimination.
B) Comment peut-on trouver la bonne position de chaque chiffre chaud?
-
Maintenant qu’on a trouvé tous les chiffres chauds, quels résultats sont les plus utiles?
- Si la proposition comprend déjà tous les chiffres chauds bien placés, on a de la chance car on détient la solution. On serait aussi heureux de savoir qu’aucun des chiffres proposés n’était bien placé car ces informations nous permettent de raturer N champs dans la table d’élimination.
-
Comment utilise-t-on la table d’élimination pour formuler la bonne solution?
- Si toutes les rangées des chiffres froids sont raturées, et s’il y a une rangée ou une colonne dont un seul champ n’est pas raturé, on sait que ce chiffre correspond à cette position, et qu’on peut raturer les champs restants dans cette colonne. Si chaque chiffre ne peut figurer qu’une seule fois dans la solution, on peut raturer aussi tous les champs restants dans la rangée.
-
Combien de combinaisons peut-on formuler à partir des chiffres chauds?
- On appelle "permutation" une telle séquence de chiffres. Alors la question qui se pose est : Combien de permutations existent pour N objets, ici N chiffres?
- Si tous les chiffres sont uniques, alors pour le premier chiffre il y a N options. Pour chacune de ces N options il y a N−1 options pour le deuxième chiffre. Pour chacune de ces N−1 options il y a N−2 options pour le troisième chiffre et ainsi de suite, alors en total il y en a N×(N−1)×...×2×1 = N! (dit N factoriel).
- Si les paramètres du jeu font que les chiffres ne doivent pas être uniques, on pourra avoir N=4 où les chiffres chauds sont 2,2,2,5. Alors on devra diviser le produit N! = 4! par 3! parce que l’ordre des trois 2 n’est pas important. On obtiendra 4!/3! = 24/6 = 4 (ou, formulé avec plus d’élégance, 4!/3! = 4×3! / 3! = 4).
-
Combien de permutations sont possibles quand N=3 ou N=4?
- Si chaque chiffre est unique, on obtient 3! = 3×2×1 = 6 et 4! = 4×3! = 24 permutations (séquences). Ce n’est pas beaucoup.
-
Comment cela nous aide-t-il à trouver la solution?
- On pourrait dresser la liste de toutes les combinaisons (les permutations de N chiffres chauds) et les vérifier une par une en interprétant les résultats des propositions précédentes. D’habitude il ne reste qu’une ou deux séquences possibles à proposer.
Veuillez noter : Après avoir proposé une solution, on pourra connaître la solution mais il faut quand même la soumettre pour prouver à l’ordinateur qu’on l’a trouvée.
En jouant selon les conseils ci-dessus, combien de propositions faut-il en moyenne pour trouver la solution?
- Dans la table ci-dessous sont figurés le nombre moyen de propositions nécessaires G pour trouver la solution d’un casse-tête comprenant N chiffres choisis parmi M chiffres possibles. Parvenez-vous à résoudre le casse-tête en autant de coups, voire à améliorer la stratégie pour résoudre le casse-tête encore plus rapidement?
| N | M | G |
|---|---|---|
| 3 | 6 | 5 |
| 3 | 9 | 7 |
| 4 | 9 | 6 |
437740
Follow or subscribe for updates: