Error Detection

In summary, the conversation revolves around finding the minimum number of questions needed to determine the status of two coins (heads up or tails up) if two lies are allowed. The initial suggestion is to ask five questions about each coin and take a majority decision, but the question is whether there is a better way using Hamming Distances. Further information is provided, including the number of possible outcomes and the minimum Hamming Distance needed for two errors. It is mentioned that ten questions can solve the problem, but the question remains if this can be improved. The conversation ends with a link to more information on Hamming Distances and the promise to post an answer later.
  • #1
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.
 
Mathematics news on Phys.org
  • #2
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:
  • #3



Hello,

Thank you for your question. In this scenario, the minimum number of questions needed to determine the status of two coins is six. Here's how:

First, ask the following question about the first coin:

"Is the first coin heads up?"

If the answer is yes, then the first coin is heads up. If the answer is no, then the first coin is tails up.

Next, ask the following question about the second coin:

"Is the second coin heads up?"

If the answer is yes, then the second coin is heads up. If the answer is no, then the second coin is tails up.

If the answers to both questions are the same (both heads up or both tails up), then you have determined the status of both coins with just two questions. However, if the answers are different, then you need to ask one more question to determine the status of the second coin. So the minimum number of questions needed is three.

But since you are allowed to ask two lies, you can ask the same question again about the second coin, giving you a total of six questions. This way, you can take a majority decision based on the answers and determine the status of both coins accurately.

I hope this helps! As for using Hamming Distance, it is a measure of the number of positions at which two strings of binary symbols differ. In this scenario, it would not be applicable as we are dealing with coins that can have either heads or tails, not binary symbols. Let me know if you have any further questions.
 

What is error detection?

Error detection is the process of identifying and correcting errors or mistakes in data or information. It is an important aspect of scientific research and ensures that accurate and reliable results are obtained.

Why is error detection important in scientific research?

Error detection is important in scientific research because it helps to ensure the accuracy and reliability of results. This is crucial in order to draw valid conclusions and make informed decisions based on the research findings.

What are some common methods used for error detection?

Some common methods used for error detection include statistical analysis, data validation and verification, and comparison of results with previous studies or known values. Other techniques such as hypothesis testing and peer review can also help to identify potential errors.

How can errors be prevented in scientific research?

Errors can be prevented by carefully designing experiments and procedures, using reliable and calibrated equipment, maintaining accurate records, and following standard protocols. Regular checks and reviews by other researchers can also help to identify and prevent errors.

What are the consequences of not detecting errors in scientific research?

The consequences of not detecting errors in scientific research can be significant. It can lead to incorrect conclusions, wasted time and resources, and even harm to individuals or the environment if the research is used to inform decisions or policies. Therefore, error detection is crucial in maintaining the integrity and credibility of scientific research.

Similar threads

  • Set Theory, Logic, Probability, Statistics
2
Replies
57
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
4
Replies
126
Views
6K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
1K
  • Set Theory, Logic, Probability, Statistics
2
Replies
45
Views
3K
  • Quantum Interpretations and Foundations
Replies
2
Views
911
Replies
1
Views
2K
  • General Math
Replies
14
Views
3K
Replies
1
Views
828
Replies
14
Views
6K
Back
Top