Error Detection

  • Thread starter wubie
  • Start date

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

2k + 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 [Broken]

under the section Hamming Distance.


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

Cheers everyone.
 
Last edited by a moderator:

Related Threads for: Error Detection

  • Posted
Replies
1
Views
2K
  • Posted
Replies
1
Views
2K
Replies
16
Views
2K
  • Posted
Replies
1
Views
3K
  • Posted
Replies
5
Views
10K
  • Posted
Replies
4
Views
1K
  • Posted
Replies
3
Views
2K
  • Posted
Replies
1
Views
3K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top