How Many Questions to Determine Coin Positions with Permitted Lies?

[wubie]

[SOLVED] Error Detection

Hello,

I have a question about error detection.

Senario:

One person can see two coins. Each coin could be laying heads up or tails up. You cannot see the coins.

Question:

What is the minimum number of questions with a "yes" or "no" response need to determine the status of two coins (that is whether they lie heads up or tails up) if two lies are permitted. All questions are tabled before any answers are given, and no hypothetical questions are allowed.


I quickly came up with one way of determining the status of the two coins:

Ask this question FIVE times about the first coin:

"Is the first coin heads up?"

Then ask this question FIVE times about the second coin:

"Is the second coin tails up?"

By taking a majority decision, one could deduce the status of the two coins. But is there a better way?

In class we have been talking about Hamming Distances. But I can't figure out how I would set this question up with regards to Hamming Distance.


Any help is appreciated.

 

[wubie]

Alright. I found out some key information that I was not aware of to solve this question.

The number of code words is equal to the number of outcomes.

The possible number of outcomes for two coins are:

Heads-Heads, Heads-Tails, Tails-Heads, Tails-Tails.

There are four outcomes and so I need four code words.


Also, if I need to correct two errors, then the Hamming Distance between codewords must be at least

2^k + 1

Therefore since there are two lies, I must have a minimum Hamming Distance of 5 between codewords.

Now I know that using ten questions I could determine the status of both coins. So, once again, the question is, "Can I do better than ten questions?"



For more nfo. on Hamming Distances as well as the course that I am taking go to:

http://www.math.uAlberta.ca/~tlewis/222_03f/scarlet2.pdf

under the section Hamming Distance.


I am still working on this question so I will post my answer later.

Cheers everyone.