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 | Bahasa Melayu| 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 |
یکنامگذاری برای خلاصه نویسی
- به جای اینکه بگوییم یک رقم « در جواب ظاهرمیشود» فقطمیگوییم که آن رقم «داغ است»و به جای اینکه بگوییم یک رقم « در جواب ظاهر نمیشود» فقطمیگوییم که آن رقم «سرد است» .
چگونهمیتوانیکسوال کلی را به چند سوال فرعی تقسیم کرد؟
- یک روش عمومی شامل دو مرحله است:
- الف) پیدا کردن تمامرقمهای داغ
- ب ) پیدا کردن محل قرار گرفتن آنها
اصول کلی یک فرمولبرای حدس بعدی چه میتواند باشد؟
- دردستورالعملهای زیر، سعی میکنیم دو اصل زیر را رعایت کنیم:
- 1) با هر حدس، بیشترین اطلاعاتممکن را به دست آوریم.
- 2)اطلاعاتی را پیدا کنیم کهاستفاده از آنها آسان باشد.
- این دو اصلدربعضیمواردبا هم در تناقض هستند.برای مثال، هر چقدر که یک حدس،برای ارائه حدس بعدی،کمتر اصلاح شود، تفسیر نتیجه آسانتر است اما به حدسهای بیشتری نیاز خواهد بود.
ابزارهای مفید :
برای انجام مرحله (الف) بهتر است که تمامرقمهای ممکن را یادداشت کنیم. چرا؟
- این لیست به ما اجازهمیدهد کهرقمهای سرد را خط بزنیم و دوررقمهای داغ خط بکشیم.
برای انجام مرحله (ب) بهتر است که یک جدول حذفیداشته باشیم. چرا و چگونه؟
- اگر جوابشاملNرقم باشد و اگرMرقم1و2و . . . وMبتوانند در آن ظاهر شوند، آنگاه رسم یک جدول حذفی(مثلابا مداد و کاغذ) که شاملNستون ( به تعدادرقمهای جواب) وMسطر (به تعدادرقمهایمجاز)باشدمفید است.هر وقت که مشخص شد یک رقم نمیتواند در یک مکان خاص از جواب قرار بگیرد، در خانه مربوط به آن رقم و آن موقعیت علامت ضرب قرار میدهیمو می گوییم «آن خانه را خط زدهایم».از طرف دیگر، اگر مشخص شد که یک رقم باید در یک موقعیت خاص قرار بگیرد،بقیه خانههای آن ستونرا خطمیزنیم.و اگرهررقم،فقط یک مرتبه درجواب ظاهر شود،بقیه خانههای سطر مربوط به آنرا خطمیزنیم.
الف) چگونهمیتوان تمامرقمهای داغ را پیدا کرد؟
-
بعد از ارائه یکحدس، چه نتایجی (پاسخهایی) مفید خواهند بود؟
- اگر همه یا بیشتررقمهای حدس زده شده داغ باشند خیلی خوب است، اما اگر دوعدد برگشتی هر دو برابر صفر باشند هم اطلاعات زیادی به دستمیآوریم زیرا نتیجهمیگیریم که هیچیک ازرقمهای حدس زده شده در جواب ظاهر نمیشوند ، یعنی، تمام اینرقمهاسرد هستند. در این حالتمیتوانیم اینرقمهای سرد(Nرقم)را از لیست حذف کنیم و یاتمامخانههایسطرهای مربوط به آنها(Nسطر) رادرجدول حذفی خط بزنیم.
-
اما اگر این قدر خوش شانس نباشیم، یک روش ممکن برای پیدا کردنتعداد بیشتری ازرقمهای داغ
چیست؟
- فرض میکنیم که جواب4رقم دارد ورقمهای آن میتوانند یکیازرقمهای1و2و . . . و9باشند که دقیقا یک بار ظاهر خواهند شد( در غیر این صورت3جمله بعدی را اصلاح کنید).چون جواب4 رقمی است، حدس اول ما شامل4رقم1و2و3و4است و حدس دوم شامل5و6و7و8خواهد بود. وقتی که تعدادرقمهای داغ در این دو حدس را بدانیم،تکلیف رقم9بطور خودکار مشخصمیشود. اگر در میان این8رقم،4رقم داغ باشد،9سرد است و در غیر این صورت داغ خواهد بود.اگر خوش شانس باشیم و هر4رقم1و2و3و4داغ باشند، با بقیهرقمهاکارینخواهیم داشت زیرا تمام آنها سرد هستند.
- فرض میکنیم که پس از تعدادی حدس، مثلا7تا حدس، متوجه شدهایم که کدامیک ازرقمهاداغ و کدامیک از آنها سرد هستند.
-
آیا اینکه این7حدس، بیشتر در موردرقمهای داغ باشند یا در موردرقمهای سرد، اهمیتی دارد؟
- به نظرمیآید که هر دو حالت به یک اندازه مفید هستند.زیرا پیدا کردن تمامرقمهای داغبا پیدا کردن تمامرقمهای سرد هیچ تفاوتی با هم ندارند. هر دسته ازرقمهارا که پیدا کنیم دسته دیگر هم پیدا شدهاست.اما دقیقا این طور نیست. زیرا اگر بیشتر حدسهای ما در موردرقمهای داغ باشند، به اطلاعات بیشتری در مورد آنها و محل قرار گرفتنرقمهای داغ نیز دست پیدا میکنیم. در حالی که اگر حدسهای ما در موردرقمهای سرد باشند چنین اطلاعاتی به دست نمیآید.
-
وقتی که بیشتر حدسهای ما در موردرقمهای داغ هستند از چه اصلی باید پیروی کنیم؟
- اصل (1) ، زیرادر مرحلههای بعدی برای پیدا کردن جواب نهایی،علاوه بر شناساییرقمهای داغ، جمع آوری اطلاعات در مورد موقعیت اینرقمهادر جواب،نیزمفید خواهد بود.
-
آیامیتوانید در مورد فرمول بندیحدسهایی که از اصل (2) پیرویمیکنند فکر کنید؟به عبارت
دیگر، چهحدسهاییمیتوانند نتایجی در اختیار ما بگذارند که به سادگی قابل استفاده باشند؟
- برای استفاده از اصل (2)میتوانیم یک حدس را با حذف یک رقم، مانند5، و اضافه کردن یک رقم دیگر، مثلا3، تغییر دهیم. اگر تعدادرقمهای داغ در حدس جدیدکمتر از حدس قبلی بود متوجه میشویم که رقم3سرد و رقم5داغ استو اگر تعدادرقمهای داغ در حدس جدیدبیشتر از حدس قبلی بود متوجهمیشویم که رقم3داغ و رقم5سرد است. در غیر این صورت، دو رقم3و5یا هر دو سرد و یا هر دو داغ خواهند بود.برای تعیین وضعیت3و5میتوان این دو رقم رادر حدس بعدی قرار داد.برای تغییر یک حدس با حذف و اضافه کردن یک رقم، از نکته قبلی استفاده میکنیم و از حدسهایی استفاده میکنیم که تعداد رقم داغ بیشتری داشته باشند که به این وسیله بتوانیم اطلاعاتی در مورد موقعیترقمهایداغ در جواب نهایی پیدا کرده و از اصل(1) هم پیروی کرده باشیم.
- فرض میکنیم که با توجه به نکته قبلی، شمایک حدس جدیدی را با حذف رقم7و اضافه کردن رقم 3در حدس قبلی ارائه کردهاید و به این نتیجه رسیدهاید که رقم3داغ و رقم7سرداست.
-
آیا این تنها چیزی است که شما در مورد این حدسمیدانید؟
- خیر. شمامیتوانید به حدس قبلی برگردید و با توجه به اینکه اکنونمیدانیدکه رقم3یک رقم داغ و 7یک رقم سرد است،اطلاعات بیشتری از حدس قبلی کسب کنید.برای مثال، حدس قبل که شامل رقم 3است،اگر فقط یک رقم داغ داشته باشد آنگاه بقیهرقمهای آن حدسرقمهای سرد خواهند بود.این اطلاعات جدید ممکن است به شما کمک کنند که داغ بودن بعضی ازرقمهادرحدسهای قبلی دیگر را نتیجه بگیرید.
-
وقتی که شما تصمیممیگیرید یک رقم را در حدس جدیدخودتانقرار دهید، آیا محل قرار گرفتن
آن رقم اهمیت دارد؟
- ما همیشهمیخواهیم ازاصلهای (1( و )2) پیروی کنیم.تا وقتی که ما نمیدانیم کدام یک ازرقمها داغ هستند و یا محل قرار گرفتنرقمهای داغ را نمیدانیم سعی میکنیم کهرقمهارا در موقعیتهای مختلف قرار دهیم و به این ترتیب اطلاعات بیشتری در مورد آنها پیدا کنیم که در مرحلههایبعدی برای ما مفید خواهند بود. برای این کار از اصل (1) پیروی میکنیم.
وقتی که تمامرقمهای داغ را شناسایی کردیمآنگاه تمامرقمهای سرد هم مشخص شدهاند و سطرهای مربوط به آنها را از جدول حذفی خطمیزنیم.
ب ) چگونهمیتوانیم محل قرار گرفتنرقمهایداغ را مشخص کنیم؟
-
اکنون که تمامرقمهای داغ رامیشناسیم،چه اطلاعاتی برای ما مفید خواهد بود؟
- اگر تمامرقمهای داغ در محل صحیح خود قرار گرفته باشند،خیلی خوش شانس بودهایمو جواب پیدا شدهاست.اتفاق خوب دیگر این است که هیچکدام ازرقمهادر محل واقعی خود قرار نگرفته باشند. در این صورت هم اطلاعات زیادی داریم ومیتوانیمNخانه از جدول حذفیرا خط بزنیم.
-
به یاد داشته باشیم که چگونهمیتوانیمبرای رسیدن به جواب،از جدول حذفی کمک بگیریم.
- اگر تمام سطرهای مربوط بهرقمهای سرد خط خورده باشند و سطری وجود داشته باشد که فقط یک خانه خط نخورده داشته باشد،آنگاه متوجهشدهایمکهرقممربوط به آن سطرباید در موقعیت مربوط به ستون آن خانه در جوابقرار بگیرد و بقیه خانههای آن ستون را باید خط بزنیم. اگر ستونی وجود داشته باشد که فقط یک خانه آن خط نخورده باشد، آنگاه رقم مناسب برای موقعیت مربوط به آن ستون را پیدا کردهایم و اگر هر رقم فقط یک بار در جواب ظاهرمیشود، تمام خانههای دیگر سطر مربوط بهآن خانه را باید خط بزنیم.
-
بارقمهای داغ،چند عددمیتوان ساخت؟
- هر یک از اعدادی (دنبالهای ازرقمها) کهمیتوان نوشت را یک جایگشتمینامند. بنابر این، سوال این است : برایNشیء، در اینجاNرقم، چند جایگشت وجود دارد؟
- اگر همهرقمهامتمایز باشند آنگاه برای اولین رقم،Nانتخاب داریم. هر رقمی را که انتخاب کنیم برای رقم بعدیN-1انتخاب خواهیم داشت. برای رقم سوم ،N-2انتخاب و . . . Must be deleted. I think!Must be added. I think! در مجموع تعداد انتخابها برابرN x (N-1) x . . . x2 x1=N!(Nفاکتوریل)است.
- اگر تمامرقمهای داغ متمایز نباشند، آنگاه برای مثال ممکن است داشته باشیمN=4ورقمهای داغ2 و2و2و5باشند. در این صورت بایدN!=4!را بر3!تقسیم کنیم. چون ترتیب انتخابسهعدد2 اهمیتی ندارد. در این مثال،جواب برابر است با4!/3!=24/6=4( یابه صورتهوشمندانهتر: 4!/3!=4 x 3!/3!=3.
-
اگرN=3یاN=4آنگاه چند جایگشت وجود دارد؟
- اگر هررقم فقط یک مرتبهدر جواب ظاهر شود، تعداد حایگشتها(دنبالههایرقمها)، به ترتیب، برابر3!=3 x 2 x 1=6و4!=4 x 3 x 2 x 1=24است.
-
این عدد چه کمکی به پیدا کردن جوابمیکند؟
- میتوان تمام اعداد ممکن (جایگشتهایNرقم داغ) را نوشت و هر یک از آنها را با توجه به حدسهای قبل بررسی کرد.معمولا، یک یا دو عدد باقیمیمانند که نیاز به حدسهای جدید داشته باشند.
لطفا توجه داشته باشید که : بعد از یکی ازحدسها، ممکن است جواب را پیدا کرده باشیم اما لازم است که جواب را ارسال کنیم و به رایانه ثابت کنیمکه جواب را پیدا کردهایم.
اگر از نکات گفته شده استفاده کنیم، معمولا و بطور متوسط، به چند حدس نیاز خواهیم داشت؟
- در جدول زیر به ازای مقادیر مختلفN(تعدادرقمهای جواب)وM(تعدادرقمهای مجاز)، عددG مقدار متوسط تعداد حدسهای لازم را،وقتی که از نکتههای گفته شده پیروی کرده باشیم،نشان میدهد.آیامیتوانیدبا این تعداد حدس به جواببرسید و یا اینکه تعداد حدسها را کاهش دهید؟
| N | M | G |
|---|---|---|
| 3 | 6 | 5 |
| 3 | 9 | 7 |
| 4 | 9 | 6 |
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 |
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 |
Abreviatura
- Rəqəm "həlldə baş verir" demək əvəzinə, bu rəqəm "isti" və "həlldə baş vermir" demək əvəzinə, sadəcə olaraq deyəcəyik. həlli" biz sadəcə "soyuqdur" deyəcəyik.
Bütün problemi alt məqsədlərə necə bölmək olar?
- Ümumi strategiya tapmaqdır
- A) ilk növbədə bütün isti rəqəmlər və
- B) sonra onların mövqeyi.
Növbəti təxminin formalaşdırılması üçün çox ümumi prinsiplər nə ola bilər?
- Aşağıdakı təlimatlarda biz çalışaraq iki prinsipə əməl edəcəyik
- 1) hər bir təxminlə məlumat qazancını maksimuma çatdırın və
- 2) istifadəsi asan olan məlumatları əldə edin.
- Hər iki prinsip bir-biri ilə müəyyən qədər ziddiyyət təşkil edir. Məsələn, növbəti təxminləri təqdim etmək üçün bir təxmin nə qədər az dəyişdirilərsə, onu şərh etmək bir o qədər asan olar nəticə, lakin daha çox təxminlərə ehtiyac var. Aşağıdakı təlimatlar hər iki prinsipə əməl etməyə çalışacaq.
Faydalı alətlər:
Birinci mərhələ üçün A) bütün mümkün rəqəmləri qeyd etmək faydalıdır, niyə?
- Siyahı soyuq rəqəmlərin üstündən xətt çəkməyə və isti rəqəmlərin altını çəkməyə imkan verəcək.
B) faza üçün eliminasiya cədvəlinin olması faydalıdır, necə və niyə?
- Həlldə N rəqəm varsa və M rəqəmləri (1,2,...,M) görünə bilərsə, aradan qaldırılmasını çəkmək faydalıdır. N sütunlu (məhluldakı hər mövqe üçün bir) və M sətirli (hər biri üçün bir) cədvəl (məsələn, kağız üzərində qələmlə) mümkün rəqəm). Rəqəmin müəyyən bir mövqedə olmadığı məlum olduqda, cədvəldəki sahənin üstündən xətt çəkilir. Aktiv digər tərəfdən, əgər rəqəmin müəyyən bir mövqedə olduğu məlumdursa, o zaman həmin sütundakı bütün digər sahələr keçə bilər. həyata. Əgər hər bir rəqəm yalnız bir dəfə baş verə bilərsə, o zaman həmin cərgədəki bütün digər sahələrin üstündən xətt çəkilə bilər.
A) Bütün isti rəqəmləri necə tapmağa cəhd etmək olar?
-
Təxmin təqdim etdikdən sonra hansı nəticələr (cavablar) çox faydalı olardı?
- Bütün və ya ən çox təxmin edilən rəqəmlərin isti olduğu ortaya çıxarsa, şanslıyıq, lakin ikisi geri qayıtsa, biz də çox məlumat əldə etdik. ədədlərin hər ikisi 0-dır, çünki onda təxmin edilən rəqəmlərin heç biri həlldə baş vermir, yəni bütün təxmin edilən rəqəmlər soyuqdur. Bu halda, mümkün rəqəmlər siyahısından N rəqəmi və ya ləğvetmə cədvəlindəki N sətirləri kəsə bilərik.
-
Əgər o qədər də şanslı deyiliksə, daha çox isti rəqəmlər tapmaq üçün hansı strategiya ola bilər?
- Fərz edək ki, həllərin 4 rəqəmi var və 1,...,9 rəqəmləri ən çox bir dəfə çıxa bilər (əks halda növbəti 3 cümləni dəyişdirin). 4 rəqəmdən ibarət məhlul ilə biz 1,2,3,4 və sonra 5,6,7,8-i təxmin edəcəyik və 1,...,8-in neçə rəqəminin isti olduğunu saymaqla avtomatik olaraq 9-u biləcəyik. Dörd isti olsaydı 9 rəqəmi soyuqdur, əksinə istidir. Əgər şanslıyıqsa və 1,2,3,4 artıq istidirsə, digər rəqəmləri sınamayacağıq, çünki onlar soyuqdur.
- Tutaq ki, biz bir sıra təxminlər etdik, məsələn, 7, bundan sonra hər rəqəm üçün onun isti və ya soyuq olduğunu bilirik.
-
Bu 7 təxminin əsasən isti və ya soyuq rəqəmlərdən ibarət olmasının əhəmiyyəti varmı?
- Bütün isti rəqəmləri təxmin etmək və bilmək və ya bütün soyuq rəqəmləri təxmin etmək eyni dərəcədə faydalı görünür, çünki bir çoxluğu bilən biri digər çoxluğu da bilir. Amma belə deyil. Təxminlərimizdə çoxlu isti rəqəmlər varsa, biz yan tərəfdə bu istilərin düzgün və ya yanlış mövqeləri haqqında əlavə məlumat toplayırıq. rəqəmlər. Təxminlərimizdə əsasən soyuq rəqəmlər varsa, bu məlumatı toplamırıq.
-
Çox isti rəqəmlərlə təxminlər təqdim edərkən hansı prinsipə əməl edirik?
- Prinsip 1) çünki biz əlavə olaraq, bütün isti mövqeləri bildiyimiz zaman faydalı olacaq mövqelər haqqında məlumat toplayırıq.
-
2-ci prinsipə əməl edən təxminlər tərtib etməyi düşünə bilərsinizmi? Başqa sözlə, hansı növ təxminlər asanlıqla istifadə edilə bilən cavablar verir?
- 2-ci prinsipə əməl etmək üçün) biz bir rəqəmi çıxararaq, deyək ki, 5 və digər rəqəmi, deyək ki, 3-ü çıxarmaqla təxmin edə və onu dəyişdirə bilərik. daha az isti rəqəmə malikdir, ondan sonra 5 isti və 3 soyuqdur. Yeni təxmində daha çox isti rəqəm varsa, 5 soyuq, 3 isə istidir. Əks halda 5 və 3 həm isti, həm də soyuqdur. Bu iki hal arasında sıralamaq üçün hər ikisi, növbəti təxmində 5 və 3 ola bilər. Hansına qərar verərkən bir rəqəmlə dəyişdirməyi təxmin edirik, biz əvvəlki ipucuya əməl edirik və həmçinin toplamaq üçün ən isti rəqəmlərə malik olan əvvəlki təxminləri seçirik. vəzifələr haqqında məlumat və 1 prinsipinə əməl edin).
- Fərz edək ki, siz əvvəlki ipucunu izləmisiniz və yalnız bir rəqəmi, məsələn, 7-ni 3-ə dəyişdiyiniz bir təxmin təqdim etdiniz və nəticədən öyrəndiniz ki, yeni 3 rəqəmi isti, 7 isə soyuqdur.
-
Bu təxmindən öyrəndiyiniz bütün bunlardır?
- Xeyr. İndi əvvəlki təxminlərə qayıdıb əvvəlki təxminlərdən daha çox məlumat çıxarmaq üçün 3-ün isti və 7-nin soyuq olmasından istifadə edə bilərsiniz. Məsələn, əvvəlki təxmin 3-ü əhatə edirdi və yalnız bir isti rəqəmə malik idi, sonra bu təxmindəki digər rəqəmlər soyuqdur. Onların olması faktı soyuq sizə hansı digər rəqəmlərin digər təxminlərdən qaynar olduğuna dair bir ipucu verə bilər və s.
-
Növbəti təxmində hansı rəqəmlərin olması lazım olduğuna qərar verdinizsə, onları hansı ardıcıllıqla qoymağın əhəmiyyəti varmı?
- Biz həmişə 1) və 2) prinsiplərinə əməl etmək istəyirik. Nə qədər ki, hansı rəqəmlərin isti olduğunu bilmirik və ya düzgün mövqelərini bilmirik isti rəqəmlər rəqəmləri həmişə fərqli mövqelərə qoymalıyıq və beləliklə, faydalı olacaq mövqelər haqqında məlumat toplamalıyıq sonra. Bunu edərkən 1) prinsipinə əməl edirik.
Bütün isti rəqəmləri bildikdən sonra bütün soyuq rəqəmləri də bilirik və aradan qaldırılması cədvəlində onların cərgələrini keçə bilərik.
B) Hər isti rəqəmin yerini necə tapa bilərik?
-
İndi bütün isti rəqəmləri bildiyimizə görə, hansı rəy çox faydalı olardı?
- Bütün təxmin edilən rəqəmlər düzgün mövqedədirsə, əlbəttə ki, şanslıyıq və problemi həll etdik. Başqa bir şanslı nəticə, heç birinin olmamasıdır təxmin edilən rəqəmlər düzgün mövqedədir. Sonra biz çox şey öyrəndik və aradan qaldırılması cədvəlində N sahənin üstündən xətt çəkə bilərik.
-
Çözümün bu son mərhələsində aradan qaldırılması cədvəlindən necə istifadə edə biləcəyimizi xatırlayın.
- Soyuq rəqəmlərin bütün sətirlərinin üstündən xətt çəkilibsə və üstündən xətt çəkilməyən yalnız bir sahə olan sətir və ya sütun varsa, bu, bizə hansı rəqəmin olduğunu bildirir. həlldəki bu mövqe və bu sütunda qalan boş sahələrin üstündən xətt çəkilə bilər. Hər bir rəqəm yalnız bir dəfə baş verə bilərsə, onda bütün sahələr də baş verə bilər sıranın üstündən xətt çəkilə bilər.
-
İsti rəqəmlərdən neçə ədəd yaratmaq olar?
- Rəqəmlərin hər bir belə ardıcıllığına permutasiya deyilir. Beləliklə, sual yaranır: N obyekt üçün neçə dəyişmə var, burada N rəqəm var?
- Bütün rəqəmlər fərqlidirsə, birinci rəqəm üçün N seçim var. Bu N-nin hər biri üçün ikinci rəqəm üçün N-1 variantları var. Bu Nx(N-1) kombinasiyalarının hər biri üçün 3-cü rəqəm üçün N-2 variantları və s. var, cəmi Nx(N-1x...x2x1 = N! (N faktorial adlanır) çoxdur.
- Əgər bütün rəqəmlər fərqli deyilsə, onda bizdə ola bilər, məsələn, N=4 və 4 isti rəqəm 2,2,2,5-dir. Sonra məhsul N! = 4! 3-ə bölünməlidir! çünki üç 2 arasındakı sıralamanın əhəmiyyəti yoxdur. 4!/3 alacağıq! = 24/6 = 4 (və ya daha zərif 4!/3! = 4x3! / 3! = 4).
-
N=3 və ya N=4 üçün bu neçədir?
- Hər bir rəqəm yalnız bir dəfə gəlsə, biz 3 alırıq! = 3x2x1 = 6 və 4! = 4x3! = 24 permutasiya (ardıcıllıq). Bunlar çox deyil.
-
Həll tapmaq üçün bu nə deməkdir?
- Bütün nömrələri (N isti rəqəmin dəyişdirilməsi) yazmaq və bütün əvvəlki təxminlərə uyğun olaraq onları bir-bir yoxlamaq olar. Adətən sadəcə bu nömrələrdən biri və ya ikisi mümkün olaraq qalır, hansı biri növbəti təxmin kimi cəhd edə bilər.
Nəzərə alın: Təxmin etdikdən sonra həllin nə olduğunu bilə bilərik, lakin kompüterə tapdığımızı sübut etmək üçün hələ də həlli təqdim etməliyik.
Yuxarıdakı göstərişlərə əməl olunarsa, orta hesabla nə qədər tez-tez təxmin etmək lazımdır?
- Aşağıdakı cədvəl müxtəlif N (həlldəki rəqəmlərin sayı), M (icazə verilən rəqəmlərin sayı) üçün ehtiyac duyduğumuz təxminlərin orta sayını G göstərir. yuxarıdakı göstərişlərə əməl edin. Buna uyğunlaşa və ya hətta təkmilləşdirə və problemləri daha sürətli həll edə bilərsinizmi?
| N | M | G |
|---|---|---|
| 3 | 6 | 5 |
| 3 | 9 | 7 |
| 4 | 9 | 6 |
អក្សរកាត់
- ជំនួសឱ្យការនិយាយថាលេខមួយខ្ទង់នេះ "កំពុងកើតមាននៅក្នុងដំណោះស្រាយ" យើងគ្រាន់តែនិយាយថាលេខមួយខ្ទង់នេះវា "ក្តៅ" ហើយជំនួសឱ្យការនិយាយថាវា "មិនកើតឡើងនៅក្នុងដំណោះស្រាយ" យើងគ្រាន់តែនិយាយថាវា "ត្រជាក់" ។
តើគេអាចបំបែកបញ្ហាទាំងមូលទៅជាបញ្ហាតូចៗដោយរបៀបណា?
- យុទ្ធសាស្ត្រទូទៅគឺស្វែងរក
- ក) ជាដំបូងលេខក្តៅទាំងអស់ និង
- ខ) បន្ទាប់មកទីតាំងរបស់ពួកគេ។
តើអាចជាគោលការណ៍ទូទៅសម្រាប់បង្កើតការស្មានបន្ទាប់បានទេ?
- នៅក្នុងការណែនាំខាងក្រោម យើងនឹងអនុវត្តតាមគោលការណ៍ពីរដោយព្យាយាម
- 1) បង្កើនការទទួលបានព័ត៌មានដោយការស្មាននីមួយៗ និង
- 2) ទទួលបានព័ត៌មានដែលងាយស្រួលប្រើ។
- គោលការណ៍ទាំងពីរផ្ទុយស្រឡះពីគ្នាទៅវិញទៅមក។ ជាឧទាហរណ៍ ការស្មានតិចជាងមួយត្រូវបានកែប្រែដើម្បីដាក់ការទស្សន៍ទាយបន្ទាប់ វាកាន់តែងាយស្រួលក្នុងការបកស្រាយលទ្ធផល ប៉ុន្តែត្រូវការការទាយកាន់តែច្រើន។ គោលការណ៍ណែនាំខាងក្រោមនឹងព្យាយាមអនុវត្តតាមគោលការណ៍ទាំងពីរ។
ឧបករណ៍មានប្រយោជន៍៖
សម្រាប់ដំណាក់កាលទី 1 ក) វាមានប្រយោជន៍ក្នុងការកត់ត្រាលេខតាមខ្ទង់ដែលអាចធ្វើបានទាំងអស់ ហេតុអ្វី?
- បញ្ជីនេះនឹងអនុញ្ញាតឱ្យយើងឆ្លងកាត់ខ្ទង់ត្រជាក់ និងគូសបញ្ជាក់លេខក្តៅ។
សម្រាប់ដំណាក់កាល ខ) វាមានប្រយោជន៍ក្នុងការមានតារាងលុបបំបាត់ តើដោយរបៀបណា និងហេតុអ្វី?
- បើដំណោះស្រាយមានលេខ N ហើយប្រសិនបើខ្ទង់ M (1,2,...,M) អាចលេចឡើង នោះវាមានប្រយោជន៍ក្នុងការគូរតារាងលុបបំបាត់ (ឧទាហរណ៍ជាមួយខ្មៅដៃនៅលើក្រដាស) ជាមួយជួរឈរ N (មួយសម្រាប់ទីតាំងនីមួយៗនៅក្នុងដំណោះស្រាយ។ ) និងជួរ M (មួយសម្រាប់ខ្ទង់នីមួយៗដែលអាចធ្វើបាន)។ នៅពេលណាដែលលេខមួយត្រូវបានគេដឹងថាមិនស្ថិតនៅទីតាំងជាក់លាក់មួយ នោះនៅក្នុងតារាងត្រូវបានកាត់វាចេញ។ ម្យ៉ាងវិញទៀត ប្រសិនបើលេខមួយត្រូវបានគេដឹងថាស្ថិតនៅទីតាំងជាក់លាក់មួយ នោះលេខផ្សេងទៀតទាំងអស់នៅក្នុងជួរឈរនោះអាចត្រូវបានកាត់ចេញ។ ហើយប្រសិនបើខ្ទង់នីមួយៗអាចកើតឡើងបានតែម្តងគត់ នោះលេខផ្សេងទៀតទាំងអស់នៅក្នុងជួរនោះក៏អាចត្រូវបានកាត់ចេញផងដែរ។
ក) តើធ្វើដូចម្តេចដើម្បីស្វែងរកលេខក្តៅទាំងអស់?
-
បន្ទាប់ពីបានដាក់ស្នើការទស្សន៍ទាយ តើលទ្ធផលមួយណា (ឆ្លើយតប) នឹងមានប្រយោជន៍ខ្លាំង?
- យើងមានសំណាងប្រសិនបើវាប្រែថាលេខដែលទាយទាំងអស់ ឬភាគច្រើនគឺក្តៅ ប៉ុន្តែយើងក៏ទទួលបានព័ត៌មានជាច្រើនផងដែរ ប្រសិនបើលេខទាំងពីរត្រឡប់មកវិញគឺ 0 ព្រោះពេលនោះគ្មានលេខទាយណាមួយកើតឡើងនៅក្នុងដំណោះស្រាយ ពោលគឺលេខដែលទាយទាំងអស់គឺត្រជាក់។ ក្នុងករណីនោះ យើងអាចកាត់ខ្ទង់ N ពីបញ្ជីខ្ទង់ដែលអាចប្រើបាន ឬជួរ N ក្នុងតារាងលុបចោល។
-
បើយើងមិនសូវមានសំណាងទេ តើមានយុទ្ធសាស្ត្រអ្វីដើម្បីស្វែងរកលេខក្តៅបន្ថែមទៀត?
- អនុញ្ញាតឱ្យយើងសន្មតថាដំណោះស្រាយមាន 4 ខ្ទង់ ហើយខ្ទង់ 1,..,9 អាចនឹងកើតឡើងភ្លាមៗ (បើមិនដូច្នេះទេកែប្រែប្រយោគ 3 បន្ទាប់)។ ជាមួយនឹងដំណោះស្រាយដែលមាន 4 ខ្ទង់ យើងនឹងទាយ 1,2,3,4 ហើយបន្ទាប់មក 5,6,7,8 ហើយនឹងដឹងដោយស្វ័យប្រវត្តិអំពី 9 ដោយរាប់ចំនួនខ្ទង់នៃ 1,..,8 គឺក្តៅ។ បើមានបួនខ្ទង់ក្តៅ នោះលេខ៩គឺត្រជាក់ ឯវាក្តៅ។ ប្រសិនបើយើងមានសំណាងហើយ 1,2,3,4 ក្តៅរួចហើយ នោះយើងនឹងមិនសាកល្បងលេខផ្សេងទៀតទេ ព្រោះវាត្រជាក់។
- សន្មតថាយើងបានទាយលេខ 7 បន្ទាប់ពីនោះយើងដឹងសម្រាប់ខ្ទង់នីមួយៗថាតើវាក្តៅ ឬត្រជាក់។
-
តើវាជាបញ្ហាទេបើការទាយទាំង៧នេះមានលេខក្តៅ ឬលេខត្រជាក់?
- វាហាក់ដូចជាមានប្រយោជន៍ស្មើៗគ្នាក្នុងការទស្សន៍ទាយ និងដឹងលេខក្តៅទាំងអស់ ឬអាចទាយលេខត្រជាក់ទាំងអស់ ព្រោះដឹងមួយឈុតក៏ស្គាល់ឈុតមួយទៀតដែរ។ ប៉ុន្តែនេះមិនមែនជាករណីនោះទេ។ ប្រសិនបើការទស្សន៍ទាយរបស់យើងមានលេខក្តៅជាច្រើន នោះយើងប្រមូលព័ត៌មានបន្ថែមអំពីទីតាំងត្រឹមត្រូវ ឬមិនត្រឹមត្រូវនៃលេខក្តៅទាំងនេះ។ យើងនឹងមិនប្រមូលព័ត៌មាននេះទេ ប្រសិនបើការស្មានរបស់យើងភាគច្រើនមានលេខត្រជាក់។
-
តើយើងអនុវត្តគោលការណ៍មួយណានៅពេលដាក់ការទាយដោយលេខក្តៅជាច្រើន?
- គោលការណ៍ 1)លើសពីនេះទៀត ដោយសារតែយើងប្រមូលព័ត៌មានអំពីទីតាំងដែលនឹងមានប្រយោជន៍នៅពេលក្រោយនៅពេលយើងដឹងពីទីតាំងក្តៅទាំងអស់។
-
តើអ្នកអាចគិតពីការបង្កើតការទស្សន៍ទាយដែលអនុវត្តតាមគោលការណ៍ ២) ទេ? ម្យ៉ាងវិញទៀត តើការទស្សន៍ទាយប្រភេទណាដែលផ្តល់ចម្លើយងាយស្រួលប្រើ?
- ដើម្បីធ្វើតាមគោលការណ៍ 2) យើងអាចធ្វើការទាយ ហើយកែប្រែវាដោយយកមួយខ្ទង់ចេញ និយាយថាលេខ 5 ហើយខ្ទង់មួយទៀតនិយាយថាលេខ 3។ ប្រសិនបើការទាយថ្មីមានលេខក្តៅតិច នោះលេខ 5 គឺក្តៅ និង 3 ត្រជាក់។ ប្រសិនបើការទស្សន៍ទាយថ្មីមានខ្ទង់ក្តៅច្រើននោះ 5 គឺត្រជាក់ និង 3 ក្តៅ។ បើមិនដូច្នោះទេ 5 និង 3 គឺក្តៅឬត្រជាក់ទាំងពីរ។ ដើម្បីដោះស្រាយរវាងករណីទាំងពីរនេះ មួយអាចមានទាំងពីរ 5 និង 3 នៅក្នុងការស្មានបន្ទាប់។ នៅពេលសម្រេចថាតើការទស្សន៍ទាយមួយណាត្រូវកែប្រែដោយមួយខ្ទង់ យើងធ្វើតាមការណែនាំមុន ហើយជ្រើសរើសការទាយពីមុនដែលមានខ្ទង់ក្តៅបំផុត ដើម្បីប្រមូលព័ត៌មានអំពីទីតាំង និងអនុវត្តតាមគោលការណ៍ 1).
- យើងសន្មតថាអ្នកធ្វើតាមការណែនាំមុននេះ ហើយដាក់ការស្មានដែលអ្នកគ្រាន់តែប្តូរលេខមួយខ្ទង់គឺជំនួសលេខ 7 ដោយលេខ 3 ហើយអ្នកបានដឹងពីលទ្ធផលថាខ្ទង់ថ្មី 3 គឺក្តៅ និង 7 ត្រជាក់។
-
តើអ្នកបានរៀនពីការស្មាននេះទេ?
- អត់បានរៀនទេ។ ឥឡូវនេះ អ្នកអាចត្រឡប់ទៅការទស្សន៍ទាយមុន ហើយប្រើចំណេះដឹងដែលថា 3 ក្តៅ និង 7 ត្រជាក់ ដើម្បីកាត់យកព័ត៌មានបន្ថែមពីការទស្សន៍ទាយពីមុន។ ឧទាហរណ៍ ការទស្សន៍ទាយពីមុនរួមបញ្ចូលលេខ 3 ហើយមានលេខក្តៅតែមួយ បន្ទាប់មកខ្ទង់ផ្សេងទៀតនៅក្នុងការទាយនោះគឺត្រជាក់។ ការពិតដែលថាពួកគេត្រជាក់អាចផ្តល់ឱ្យអ្នកនូវតម្រុយដែលលេខផ្សេងទៀតក្តៅពីការស្មានផ្សេងទៀតជាដើម។
-
ប្រសិនបើអ្នកសម្រេចចិត្តថាតើលេខមួយណាគួរតែជាលេខក្នុងការទស្សន៍ទាយបន្ទាប់ តើវាសំខាន់ក្នុងការដាក់លេខនោះក្នុងខ្ទង់មួយណា?
- យើងតែងតែចង់ធ្វើតាមគោលការណ៍ ១) និង ២)។ ដរាបណាយើងមិនដឹងថាខ្ទង់ណាក្តៅ ឬមិនស្គាល់ទីតាំងត្រឹមត្រូវនៃខ្ទង់ក្តៅ យើងគួរដាក់លេខនៅខ្ទង់មានទីតាំងផ្សេងៗគ្នា ដូច្នេះហើយប្រមូលព័ត៌មានអំពីទីតាំងដែលនឹងមានប្រយោជន៍នៅពេលក្រោយ។ ក្នុងការធ្វើបែបនេះ យើងធ្វើតាមគោលការណ៍ ១).
នៅពេលដែលយើងដឹងពីខ្ទង់ក្តៅទាំងអស់ យើងក៏ដឹងពីខ្ទង់ត្រជាក់ទាំងអស់ ហើយអាចកាត់ជួររបស់ពួកគេនៅក្នុងតារាងលុបបំបាត់។
ខ) តើយើងអាចស្វែងរកទីតាំងនៃខ្ទង់ក្តៅនីមួយៗដោយរបៀបណា?
-
ឥឡូវយើងដឹងលេខក្តៅទាំងអស់ហើយ តើមតិត្រឡប់អ្វីនឹងមានប្រយោជន៍ខ្លាំង?
- ប្រសិនបើលេខដែលបានទាយទាំងអស់ស្ថិតនៅទីតាំងត្រឹមត្រូវនោះ ពិតណាស់យើងមានសំណាងហើយបានដោះស្រាយបញ្ហា។ លទ្ធផលសំណាងមួយទៀតគឺនៅពេលដែលគ្មាន លេខដែលទាយត្រូវនៅទីតាំងត្រឹមត្រូវ។ បន្ទាប់មក យើងបានរៀនច្រើន ហើយអាចឆ្លងកាត់ទីតាំង N ក្នុងតារាងលុបបំបាត់។
-
រំលឹកឡើងវិញថា តើយើងអាចប្រើតារាងលុបបំបាត់ក្នុងដំណាក់កាលចុងក្រោយនៃដំណោះស្រាយនេះដោយរបៀបណា។
- ប្រសិនបើជួរទាំងអស់នៃខ្ទង់ត្រជាក់ត្រូវបានកាត់ចេញ ហើយប្រសិនបើមានជួរដេក ឬជួរឈរដែលមានខ្ទង់តែមួយដែលមិនត្រូវបានកាត់ចេញនោះ វាប្រាប់យើងថាលេខមួយណាដែលមានទីតាំងនេះនៅក្នុងដំណោះស្រាយ ហើយផ្នែកទំនេរដែលនៅសល់ក្នុងជួរឈរនេះអាចត្រូវបានកាត់ចេញ។ ប្រសិនបើខ្ទង់នីមួយៗអាចកើតឡើងតែម្តងប៉ុណ្ណោះ នោះផ្នែកទាំងអស់នៅក្នុងជួរនេះក៏អាចត្រូវបានកាត់ចេញផងដែរ។
-
តើចំនួនប៉ុន្មានអាចបង្កើតបានពីខ្ទង់ក្តៅ?
- លំដាប់នៃលេខនីមួយៗត្រូវបានគេហៅថាការផ្លាស់ប្តូរ។ ដូច្នេះសំណួរគឺ៖ តើមានចម្លាស់ប៉ុន្មានសម្រាប់វត្ថុ N នៅNខ្ទង់?
- ប្រសិនបើលេខទាំងអស់ខុសគ្នា នោះសម្រាប់ខ្ទង់ទីមួយមានជម្រើស N ។សម្រាប់ខ្ទង់ទីពីរ មានជម្រើស N-1 ។ សម្រាប់ ខ្ទង់ ទី 3 មានជម្រើស N-2 ហើយបន្តបន្ទាប់ទៀត។ បន្សំ N(N-1) នីមួយៗទាំងនេះ សរុប N(N-1)x...x2x1 = N! (ហៅថា N ហ្វាក់ទ័រ) ជាច្រើន។
- ប្រសិនបើមិនមែនលេខទាំងអស់ខុសគ្នាទេ នោះយើងអាចមានឧទាហរណ៍ N=4 ហើយលេខក្តៅទាំង 4 គឺ 2,2,2,5។ បន្ទាប់មកផលិតផល N! = ៤! ត្រូវតែចែកនឹង ៣! ព្រោះលំដាប់រវាងខ្ទង់ទាំងបី 2's មិនមានបញ្ហាទេ។ យើងនឹងទទួលបាន 4!/3! = 24/6 = 4 (ឬល្អជាងនេះ 4!/3! = 4x3! / 3! = 4) ។
-
តើមានចំនួនប៉ុន្មានសម្រាប់ N=3 ឬ N=4?
- បើគិតខ្ទង់នីមួយៗតែម្ដង យើងទទួលបាន ៣! = 3x2x1 = 6 និង 4! = ៤x៣! = 24 ចម្លាស់ (លំដាប់) ។ ទាំងនេះមិនច្រើនទេ។
-
តើការស្វែងរកដំណោះស្រាយនោះមានន័យយ៉ាងណា?
- មនុស្សម្នាក់អាចសរសេរលេខទាំងអស់ (ចម្លាស់នៃ N លេខ«ក្តៅ») ហើយពិនិត្យមើលវាម្តងមួយៗ ទាក់ទងទៅនឹងការទាយមុនទាំងអស់។ ជាធម្មតាមានតែលេខមួយ ឬពីរនៃលេខទាំងនេះនៅតែអាចធ្វើទៅបាន ដែលអាចសាកល្បងតាមការទស្សន៍ទាយបន្ទាប់។
សូមចំណាំ៖ បន្ទាប់ពីការទស្សន៍ទាយ យើងប្រហែលជាដឹងថាដំណោះស្រាយត្រូវតែជាអ្វី ប៉ុន្តែយើងនៅតែត្រូវបញ្ជូនដំណោះស្រាយដើម្បីបញ្ជាក់កុំព្យូទ័រដែលយើងបានរកឃើញវា។
តើគេត្រូវទាយជាមធ្យមប៉ុន្មានដង ប្រសិនបើការណែនាំខាងលើត្រូវបានអនុវត្ត?
- តារាងខាងក្រោមបង្ហាញសម្រាប់ N (ចំនួនខ្ទង់ក្នុងដំណោះស្រាយ) M (ចំនួនខ្ទង់ដែលបានអនុញ្ញាត) ចំនួនមធ្យម G នៃការទាយដែលយើងត្រូវការនៅពេលធ្វើតាមការណែនាំខាងលើ។ តើអ្នកអាចផ្គូរផ្គង ឬកែលម្អវា និងដោះស្រាយបញ្ហាបានលឿនជាងមុនទេ?
| N | M | G |
|---|---|---|
| 3 | 6 | 5 |
| 3 | 9 | 7 |
| 4 | 9 | 6 |
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 |
Singkatan
- Daripada mengatakan digit “sedang berlaku dalam penyelesaian”, kita hanya akan mengatakan digit ini “panas” dan bukannya mengatakan ia “tidak berlaku dalam penyelesaian” kita hanya akan mengatakan ia “sejuk”.
Bagaimanakah seseorang boleh memecahkan keseluruhan soalan kepada sub-matlamat?
- Strategi umum ialah dengan mencari
- A) pertamanya, semua digit panas dan
- B) kemudian, lokasi mereka.
Apakah prinsip yang umum sekali untuk merumuskan tekaan seterusnya?
- Dalam panduan di bawah, kita akan mengikuti dua prinsip dengan mencuba
- 1) memaksimumkan perolehan maklumat dengan setiap tekaan dan
- 2) mendapatkan maklumat yang mudah digunakan.
- Kedua-dua prinsip itu agak bercanggah antara satu sama lain. Sebagai contoh, semakin kurang satu tekaan diubah suai untuk menghantar ke tekaan seterusnya, lebih mudah untuk mentafsir keputusan tetapi lebih banyak tekaan diperlukan. Garis panduan di bawah akan cuba mengikuti kedua-dua prinsip.
Alat yang berguna:
Untuk fasa pertama A) adalah berguna untuk membuat nota semua digit yang mungkin, mengapa?
- Senarai itu akan membolehkan kita padamkan digit sejuk dan menggariskan digit panas.
Untuk fasa B) adalah berguna untuk mempunyai jadual penyingkiran, bagaimana dan mengapa?
- Jika penyelesaian mempunyai N digit dan jika M digit (1,2,……,M) boleh muncul maka adalah berguna untuk melukis jadual penyingkiran (contoh, dengan pensel di atas kertas) dengan N lajur (satu untuk setiap kedudukan dalam penyelesaian.) dan baris M (satu untuk setiap digit yang mungkin). Apabila satu digit diketahui tidak berada pada kedudukan tertentu maka satu kawasan dalam jadual dipadamkan. Sebaliknya, jika digit diketahui berada pada kedudukan tertentu maka semua kawasan lain dalam lajur itu boleh dipadamkan. Dan jika setiap digit boleh berlaku sekali sahaja maka semua kawasan dalam baris itu juga boleh dipadamkan.
A) Bagaimanakah seseorang boleh cuba mencari semua digit panas?
-
Selepas menghantar satu tekaan, hasil (balasan) yang manakah akan sangat berguna?
- Kita bernasib baik jika ternyata semua atau kebanyakan digit yang diteka panas, tetapi kita juga mendapat banyak maklumat jika kedua-dua nombor yang dikembalikan adalah kedua-duanya 0 kerana kemudian tiada satu pun digit yang diteka berlaku dalam penyelesaian, iaitu semua digit yang diteka adalah sejuk. Dalam kes itu, kita boleh memadam N digit daripada senarai kemungkinan digit atau baris N dalam jadual penyingkiran.
-
Jika kita tidak begitu bernasib baik, apakah strategi yang mungkin untuk mencari lebih banyak digit panas?
- Mari kita andaikan bahawa penyelesaian mempunyai 4 digit dan digit 1,…,9 mungkin muncul paling banyak sekali (jika tidak, ubah suai 3 ayat seterusnya). Dengan penyelesaian yang mengandungi 4 digit, kita akan meneka 1,2,3,4 dan kemudian 5,6,7,8 dan secara automatic akan mengetahui tentang 9 dengan mengira berapa digit 1,…,8 panas. Jika terdapat empat digit panas maka 9 adalah sejuk atau panas. Jika kita bernasib baik dan 1,2,3,4 sudah panas maka kita tidak akan mencuba digit lain kerana ia sejuk.
- Mari kita andaikan kita membuat beberapa tekaan, katakan 7, selepas itu kita tahu untuk setiap digit sama ada ia panas atau sejuk.
-
Adakah penting sama ada 7 tekaan ini kebanyakannya mengandungi digit panas atau digit seuk?
- Nampaknya sama berguna untuk meneka dan mengetahui semua digit panas atau meneka semua digit sejuk kerana mengetahui satu set, seseorang tahu set yang lain juga. Tetapi itu tidak berlaku. Jika tekaan kita mengandungi banyak digit panas maka kita mengumpul maklumat tambahan di sebelahnya tentang kedudukan betul atau salah digit panas ini. Kita tidak akan mengumpul maklumat ini jika tekaan kita kebanyakannya mengandungi digit sejuk.
-
Prinsip manakah yang kita ikuti apabila menghantar tekaan dengan banyak digit panas?
- Prinsip 1) kerana di samping itu, kita mengumpul maklumat mengenai lokasi yang akan berguna nanti apabila kita tahu semua lokasi digit panas.
-
Bolehkah anda memikirkan untuk merumuskan tekaan yang mengikut prinsip 2) ? Dalam kata lain, tekaan yang manakah memberikan balasan yang mudah digunakan?
- Untuk mengikut prinsip 2) kita boleh mengambil satu tekaan dan mengubah suainya dengan mengeluarkan satu digit, katakan 5, dan masukkan satu digit, katakan 3. Jika tekaan baharu mempunyai lebih sedikit digit panas maka nombor 5 adalah panas dan nombor 3 adalah sejuk. Jika tekaan baru mempunyai lebih banyak digit panas maka nombor 5 adalah sejuk dan nombor 3 adalah panas. JIka tidak, nombor 5 dan 3 kedua-duanya panas atau kedua-duanya sejuk. Untuk menyelesaikan antara dua kes ini, seseorang boleh mempunyai kedua-duanya, nombor 5 dan 3 dalam tekaan seterusnya. Apabila memutuskan tekaan yang hendak diubah suai dengan satu digit, kita mengikut petunjuk terdahulu dan memilih tekan sebelumnya yang mempunyai digit paling panas untuk mengumpul juga maklumat tentang kedudukan dan mengikut prinsip 1).
- Mari kita andaikan anda mengikuti petunjuk sebelum ini dan menghantarkan tekaan di mana anda hanya menukar satu digit, katakan 7 dengan 3, dan anda mengetahui daripada balasan bahawa digit 3 baharu adalah panas dan 7 adalah sejuk.
-
Itu sahaja yang anda pelajari daripada tekaan ini?
- Tidak. Anda kini boleh kembali kepada tekaan awal dan gunakan pengetahuan bahawa 3 panas dan 7 sejuk untuk membuat kesimpulan lebih banyak maklumat daripada tekaan sebelumnya. Sebagai contoh, tekaan sebelum ini termasuk 3 dan hanya mempunyai satu digit panas kemudian digit lain dalam tekaan itu sejuk. Fakta bahawa mereka sejuk mungkin memberi anda petunjuk yang mana digit-digit lain adalah panas daripada tekaan lain dan sebagainya.
-
Jika anda memutuskan digit mana yang sepatutnya ada dalam tekaan seterusnya, adakah ia peting dalam susunan yang mana untuk meletakkannya?
- Kita sentiasa mahu mengikut prinsip 1) dan 2). Selagi kita tidak tahu digit mana yang panas atau tidak tahu lokasi digit panas yang betul, kita harus meletakkan digit sentiasa pada lokasi yang berbeza dan dengan itu mengumpul maklumat tentang lokasi yang akan berguna nanti. Dalam melakukan ini, kita mengikut prinsip 1).
Sebaik sahaja kita mengetahui semua digit panas, kita juga tahu semua digit sejuk dan boleh memadam barisnya dalam jadual penyingkiran.
B) Bagaimanakah kita boleh mencari lokasi setiap digit panas?
-
Sekarang, setelah kita mengetahui semua digit panas, balasan apakah yang akan menjadi sangat berguna?
- Jika semua digit yang diteka berada pada lokasi yang betul maka, sudah tentu, kita bertuah dan menyelesaikan masalah itu. Satu lagi keputusan bertuah ialah apabila tiada satu pun daripada angka yang diteka berada pada kedudukan yang betul. Kemudian kita belajar banyak dan boleh memadam N kawasan dalam jadual penyingkiran.
-
Ingat balik, bagaimana kita boleh menggunakan jadual penyingkiran dalam peringkat akhir penyelesaian ini?
- Jika semua baris digit dipadamkan dan jika terdapat baris atau lajur dengan hanya satu kawasan yang tidak dipadamkan maka ini memberitahu kita digit mana yang mempunyai lokasi ini dalam penyelesaian dan kawasan kosong yang tinggal dalam lajur ini boleh dipadam. Jika setiap digit boleh berlaku sekali sahaja maka semua kawasan dalam baris ini juga boleh dipadamkan.
-
Berapakah bilangan nombor yang boleh dibentuk daripada digit panas?
- Setiap jujukan digit tersebut dipanggil pilih atur. Jadi persoalannya ialah: Berapa banyak pilih atur yang ada untuk N objek , di sini N digit?
- Jika semua digit berbeza maka untuk digit pertama terdapat N pilihan. Bagi setiap satu daripada N ini terdapat pilihan N-1 untuk digit kedua. Bagu setiap kombinasi N x (N-1)ini terdapat pilihan N-2 untuk digit ke-3 dan seterusnya, dalam jumlah N x (N-1) x … x 2 x 1 = N! (dipanggil N faktorial) banyak.
- Jika tidak semua digit adalah berbeza maka kita boleh mempunyai, sebagai contoh, N=4 dan 4 digit panas ialah 2,2,2,5. Kemudian produk N! = 4! Kena bahagi 3! Kerana susunan antara tiga 2 itu tidak penting. Kita akan mendapat 4!/3! = 24/6 = 4 (atau lebih elegan 4!/3! = 4x3! / 3! = 4)
-
Berapakah bilang itu untuk N=3 atau N=4?
- Jika setiap digit muncul hanya sekali, kita mendapat 3! = 3x2x1=6 dan 4!=4x3! =24 pilih atur (jujukan). Ini tidak banyak.
-
Apakah maksudnya untuk mencari penyelesaian?
- Seseorang boleh menulis semua nombor (permutasi N digit panas) dan menyemaknya satu demi satu berkenaan dengan semua tekaan awal. Biasanya hanya satu atau dua daripada nombor ini kekal mungkin yang mana satu boleh cuba sebagai tekaan seterusnya.
Sila ambil perhatian: Selepas meneka, kita mungkin tahu apakah penyelesaiannya tetapi kitamasih perlu menghantarkan penyelesaian itu untuk membuktikan computer yang kita temui.
Berapa kerap seseorang perlu meneka secara purata jika petunjuk di atas diikuti?
- Jadual dibawah menunjukan untuk N berbeza (bilangan digit dalam penyelesaian), M (bilangan digit yang dibenarkan) purata nombor G tekaan yang kami perlukan semasa mengikuti petunjuk di atas. Bolehkan anda memadankan atau memperbaikinya dan menyelesaikan masalah dengan lebih cepat?
| N | M | G |
|---|---|---|
| 3 | 6 | 5 |
| 3 | 9 | 7 |
| 4 | 9 | 6 |
445339
Follow or subscribe for updates: