Two secret numbers

Question

I have two identical pieces of paper. On each piece of paper I write down a number, either 1 or 2. I do not show or tell the numbers to anyone. My writing is always the same - if I write the same number twice then it will look identical both times. I tell you that the sum of the numbers is even. How can I prove it to you beyond reasonable doubt that my statement is true without showing or telling you the actual numbers?

Bonus: Could I still prove it to you if the numbers I wrote down were 1, 2 or 3?

Hint for bonus question:

I can get more pieces of paper and I can write numbers on them that are identical to the original. I can also show you what I wrote down this time.

Answer 1

Here is a clean solution assuming the following. (I'm not claiming originality; elements of this are already in other answers.)

Dmitry can be trusted in

• that he wrote 1 or 2 on the two sheets
• that he is incapable of writing two copies of either 1 or 2 that he himself would be able to distinguish

Apart from that he is a competent liar and cannot be trusted on anything.

Further assumption: There is a way Dmitry can shuffle a given set of sheets without any chance of tampering with them.

Then he can prove without disclosing any information whatsoever that the two original numbers are identical by:

1. Writing openly a 1 and a 2 on two more sheets. Call this the new pair, and the original one original pair.

2. Flipping the two new sheets over and shuffling them before passing then to us so we know they are 1 and 2 but not which is which. (Without this step Dmitry would disclose additional information because if we knew which was which we would be able to infer whether the original pair was two 1s or two 2s later.)

3. Allowing us to repeatedly select one of the four sheets at random (without looking at what is written on it but keeping track of which pair it was from) and let him see the number.

4. Accepting his claim if he manages to guess significantly above chance (50%) level which pair the number comes from.

Note that this does not require us to trust Dmitry. It only requires that Dmitry wants to convince us.

Why this works

If the sum is not even, the original pair will contain 1 and 2, so we have two 1's and two 2's in the four sheets. So if Dmitry lied, he couldn't have got above chance level (50%) to guess which pair the sheet we picked come from. Only when the sum is even will Dmitry be able to guess above chance level, by guessing "original" if the number is the same as the two original number, and guessing "new" if the number is different. This way Dmitry will make a correct guess 75% of the time.

Variation:

Instead of step 3 and 4 above, we could also do:

3' Randomly select a pair (either original or new) and let Dmitry see both numbers, and guess whether it's the original pair or the new pair. Repeat.

4' Accept his claim if he guesses correctly 100% of the time.

Generalisation:

Dmitry claims something, which basically means he is choosing a subset of all possible outcomes. We let him openly produce all other outcomes, which we verify. Then shuffle them and pass them to us in an opaque (think face down) state.

If he now is able to tell with 100% accuracy whether a randomly selected outcome is the original submission or not he must be telling the truth.

Answer 2

My answer is wrong and here is why.

First, let me refer to ZKP wikipedia https://en.wikipedia.org/wiki/Zero-knowledge_proof (Two balls and the colour-blind friend), and to Computer Science exchange https://cs.stackexchange.com/questions/150548 (How can you convince your colour-blind friend that two balls have the same colour?), and let me thank @MichaelS (and others) who opened my eyes. Dmitry Kamenetsky's nice question boils down to: we know a ZKP for different colors (or odd sum) exists. Does one also exist for same colors (or even sum)? Note that P can look at the numbers and V not. In case of the colors, V can look as well, but it does not help ... V is color-blind. In such ZKP example you (P) claim to know statement S is true and a protocol must be designed which proves me (V), not trusting you, that S indeed is true. There are two aspects I missed: 'claim' and 'trust'. Also, it is neither the case that V must design the protocol to unveil potential lies from P, nor it is the case that P must design the protocol because P wants to convince V about S. Rather: this sort of scenarios often have cryptography as motivation and it's only a matter of designing protocols where parties that should not trust one another can exchange information without giving anything away to everyone. My answer depends on V trusting P but that's exactly what must not be so: P may not be trustworthy and still V needs to be proven S is true. My proof only proves to V that P claims S is true, but, if P can be trusted, V might as well ask about S directly or believe the claim in the first place! The flaw lies in the case when P lied to V about S. That is: S is false. Then my protocol does not work. Because P might as well toss a coin and answer 'swap' for head and 'no swap' for tail. He might do so for S is true as well, that's OK, but for S is false (same colors, or, odd sum) then P leaves V with no proof (S could be true or false). Otherwise stated: my (wrong) protocol is complete but not sound.

Please do not let my comments depending on the flaw confuse you...

(wrong) answer to 'case $1$ $2$' version:

could be $0$ and $1$ too

Let's follow a classical ZKP protocol: you close your eyes and, each time, I either swap the (identical sized, with number hidden) papers or not. Each time, I then allow you to look at one and you must guess and tell me (as perfect thinker who is wanting to prove me something), to your best effort, if I swapped or not. You are not able to conclude correctly if sum is even (both numbers same) so you will eventually give some wrong answers. But if sum is odd you can always conclude correctly and you will give 100% correct answers. So if you do not keep on answering correctly such proves sum is even without extra information being leaked. In fact, any other (passive) spectator does not get anything extra revealed either.

Answer 3

I would like to ask for clasrification but I can't ask in a comment due to reputation. I assume that you can show the actual numbers as long as I can't know what you originally wrote. Otherwise this seems fairly impossible as anything you show me is created independently of the original numbers and so doesn't need to relate to them.

Assuming that here is my solution to the first puzzle.

Clearly you have either written $(1,1)$ or $(2,2)$. Now write on $2$ new pieces of paper the other number. Put these pairs of numbers into $2$ seperate envelopes. Shuffle the envelopes and then give them to me. Now I can open each envelope and see that they contain $(1,1)$ and $(2,2)$. This could only be true if the original numbers sum is even, but additionally I know nothing about the original numbers other than that.

Edit: There is also a simple extension for any property of any collection of numbers.

Simply repeat the same idea but instead write all the possible options that satisfy the property and place these into envelopes. Exactly the same argument shows that this proves you were telling the truth and tells me nothing more. (Although it is propably suboptimal as a solution)

As a note, the reason that this isn't like a zero knowledge proof is that you technically do give me information about what you have written, but only in the sense that you tell me what the options are for things which sum to even values. i.e. it is information which doesn't help me identify what you wrote.

Answer 4

By showing me their respective last digits.

Answer 5

You tell me that you wrote the same number on both pieces.

Answer 6

This problem reduces to "How can I prove to you that I wrote the same number on both pieces?"
If I also assume that you write consistently in form, size, and location, then you can

measure various physical properties of the paper, like weight, moments, and so forth. Since the pieces are stated to be identical, the only way the measurements could differ is if you added different markings to the paper, and multiple identical measurements would be very suggestive (but not definitive proof) of identical numbers.

Answer 7

For the sum to be even, both numbers have to be 1 or both numbers have to be 2. So

Write the numbers in seven segment display, and overlay the paper. By shining a light through the paper, you will observe either:

1 + 1 = 1
1 + 2 or 2 + 1 = backwards 6
2 + 2 = 2

So if the shadow is 1 or 2, the sum is even as the numbers are the same

Bonus:

This also works for 1, 2 and 3, we now also have 1+3 = 3 and 3+3 = 3, and for odds, 2 + 3 = backwards 6

So as long as the shadow is not a backwards 6, the sum is even

Answer 8

My answer is wrong please refer to explanation in answer 'case 1 2'

As for the bonus:

It needs a slightly more complex protocol. But the same idea remains: somehow I (verifier, spectator) must, following your protocol instructions, repeatedly interact with you to convince myself mathematically that you know something about the two initial numbers (the fact they are even). The protocol involves that each step I do something you do not 'see' (hence you do not know) but you can guess. The probabilities that you (prover, performer), acting logically and cooperative (since you want to prove me something), can guess what I did each step must, no matter what your initial numbers are, be such that, if sum were odd, you can always guess right, and if sum were even, you can't. Then, if you do not always answer correctly, sum must be even, without leaking information.

So now for the 'case $1$ $2$ $3$'. I do not have a general protocol for the 'case $1$ $...$ $N$' let alone for any integer. Perhaps such protocol exists and Dmitry Kamenetsky could let us know about it (in case one exists and if he knows it).

Here we go

You could (if allowed) add another extra identical paper and write a number on it. You choose the number not random but as follows: if original sum is even, you choose left number from pair, and, if original sum is odd, you choose number not in pair. So this time we take advantage of a property of all odd sums of pairs. Then you place the extra paper in between the original pair. You would explain me your strategy (but you do not show any number). Now, each step in the protocol, just like in 'case $1$ $2$', I am allowed, while you close your eyes, to swap, this time: either left or right one, with middle one. You must then inspect middle one and mathematically guess if there was a swap or not.

As it turns out for this particular choice (see overview below): In case original sum was odd, you can guess correctly with probability PO $1$ (i.e.: always) and, in case original sum was even, you can guess correctly with probability PE $\frac{1}{2}$ (in $\frac{3}{5}$th of the cases) and PE $\frac{2}{3}$ (in $\frac{2}{5}$th of the cases). The required ingredient (you can always answer correct if sum is odd) is present, and, so I can know what you know (that the sum is even). The $\frac{2}{3}$ is high but still less than $1$. It accounts for the pairs $(1,3)$ and $(3,1)$ that make simple protocol fail.

epilogue

I see two potential objections: (1) "is it allowed to bring in a third object into the guessing?", and (2) "does this protocol reveal any information?". I will not address (1). About (2): will it, in case you had $(1,3)$ or $(3,1)$, not suggest such to be the case (and reveal the numbers, not the order) because probability to guess correctly can be two times higher in that case (and expected number of guesses before first wrong one as well) than in all other even sum choices? Well, since only a single wrong answer is sufficient, even if it took a bit long, there is no 100% certain conclusion I can draw from what happened. Not sure if statistical information is counted and when it is relevant. The relevant sigma can be calculated but I don't do this here.

Here is overview of situations showing PO PE

 ====
 11
 e
 m 1
111
e 0.5 111 <- no swap
 e 0.5 111 <- swap  l
 e 0.5 111 <- swap  r
PE 1/2
====
 12
 o
 m 3
132
o 1.0 132 <- no swap
 o 1.0 312 <- swap  l
 o 1.0 123 <- swap  r
PO 1
====
 13
 e
 m 1
113
e 0.5 113 <- no swap
 e 0.5 113 <- swap  l
 e 1.0 131 <- swap  r
PE 2/3
====
 21
 o
 m 3
231
o 1.0 231 <- no swap
 o 1.0 321 <- swap  l
 o 1.0 213 <- swap  r
PO 1
====
 22
 e
 m 2
222
e 0.5 222 <- no swap
 e 0.5 222 <- swap  l
 e 0.5 222 <- swap  r
PE 1/2
====
 23
 o
 m 1
213
o 1.0 213 <- no swap
 o 1.0 123 <- swap  l
 o 1.0 231 <- swap  r
PO 1
====
 31
 e
 m 3
331
e 0.5 331 <- no swap
 e 0.5 331 <- swap  l
 e 1.0 313 <- swap  r
PE 2/3
====
 32
 o
 m 1
312
o 1.0 312 <- no swap
 o 1.0 132 <- swap  l
 o 1.0 321 <- swap  r
PO 1
====
 33
 e
 m 3
333
e 0.5 333 <- no swap
 e 0.5 333 <- swap  l
 e 0.5 333 <- swap  r
PE 1/2
 

Answer 9

Solution:

Leverage the fact that the op stated:

I do not show or tell the numbers to anyone

instead of

I do not show or tell the numbers to anything

To start, I have op write a 1 on one extra sheet of paper, and a 2 on another, showing me both.
I scan these into a computer using a scanner and write a program that leverages numerical OCR and math to convert the images into two numbers and output "E" if their sum is even, else "O" if their sum is odd. I tweak as needed to account for any idiosyncrasies with respect to the op's handwriting.
I test the program and verify it works.

I now have the op get two identical pieces of paper. On each piece of paper the op writes down a number, either 1 or 2, without showing me. When done, I take the papers and, without looking at them, scan them and run the program I created. When it outputs E or O, I am convinced beyond reasonable doubt as to whether the op's statement regarding the sum of the numbers is true or false. This leverages the assumption that for the op, "My writing is always the same - if I write the same number twice then it will look identical both times".

Bonus question: Same solution, but test the software with OCR on "3"'s.

Note: for the 1/2 basic case, this is also solvable with

very heavy ink and an extremely precise balance scale.

Answer 10

In keeping with my answer to your Computer Science question, here's an answer that only involves 3 sheets of paper and doesn't involve showing me any numbers for the two-possibility case. I can't come up with a good answer for the three-possibility case, but I've given an answer that's not completely bad.

We have to assume you can't write anything on a paper except the allowed numbers (1, 2, and possibly 3), and any paper with a given number is indistinguishable from other papers with the same number.

Two Possibilities (1, 2)

The numbers 1 and 2 can be substituted for any other integers provided one is even and one is odd.

For the sum to be even, the two papers must contain the same number. So the proof is simply that the papers match: either both are 1, or both are 2.

So you write a number on a third sheet of paper that isn't the first number. If the existing sheets are both 1, the third sheet is 2. Otherwise the third sheet is 1.

Now, you prove the third sheet doesn't match the first sheet. You hand me both sheets. I ensure I never lose track of which is which, but I hide them from you so you can't tell while shuffling.

I show you (and only you) both sheets. You now know which is on the left and right. I hide them from you, and either leave them in place, or switch them left to right, randomly. I again show you each sheet, so you can tell left from right. You tell me whether I switched them or left them the same.

If you can consistently tell when I switched them or didn't, I know they're different. Otherwise, the test fails.

Since I kept track of when I switched them, I know which one is the third sheet. I place the first sheet to the side, then take the second sheet. I repeat the test to prove you know which is the second sheet and which is the third.

If you can consistently tell me which is the second and which is the third sheet, I know they're different. Since you were only allowed to write one of two numbers, and neither of the first two sheets matches the third, the first two sheets must match each other.

Three Possibilities (1, 2, 3)

We can substitute 1, 2, and 3 with any other integers provided two are odd and one is even.

Unfortunately, my answer to the Computer Science question won't completely work here.

That answer only shows the two numbers match. Here, it's also acceptable if the numbers are 1 and 3. So we have to prove neither of the papers has the number 2, or both have the same number.

First, we can simply test using the above method.

You give me four papers, $P_1, P_2, P_3, P_4$. The papers $P_2, P_3, P_4$ must have the numbers 1, 2, and 3, but I don't know which is which. $P_1$ + $P_2$ is claimed to be even.

Using the standard method, I prove that each pair of papers in [$P_2, P_3, P_4$] is different. I test you with $P_2\neq P_3$, $P_2\neq P_4$, and $P_3\neq P_4$. This ensures you have one of each number.

Now, I prove that $P_1$ is neither $P_3$ nor $P_4$ using the standard method, which tells me $P_1$ must be $P_2$.

If this proof succeeds, we're done. The result is guaranteed to be even. However, failure here isn't a total failure since there were multiple ways the result could be even.

Sadly, there's no way to find the answer without giving away some extra information.

If the two numbers don't match, any test proving the sum is even automatically tells us the numbers are 1 and 3.

You can write the number 2 on a paper, $P_5$, then use the standard method to prove that neither $P_1$ nor $P_2$ matches $P_5$. This proves that both are 1, both are 3, they're 1 and 3, or they're 3 and 1.

This never tells us the exact value of either paper, but I don't really like it, given the spirit of "zero information" protocols. I'd prefer a method that never distinguishes between

matching papers and papers aren't 2

but I can't think of such a method.

Real World (Lack of) Applicability

I'm unable to come up with any scenario where these "proofs" really work. As a puzzle, we can magic away some of the rules and that's fine. But it doesn't work in a practical setting.

The original test, that two objects are definitely different, is clear-cut. I can't tell two things apart, but you can. That's potentially useful, and is immediately convincing.

In this test, I require proof that you can't cheat. It would be trivial to make a small mark on one paper, or write the number in way you can see the difference but I can't, or just write completely different numbers than agreed upon. Since I'm not allowed to examine the papers, I have no way of showing that it's even likely you can't cheat.

So I'm required to either take your word for it, in which case I can just skip the entire test. Or take the word of a trustworthy third-party, in which case I can just have them verify on my behalf.

It might work as a magic trick of some kind. Use cards from brand-new card decks, and have an audience member verify the cards aren't tampered with. But magicians can easily acquire trick decks that are sealed, so that's not really convincing. And your average audience member isn't going to have to logical aptitude to be any more convinced by this proof than you just claiming you're right.