300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийМегамозок
Total number of plays: 445808
| Кількість цифр | 0 | ||
| Діапазон цифр 1 .. | 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
- first all hot digits and
- 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
- 1) maximize the information gain with each guess, and
- 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?
- If you decided which digits should be in the next guess, does it matter in which order to put them?
- 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 third 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.
- Each such sequence of digits is called a permutation. So the question is: How many permutations are there for N objects, here N digits?
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 |
Слідкуйте за оновленнями або підписуйтесь на них: