A substitute teacher lead a groop of students to go for a trip. The teacher who in charge of the groop of the students told the substitude teacher that there are two students who always lie, and the others always tell the truth. But the substitude teacher don't know who are the two students always lie. They get lost in a forest. Finally the are in a crossroad which has four roads. The substitute teacher knows that their camp is on one road, and the distence is $20$ minutes' walk. The students have to go to the camp before it gets dark. $(1)$ If there are $8$ students, and $60$ minutes before it gets dark, give a plan that all students can get back to the camp. $(2)$ If there are $4$ students, and $100$ minutes before it gets dark, is there a plan that all students can get back to the camp?
Problem
Source: 2016 China South East Mathematical Olympiad Grade 11 Problem 4
Tags: combinatorics, China Southeast MO, Interesting problem
21.11.2016 17:06
Do the students also lie when the teacher know they are lying? Because then for (2), the teacher can first walk with one of the students, and after coming back the substitute teacher hears whether this child lies about whether they have found the camp, but this seems a very silly solution.
21.11.2016 17:47
Eva17 wrote: Do the students also lie when the teacher know they are lying? Because then for (2), the teacher can first walk with one of the students, and after coming back the substitute teacher hears whether this child lies about whether they have found the camp, but this seems a very silly solution. Ah, but if they didn't find the camp, it's not exactly aan immediate solution to know if that child is a liar - the group must still find the camp!
21.11.2016 17:58
My solution for a) is to split the children into groups of 3/3/2. Send them down a path each, and have the sub go down the 4th. If the liars are together, it's easily noticeable - either all 3 are unanimous, or exactly 1 of the trios will be split 1/2. If they're split, either both of the trios will be split 1/2 (and the liars are outnumbered), or one of the trios is split and the pair is split. Since all 4 cases are disjoint, regardless of exactly which path has the camp, the teacher should be able to determine which of the 3 paths has the camp, if they hadn't already stumbled upon it themselves. For part b), I think it's a little too loose there, since it's easy to just send all the children along with the teacher down one path, then determine which are the liars from that, then split them up down a path each. Of course, this is assuming 'did you find the camp?' Is the only acceptable question. If the sub can ask 'is the sky blue?', the question becomes even simpler.
26.04.2022 12:12