• Support PF! Buy your school textbooks, materials and every day products Here!

Error Detection and Correction

  • Thread starter wubie
  • Start date
  • #1
wubie
Hello,

First I will post my question. I think it might be easier if I do this.

There is a group of campers and one counsellor. They are making their way to their camp site when they arrive at a crossroad. There are four different paths they can take. They have only 100 minutes until dark to find the proper path which will take them all to the campsite. A trip down a path takes 20 minutes. Therefore the campers and the counsellor are allowed two round trips to determine which path takes them to the campsite. Now this would not be a problem. However, three of the campers in the group lie sometimes. And the counsellor does not know which campers lie. How many campers must the counsellor have in this group to determine which path to take given that three of the campers lie sometimes.

Now I figure that the counsellor can take two of the four paths to determine if the campsite is down either of them. However, he still must depend on the campers to find out whether the remaining two paths lead to the campsite should the counsellor not find the campsite him/herself.

Now given that three of the campers lie, and there are two remaining paths, how many campers would the counsellor need to determine the proper path to take should the campsite not be down the paths the counsellor takes.

I would think that if the counsellor sent seven campers (three of which could lie) down one path one trip and the same seven campers again down the other path, then the counsellor could take the majority decision and determine what path to take.

Is there any way that I can optimize this answer? That is, is there any way that I can use less campers than seven?

I can't think of any other way given three campers that lie.


Any help would be appreciated.

Thankyou.
 

Answers and Replies

Related Threads on Error Detection and Correction

  • Last Post
Replies
3
Views
551
  • Last Post
Replies
4
Views
602
Replies
10
Views
390
  • Last Post
Replies
7
Views
47K
  • Last Post
Replies
4
Views
1K
Replies
8
Views
2K
  • Last Post
Replies
14
Views
118
  • Last Post
Replies
4
Views
923
Top