Problem 30 · 2017 Math Kangaroo
Stretch
Logic & Word Problems
casework
2017 people live on an island. Each person is either a liar (who always lies) or a nobleman (who always tells the truth). Over a thousand of them attend a banquet where they all sit together around one big round table. Everyone says, “Of my two neighbours, one is a liar and one is a nobleman.” What is the maximum number of noblemen on the island?
Show answer
Answer: A — 1683
Show hints
Hint 1 of 2
The banquet statement constrains only the people seated at the round table; the others on the island are free.
Still stuck? Show hint 2 →
Hint 2 of 2
Work out the densest valid liar/nobleman pattern around the table, then add the unseated islanders.
Show solution
Approach: maximise noblemen given the round-table constraint plus free islanders
- A seated nobleman truly has one liar neighbour, so two noblemen can sit together but never three in a row; a seated liar lies, so its two neighbours match (both noblemen or both liars).
- The densest legal seating repeats the block nobleman-nobleman-liar, making at most \(\frac{2}{3}\) of the seated people noblemen, so a table of \(n\) (a multiple of 3) seats up to \(\frac{2n}{3}\) noblemen.
- Everyone not at the banquet can be a nobleman, so the island total is \((2017-n) + \frac{2n}{3} = 2017 - \frac{n}{3}\), maximised by the smallest legal \(n\) over a thousand, namely \(n = 1002\).
- That gives \(2017 - 334 = 1683\) noblemen, answer A.
Mark:
· log in to save