Learn / Library / Brainteasers

Triple-neighbourhood claims

BrainteasersHard

$12$ sensors are fixed around a circular fence. Each sensor is reliable (a truth-teller) or broken (a liar). Every sensor reports: "Among me and my $2$ neighbours there is exactly one broken sensor." In how many different ways can the types be assigned to the labelled positions so that all $12$ reports are consistent?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Find which patterns of seats around any person make his statement true, and check what that forces for truth-tellers and liars.

Solution

A truth-teller needs exactly one liar among himself and his neighbours, and a liar needs a number of liars in his triple that is not $1$ ; a lone truth-teller between liars has $2$ liars in his triple, and $3$ truth-tellers in a row give the middle one $0$ , so truth-tellers occur only in adjacent pairs.
A single liar between $2$ truth-tellers would see exactly $1$ liar (himself), which is not allowed, so between consecutive pairs of truth-tellers there are at least $2$ liars, and the case of no truth-tellers at all (all liars) is consistent.
With $k$ pairs, each followed by a gap of at least $2$ liars, the extra liars beyond $2$ per gap total $12 - 4 k$ and can be shared out in $(k - 1 11 - 3 k)$ ways, and placing the pattern on $12$ labelled seats gives $12 \times \frac{( k - 1 11 - 3 k )}{k}$ arrangements.
This gives $12$ , $30$ and $4$ for $k = 1$ , $2$ , $3$ , and $1$ for $k = 0$ , so the total is $1 + 12 + 30 + 4 = 47$ .

Answer: $47$

Next question Back to the library