Proofs in Computer Science (Optional) · Interactive Proofs
Lesson 3
Most often, the following solution is proposed. You take two bottles of wine, pour two glasses, and place them on the table (the glasses look identical, of course). You let your friend taste the wine from the first glass, then ask him to turn away and randomly swap the glasses (for example, flip a coin and swap the glasses if it lands heads). Now the first glass contains a random wine from the two varieties. You ask your friend to taste the wine from the first glass again and tell you whether it is the same variety he tasted initially or not. If your friend is indeed knowledgeable, he will easily answer. If he is not, he will guess with a probability of \(1/2\). If you repeat this experiment \(k\) times, the probability that your friend guesses correctly every time will be \(1/2^{k}\).