Japan 2007

If $0\le T\le 668$, we will prove that there exists an instruction which fulfills the conditions. Give the following instruction to every villager.

Define today as 0th day. All the villagers must prepare a notebook and a memo pad.

Today, each villager $p$ should write the idea of the village's name $m$ in the letters $[p$ proposed $m]$ and send these letters to every villager (including oneself). And at $i=1,2,\dots ,2T+2$th day, perform all the following in order.

If you receive the letter $[p_0$ proposed $m]$ from villager $p$ in the morning, send the letter $[i-1$th day $p$ says $p_0$ proposed $m]$ to every villager. Until then, if you have received the letter $[j$th day $p$ says $p_0$ proposed $m]$ ($j\le i-2$) from $2007-2T$ or more persons, send the letter $[j$th day $p$ says $p_0$ proposed $m]$ to every villager. Until then, if you have received the letter $[j$th day $p$ says $p_0$ proposed $m]$ ($j\le i-2$) from $2007-T$ or more persons, write [sure: $j$th day $p$ says $p_0$ proposed $m]$ to your memo pad. About villager $p_0$ and idea $m$, if $i$ is even and distinct $\frac{i}{2}$ villagers $p_0,p_2,\dots ,p_{i-2}$ exist and [sure: $j$th day $p_j$ says $p_0$ proposed $m]$ is written in your memo pad for all the even numbers that satisfy $0\le j<i$, then write $[p_0$'s idea seems to be $m]$ in your notebook and send the letter $[p_0$ proposed $m]$ to every villager.

And at $2T+2$th day, all the villagers must look into their notebook and look for all the pairs $(p,m)$ that satisfy the following condition.

Condition: $[p$'s idea seems to be $m]$ is written in your notebook. And if $[p$'s idea seems to be $m]$ and $[p$'s idea seems to be $n]$ are both written in your notebook, then $m=n$.

Consider $(p,m)$ pairs that satisfy this condition only. Count the kind of $p$ corresponding to each $m$. And if only one $m$ has the most kinds of $p$, then send a letter $[m]$ to God. Otherwise, send a letter [JMO] to God.

Now let us prove that this instruction satisfies the problem's condition. We will prove the following. Notice that $2007>3T$.

(1) If some honest person wrote [sure: $j$th day $p$ says $p_0$ proposed $m$] in his memo pad, villager $p$ really sent the letter [$p_0$ proposed $m$] on the $j$th day.

(2) If some honest person wrote [sure: $j$th day $p$ says $p_0$ proposed $m$] in his memo pad on the $k$th day, every honest person wrote the same content in their memo pads by the $k+1$th day.

(3) Now assume that $p_0$ is an honest person. If some honest person wrote [$p_0$'s idea seems to be $m$] in his notebook, $p_0$ really proposed $m$. And if $p_0$ proposed $m$, every honest person would write [$p_0$'s idea seems to be $m$] in their notebook by the $2T+2$th day.

(4) If some honest person wrote [$p$'s idea seems to be $m$] in his notebook, every honest person would write the same content in their memo pads by the $2T+2$th day.

Proof of (1): Assume that some honest person wrote [sure: $j$th day $p$ says $p_0$ proposed $m$] to his memo pad. According to the instruction, he received the letter [$j$th day $p$ says $p_0$ proposed $m$] from $2007-T$ or more persons. Especially, from $2007-T>T$, there exists some honest person who sent the letter [$j$th day $p$ says $p_0$ proposed $m$]. Now define $q$ as the honest person who sent this content first. There are two possible reasons why $q$ sent this letter.

(a) $q$ received the letter of this content from $2007-2T$ or more people. (b) $q$ received the letter of the content [$p_0$ proposed $m$] from $p$.

But in the case of (a), from $2007-2T>T$, a certain honest person sent a letter [$j$th day $p$ says $p_0$ proposed $m$] to $q$ earlier than $q$ sent the same letter. This is contrary to the definition of $q$. Therefore, there is the case (b) only, and lemma (1) is proved.

Proof of (2): Assume that some honest person wrote [sure: $j$th day $p$ says $p_0$ proposed $m$] to his memo pad on the $k$th day. It means that $2007-T$ or more villagers, therefore $2007-2T$ or more honest people sent a letter [$j$th day $p$ says $p_0$ proposed $m$] to him by the $k$th day. By the way, every honest person sent letters to every villager every day, so every villager receives the letter of this content from $2007-2T$ or more persons by the $k$th day, and so every honest person sent the letter of this content to every villager, and therefore every villager will receive the letter of this content from $2007-T$ or more persons by the $k+1$th day. Thus, every honest person wrote [sure: $j$th day $p$ says $p_0$ proposed $m$] in their memo pad by the $k+1$th day. Lemma (2) is proved.

Proof of (3): Assume that some honest person wrote [$p_0$'s idea seems to be $m$] in his notebook. According to the instruction, [sure: 0th day $p_0$ says $p_0$ proposed $m$] was written in his memo pad. According to lemma (1), $p_0$ sent the letter [$p_0$ proposed $m$] on the 0th day. Next, assume that $p_0$ sent the letter [$p_0$ proposed $m$] to every villager. Then on the 1st day, every honest person, that means $2007-T$ or more honest people receive this letter, and send the letter [0th day $p_0$ says $p_0$ proposed $m$] to every villager. Then on the 2nd day, every honest person receives this letter, and writes [0th day $p_0$ says $p_0$ proposed $m$] to their memo pad, and then write [$p_0$'s idea seems to be $m$] to their notebook. Lemma (3) is proved.

Proof of (4): Assume that the honest person who wrote [$p_0$'s idea seems to be $m$] in the notebook earliest is $q$, and $q$ wrote this on the $2i+2$th day. According to the instruction, there exist distinct villagers $p_0,p_2,\dots ,p_{2i}$ and [sure: $2j$th day $p_{2j}$ says $p_0$ proposed $m$] in $q$'s notebook. From $2i+2\le 2T+2$, then $i\le T$. So there exists a number $j$ that $p_{2j}$ is an honest person, or there doesn't exist such number $j$. In this case, $i<T$.

In the case of the former, if $p_{2j}$ is an honest person, according to lemma (1), $p_{2j}$ really sent the letter [$p_0$ proposed $m$] on the $2j$th day, or $2j=0$. But the former is contrary to the definition of $q$. So $j=0$. And thus every honest person wrote [$p_0$'s idea seems to be $m$] in their notebook on the 2nd day. (This fact is proved by the part of proof of lemma (3))

In the case of the latter, $q$ sent the letter [$p_0$ proposed $m$] to every villager on the $2i+2$th day. And from the same argument as (3), every honest person wrote [sure: $2i+2$th day $q$ says $p_0$ proposed $m$] in their notebook on the $2i+4$th day. By the way, the content [sure: $2j$th day $p_{2j}$ say $p_0$ proposed $m$] ($0\le j\le i$) in $q$'s notebook will be also written in every honest person's notebook (reference to lemma (2)). Every $p_{2j}$ isn't honest, so $q$ is different from every $p_{2j}$. Therefore, from these facts, every honest person wrote [$p_0$'s idea seems to be $m$] in their notebook on the $2i+4$th day. Now $i<T$, then $2i+4\le 2T+2$. Lemma (4) is proved.

According to lemma (4), on the evening of the $2T+2$th day, the contents of every honest person's notebook are the same. So every honest person will send the same letter to God. Thus the first condition is satisfied. Next, according to lemma (3), every honest person's idea is written in every honest person's memo pad. And for honest person $p$, at most one $m$ is written as [$p$'s idea seems to be $m$]. Therefore, if every honest person had the same idea of the village name $h$, $h$ gains the most votes. ($2007-T>\frac{2007}{2}$) Thus every honest person sends a letter $[m]$ to God. So the second condition is satisfied.

Next, we will prove that if $T\ge 669$, instructions which fulfill the conditions don't exist. At first, prove the following lemma.

Lemma A: In the problem, if the number of villagers is changed into $3$, and put $T=1$, instructions which fulfill the conditions don't exist.

Proof of Lemma A: Assume that instructions which fulfill the conditions exist. Define three villagers as $1,2$ and $3$. Assume that this instruction doesn't direct to send a letter to oneself. Consider the following situation X. There was another village in which three villagers $1,2$ and $3$ live. And this village also had no name. And in this village, another God gave the same instruction as the same day ($1,2,3$ correspond to $1,2,3$). But because of a mistake of the post office, the letter from $i$ to $j$ always arrived as a letter from $i$ to $j$, and the letter from $i$ to $j$ always arrived as a letter from $i$ to $j$ ($i,j=1,2,3$). And $1,2,3,1^{\prime },2^{\prime },3^{\prime }$ are honest people, and consider $a,a,b,b,b,a$ as their ideas of the name of the village respectively. ($a\ne b$)

First, take notice of $1$ and $2^{\prime }$. Consider the following village Z.

Village Z has three villagers $1^{\prime \prime },2^{\prime \prime },3^{\prime \prime }$. The same direction was given to village Z. $1^{\prime \prime }$ is a honest person, and considers $a$ as an idea of the name of the village Z. $2^{\prime \prime }$ is a honest person, and considers $b$ as an idea of the name of the village Z. $3^{\prime \prime }$ is a liar. $3^{\prime \prime }$ sends a letter which $3$ sent to $2$ on the $i$th day to $2^{\prime \prime }$ on the $i$th day. And $3^{\prime \prime }$ sends a letter which $3$ sent to $1$ on the $i$th day to $1^{\prime \prime }$ on the $i$th day.

In this situation, actions of $1^{\prime \prime }$, $2^{\prime \prime }$ in Village Z is the same as actions of $1,2^{\prime }$ in Situation X. From the assumption that the instruction fulfills the conditions, $1^{\prime \prime }$ and $2^{\prime \prime }$ send the same idea $x$ for the name of the village Z to God. $x\ne a$ or $x\ne b$ holds, and we can assume $x\ne a$.

Next, take notice of $1$ and $3^{\prime }$. From the same reason, they send the same idea $x$ for the name of the village Z to God. But they considered the same idea $a$ at first, so the idea they send to God is $a$ (from the second condition). This is a contradiction. So the lemma A is proved.

And now assume that there exists an instruction $K$ which fulfills the conditions if $T\ge 669$. Define $2007$ villagers as $A_1,A_2,\dots ,A_{669},B_1,B_2,\dots ,B_{669},C_1,C_2,\dots ,C_{669}$. Consider the following instruction J about the village which three persons $\alpha ,\beta ,\gamma$ live in and $T=1$.

Each villager must prepare $669$ dolls. Define the dolls of $\alpha ,\beta ,\gamma$ as $a_1,a_2,\dots ,a_{669},b_1,b_2,\dots ,b_{669},c_1,c_2,\dots ,c_{669}$. $\alpha$ should make each doll $a_j$ consider the same idea as $\alpha$ thinks. And $\alpha$ should make each doll $a_j$ do the same action as the action which $A_j$ does in the instruction $K$. If $a_j$ sends a letter $[x]$ to $A_i$ (or $B_i,C_i$), $\alpha$ must send a letter $[A_j\to A_i,x]$ to $\alpha$ (or $\beta ,\gamma$). And if $\alpha$ receives the letter of the following form, $\alpha$ must give this letter to $a_j$ (as the letter from $A_i,B_i,C_i$. And the content of this letter is $[y]$). And if $\alpha$ received a letter in other forms, $\alpha$ must ignore it.

$[A_i\to A_j,y]$ from $\alpha$ $[B_i\to A_j,y]$ from $\beta$ $[C_i\to A_j,y]$ from $\gamma$

And if every $a_i$ ($i=1,2,\dots ,669$) sent the same letter $[z]$ to God, $\alpha$ must send the letter $[z]$ to God. $\beta ,\gamma$ must act the same way. We will prove that the instruction J fulfills the conditions. Assume that only $\alpha$ is a liar. In the case of $A_1,A_2,\dots ,A_{669}$ are liars and the others are honest people, $B_1,B_2,\dots ,B_{669},C_1,C_2,\dots ,C_{669}$ will send the same idea to God, so $\beta ,\gamma$ will send the same idea. And the instruction J also fulfills the second condition. We can prove other cases by the same way. But this is contrary to the Lemma A. So it is proved that if $T\ge 669$, instructions which fulfill the conditions don't exist.

Therefore, the answer is $668$.