[SOLVED] Error Detection


by wubie
Tags: detection, error, solved
wubie
#1
Oct5-03, 07:34 PM
P: n/a
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.
Phys.Org News Partner Mathematics news on Phys.org
Math modeling handbook now available
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
wubie
#2
Oct7-03, 02:28 PM
P: n/a
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/...f/scarlet2.pdf

under the section Hamming Distance.


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

Cheers everyone.


Register to reply

Related Discussions
[SOLVED] Momentum-space detection of an Electron (EWP) Quantum Physics 1
cmput: 2D parity error detection scheme Engineering, Comp Sci, & Technology Homework 1
Transmission Error Detection General Math 1
Probability Question about Error Detection Engineering, Comp Sci, & Technology Homework 7
Error Detection and Correction Introductory Physics Homework 0