deception, predictions and zero knowledge proofs
Louigi Verona
March 2022
There are even numbers, odd numbers and then there are perfect numbers. What are perfect numbers? Well, this is for you to decide!
In "Perfect Numbers" players come up with a rule or a set of rules that define perfect numbers. Players then write examples of their perfect numbers to each other. One who correctly guesses the rule behind their opponent's numbers first - wins!
Perfect Numbers is a paper and pencil game for 2 players.
Just like with many paper and pencil games, Perfect Numbers is very easy to explain in person, but a bit more challenging to explain in writing. Therefore, do not be intimidated by the length of the rules.
I start out with a quick explanation and an example game. The rest of the sections provide details and further analysis.
A quick explanation
Step 1. Each player comes up with a rule that defines what a perfect number is and writes it down without letting the other player see it. The rule set can be as simple or as complex as you like: "must contain a 3", "all digits should sum up to 20", "first two digits should differ by 2, last two digits by 1", etc.
There are three limitations:
The latter means that a rule should be verifiable from a standalone number, without knowing any of the previous or subsequent numbers.
Step 2. Each player writes three examples of their perfect numbers and provides it to their opponent.
Step 3. Each player looks at the numbers provided and writes down a prediction that they think would be true of their opponent's next example. For instance, "must contain a 3". A player might also choose to write nothing and simply request the next number.
Step 4. If the prediction is incorrect, your opponent must demonstrate it by providing an example of a perfect number that clearly breaks it. For instance, "4759" (doesn't contain a 3). In this case you go back to Step 3 and provide another prediction.
If, however, there is no way to provide a number that breaks the prediction and your opponent returns a number that satisfies it, then you go to Step 5.
Step 5. Now that your prediction was verified, you are given a chance to prove that you know the underlying rule set. You do that by writing three examples of your opponent's perfect numbers. Your opponent then has to check them. If all three guesses satisfy the rule, this is considered as proof that you now know the rule. If, however, there is even a single mistake, you go back to Step 3.
Step 6. But you haven't won just yet! When you correctly guess all the numbers in Step 5, your opponent is given the final chance to take a stab at your numbers and also provide three examples. This is called "the counter". If your opponent makes even a single mistake, you win. However, if they guess all three numbers correctly - they win.
It's very important to keep the counter in mind when coming up with your rule set.
An example game
| Bob | Gary | |
|
136472 456098 340116 |
334260 576639 123003 |
players first provide 3 examples of their numbers |
| has more than 3 digits | contains a 3 | players write their predictions |
| 294 | 804426 | both predictions were shown to be incorrect |
| has to be even | needs to be 6 digits long | players write their predictions again |
| 136072 | 598677 | both predictions were confirmed! |
|
24 ✓ 496 ✗ 836478 ✗ |
748392 ✗ 263430 ✗ 234765 ✗ |
players provide three examples to try to prove they know the rule but none of the players got it right |
| last digit has to be double of the first | needs to have two of the same digits | players write their predictions again |
| 48768 | 325014 | Gary's prediction was confirmed! |
|
48 ✓ 346 ✓ 123452 ✓ |
459812 ✗ 111111 ✓ 375896 ✗ |
Gary got it right Bob tried to counter, but failed Gary won! |
| last digit has to be double of the first |
each pair of digits has to add up to the same result: 235041 -> 2+3=5+0=4+1 |
what the actual rules were |
The game could have gone very differently. Notice the 111111 guess by Bob. If he had gotten that guess in the earlier phase, it might have still prompted him to think this has something to do with having two of the same digits. But during the counter, Bob could have given 222222, 333333, 444444. In this case he would've won.
And this also means that someone could win without even knowing your rule, and, in a way, just hacking it. So, when coming up with a rule you have to be mindful of how someone can consistently get the right result without even knowing the full rule set.
Bob's rule is also not perfect here, since the doubling of the last digit forces each number to be even. The probability that someone would make all the guesses correctly just by knowing this is not high, but it's still an opening Bob's opponent could exploit.
Imagine instead that the rule was "first digit has to be double of the last". In this case, Bob would have full control over whether the number would be even or odd. And he could, in fact, choose to bait his opponent by deliberately making all numbers even, only to then respond with an odd number to the fairly obvious even hypothesis.
More about defining perfect numbers
In the "quick explanation" section I provided a brief colloquial explanation that would totally work in the face to face setting for a first friendly game. However, as people play more, they might need to better understand which definitions would qualify and which would not.
A perfect number can be defined in any way you like, provided you honor these limitations:
The 6-digit limitation is there to make the game more playable. It's easy to wrap your head around 6 digits and it's also possible to count it visually at a glance.
The second limitation is very important to understand and means that your rules should define a single set of numbers.
Example:
The first scenario can be more formally described like this: a number is perfect IF the first two digits add up to 8 AND the last two digits add up to over 8.
The second scenario looks like this: a number is perfect IF the first two digits add up to 8 OR the last two digits add up to over 8.
The "OR" in the second rule set is the problem: you are essentially creating two separate sets of numbers. To put it another way - each rule is going to be true only for a subset of perfect numbers.
Additional reading ▼
In case you're interested why defining perfect numbers as more than one set cannot be allowed: this is done to prevent what I call "arbitrary sets".
Imagine that you can use an "OR" in your rules. In other words, you can define several sets. In this case, nothing prevents you from defining your perfect numbers as an arbitrary set of specific integers, say, 1, 2, 3, 49, 194, 1234, 3546, 3547, 4001, 5020, 5022, 6507, 7890, 7895, 8001 and 8009. This gives you enough mileage to last through the normal length of the game, while keeping you pretty much immune from both a successful prediction and the counter. This would basically be the winning strategy, making the game pretty much unplayable.
Of course, one way to ensure that this doesn't happen is to limit the amount of "OR" clauses you can have. But this would be a bad game design decision. If players are allowed, say, one OR clause or, to put it another way, they are allowed to define essentially two sets of perfect numbers, the winning strategy would be to always define two sets. But all that would do is simply prolong the game, making figuring out the rules longer and more tedious, while adding essentially no value: your opponent would have to identify just a single set in order to win anyway.
There are many ways to explain this limitation, like through the "OR" clause like I did just now. But I am glad I found more colloquial wording - that each rule should be true for all numbers. Which essentially does the same, without appealing to algorithms and logical operators.
Although this limitation seems to be pretty sweeping, in reality I found it to be adding a lot to the game. It forces players to be clever and come up with truly devious rules that are not at all easy to zero in on.
The third limitation means that whether a given number is a perfect number or not should be clear just by seeing that number alone.
Some examples:
Additional reading ▼
In case you're interested why I decided to exclude sequences: not only would they require a ton of iterations, but sequences can be incredibly intricate and almost impossible to solve. Sequences are just very bad at giving away information about their underlying principle.
Here's an illustrative example: 0, 0, 0, 1, 0, 1, 1, 2, 1, 3, 2...
The first 7 elements are just a collection of apparently random 0s and 1s. And the solution to this sequence is that this is the number of triangles with integer sides and perimeter n.
In other words, the underlying principles can be so complicated and arbitrary, that there is almost no way to formulate a hypothesis in a game setting that would shed light on how the sequence was formed.
Sequences also immediately move the game out of the realm of casual players.
More about making predictions
While making predictions does not seem to require much limitations, in reality there are a couple of things that are fairly common sense, but would benefit from being clearly defined:
The first point means that you cannot do things like "consists of some amount of digits", where it's clear that regardless of what the principle behind your opponent's numbers is, they would have to basically respond with a "yes" and award you three guesses.
So, whatever your prediction is, there must potentially be a number that won't satisfy it.
The second point is the mirror image of the rule set limitation when defining perfect numbers. Without such a limitation one would be able to do things like "contains 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9" and almost always get free guesses. It's also conceptually problematic, since without such a limitation one could in principle construct what would amount to an endless string of hypotheses, separated by "or".
Tips and strategy
There are several interconnected elements: creating a rule set, the opening move, providing perfect numbers, guessing your opponent's rule set and the counter.
When creating a rule set, you should carefully balance how many numbers you exclude with how many numbers are available.
Think of it this way - the more rules you impose, the less numbers are going to be available to you. Less available numbers means clearer patterns for your opponent to notice. On the other hand, loose rules mean more numbers available not only to you, but also to your opponent. Even if they are not able to zero in on a successful prediction, they can win by simply providing random numbers during the counter.
This is why the counter is so important to the game. Imagine, Bob comes up with this sneaky rule: "a perfect number is any number that is larger than 5."
This rule seems perfect: it allows Bob to evade almost any prediction. Even if it's something like "has to be more than 1 digit", Bob can falsify it with 6, 7, 8 or 9. But the problem is that once Bob arrives at Gary's rule, Gary will do the counter and win with high probability by just writing down three random numbers.
Therefore, there is no need to prohibit rules like these. Instead, the structure of the game incentivizes players to find a balance between rules that are too restrictive and rules that are too permissive.
It is also for this reason that the definition "a perfect number is any number" does not need to be prohibited. A player picking such a definition is guaranteed to lose.
Another thing to consider is how exposed the rule set will make you. Each time you provide your perfect number, you are giving up information. Make sure that you are able to wield enough control to not give away your rules too quickly. A good illustration of this is Bob's rule from the example game: "last digit has to be double of the first". This forces every perfect number to be even.
The reason it's bad is because it provides an opening for Bob's opponent to file a fairly obvious prediction. And a successful prediction means forcing Bob to divulge quite a bit of information, since Gary is now awarded three guesses that Bob must verify. And three numbers is a lot, especially since Gary is going to try to learn as much as possible with these three guesses.
In fact, the game is not only about numbers. It has a great deal of psychology to it. Which numbers you expose to your opponent can be critical to how quickly they catch on to your rule set.
"Baiting" is one trick you can use. This is when you create a misleading pattern, prompting your opponent to file a prediction that you know will be wrong, thus buying yourself time. Of course, your opponent might know this, but you might also know that they know.
Even a very simple rule can be coaxed in layers of deception. Take this transcript:
|
123210 535240 246360 |
| contains a 2 |
| 893680 |
| contains a 3 |
| 444440 |
| contains a 0 |
| 137247 |
| contains 2 of the same digits |
| 678531 |
The rule here is very clever: "n-1 should contain a 3". But it's been made very difficult to get to by creating several false patterns. Obviously, this is just an example and an experienced player might see through it and try something very different, but, nevertheless, great care should be taken when presenting perfect numbers to your opponent.
When given a chance to present your own guesses for the first time, try to use the opportunity to not only confirm your existing hypothesis, which might actually be wrong or incomplete, but also try very different things. Trying very short numbers or unusual numbers, like 24 or 222333 could be surprisingly helpful.
A reference of miscellaneous rules
Many games have rules that seem so obvious that they remain unwritten. But it's good to be able to have a reference where all such rules could be looked up if a question does come up. I also spell out some of the rules that were only mentioned in passing.