There are $n\leq 99$ people around a circular table. At every moment everyone can either be truthful (always says the truth) or a liar (always lies). Initially some of people (possibly none) are truthful and the rest are liars. At every minute everyone answers at the same time the question "Is your left neighbour truthful or a liar?" and then becomes the same type of person as his answer. Determine the largest $n$ for which, no matter who are the truthful people in the beginning, at some point everyone will become truthful forever.
Problem
Source: Bulgaria JBMO TST 2022 Day 2 Problem 4
Tags: combinatorics, induction
15.05.2022 19:15
Isn't answer just $2$ Denote $0$ as truthful people and $1$ as liar people ( basically binary) and for $n>3$ we can make combination $..000010000..$ and the combination goes like this: $$...000000100000...$$$$...0000001100000...$$$$..00000010100000...$$$$..000000110100000..$$$$ .$$$$ .$$$$ .$$$$..1111111011111111..$$$$..00000001100000000..$$Which we get back to the second step, hence it goes infitely, but this is not true for $ n\le 2$ and $n=2$ obviously works? Uppsss you are right @below
15.05.2022 19:34
@above I don't see why you would get $0$ with all ones at the second-to-last step. For example, when $n=4$, we have $0100 \to 0110 \to 0101 \to 1111 \to 0000$.
15.05.2022 20:10
I'm very unsure about this solution, but I think it works First, we prove that every odd numbered configuration doesn't work. We can change the problem to make truth tellers 1, liars -1, and every minute, people turn into their number multiplied by the number of the person to their left. The final state of the circle is everyone is 1. The second last state of the circle can only be 111... or -1-1-1..., which means that the third-last state must be 111..., -1-1-1..., or 1, -1, 1, -1, and so on. This alternating configuration does not work for odd numbered circles, so there are only two initial configurations that work, that is 111 and -1-1-1. qed Now that we have proven this, it's easy to show that for $n$ with odd prime factors, there exist initial configurations that never reach the ultimate truth. We now prove that powers of 2 work. This is the part of the proof I haven't expressed in a strict algebraic form, so bear with me. Number the people in the circle in a clockwise fashion, and assume they are all facing inwards towards the table. Let $x_i$ be the initial number (that is, -1 or 1) for the person at the $i$th position. For $i$ greater than 64, simply take the remainder modulo 64. We now prove by induction that after $2^k$ minutes, the $i$th person has a number equal to $x_i\times x_{i+2^k}$. The base case is true because after two minutes, the $i$th person's number is $x_i\times x_{i+1}^2 \times x_{i+2} = x_i\times x_{i+2}$. Assume that $2^k$ have passed. Since everyone's number is equivalent to their initial number times the number of the person $2^k$ places to their left, everyone's numbers for the next $2^k$ minutes is equivalent to their own number in the first $2^k$ minutes times the number of the person $2^k$ places to their left in the first $2^k$ moves. In other words, if you want to find the number of the $i$th person after $2^k+\epsilon$ minutes, you take their number at $\epsilon$ minutes and multiply by the number of the person $2^k$ units to their left after $\epsilon$ minutes. This means that after another $2^k$ minutes, the person at $i$ has the number $x_i \times {x_{i+2^k}}^2\times x_{i+2^{k+1}} = x_i \times x_{i+2^{k+1}}$. Thus, for a circle of a size equal to a power of 2, at one point, their number is equal to their own number times itself, which means that everyone is a truth teller. the largest power of 2 in the restraints is $\boxed{64}$.