Given 10 statements relating to one another, what is the maximum number of true statements?

Question

(I don't know whether this can be classified as an actual mathematics question. Feel free to take this down if it doesn't qualify.)

Given the following statements, \begin{align} 1. &\text{ At least five of the statements listed below are true.}\\ 2. &\text{ At least four of the statements listed below are false.}\\ 3. &\text{ At least three of the statements listed below are true.}\\ 4. &\text{ At least two of the statements listed below are false.}\\ 5. &\text{ At least one of the statements listed below is true.}\\ 6. &\text{ At least one of the statements listed above is false.}\\ 7. &\text{ At least two of the statements listed above are true.}\\ 8. &\text{ At least three of the statements listed above are false.}\\ 9. &\text{ At least four of the statements listed above are true.}\\ 10. &\text{ At least five of the statements listed above are false.}\\ \end{align} Providing that true statements provide information that is supported by evidence and false statements provide information that contradicts evidence, what is the maximum number of true statements?

Right, first of all, suppose there are exactly four false statements between $(3)$ and $(10)$. (I should clarify that whenever "between $(a)$ and $(b)$" is mentioned, it applies to all statements $(n)$ where $a \le n \le b$.) The other four statements between $(3)$ and $(10)$ are true and additionally, statement $(2)$ is correct. This means there are exactly five true statements between $(2)$ and $(10)$, and statement $(1)$ is therefore correct.

Having identified the conditions given in statements $(1)$ and $(2)$ are met, we can also infer that statement $(7)$ is true, and from which infer that statement $(5)$ is also true. Refer to this logic again and the two next correct statements to be found are $(9)$ and $(3)$ in that order.

So far, six statements have to proven to be true - $(1) - (2) - (3) - (5) - (7) - (9)$ (which consist of all statements relating to the number of true statements and one statement on which we base our hypothesis). This eliminates the possibility of there being five or more correct statements between $(1)$ and $(9)$, thus, statement $(10)$ is false, implying statement $(5)$ is true. Continuing with this logic, conditions presented in statements $(7)$ and $(9)$ are not fulfilled, from which we can confirm their falsehood.

In the end, there are three false statements - $(6) - (8) - (10)$, which contradicts the presupposed hypothesis of there being "exactly four true statements between $(3)$ and $(10)$". (Why does it have to end this way? It was going so well~)

Let's start the other way around. Suppose there are exactly four true statements between $(1)$ and $(8)$, the other four statements between $(1)$ and $(8)$ are false. However, according to this hypothesis, statement $(9)$ is not incorrect, meaning that statement $(10)$ is false. Since we're looking for the maximum number of true statements, we'll assume that there are a minimum of four true statements between $(1)$ and $(8)$, reaffirming that statement $(9)$ is correct and statement $(10)$ is incorrect.

From this starting point, we can deduce that statement $(5)$ is true, (doesn't it start to look like our first case? Statements $(5) - (9) - (10)$ are factually the same), and actually, that's all of it. We can technically go further if we come up with more presumptions, but I'll stop here for now.

How about we revisit our first hypothesis? Since we're looking for the maximum number of true statements, we'll assume that statement $(2)$ is false, meaning that statement $(1)$ is true. Actually, let's skip the tedious reasoning. I've made a table detailing the process it takes to decide whether each statement is true according to previous claims. This is one of the configurations which provide supporting information to true statements and contradicting information to false ones.

But is this the case which maximises the number of true statements? Is there a way to prove that a combination with more than seven true statements is not logically attainable? What about one with the most false statements possible? I'd surmise that it's basically the opposite to the configuration above - $\text{T} - \text{F} - \text{T} - \text{F} - \text{F} - \text{F} - \text{F} - \text{F} - \text{F} - \text{T}$.

Answer 1

If you would have eight or more True statements, then you have at most two False statements, and hence 2, 8 and 10 all have to be False, ... which contradicts that you would have at most two False statements!

So no, you cannot have eight or more True statements.

Now, you found a solution with exactly seven True statements. Are there any other solutions with 7 True statements? No, because with 7 True statements, we know that 2 and 10 are False (again: not enough False statements), but with 3 False statements, and 10 already being False, 8 can at most have two False statements above it, and so 8 has to be False as well. So, 2, 8, and 10 have to be False if there are 7 True statements, and so this is the only solution with 7 True statements.

OK, but what about maximizing the number of False statements?

First, note that your solution for False's

$\text{T} - \text{F} - \text{T} - \text{F} - \text{F} - \text{F} - \text{F} - \text{F} - \text{F} - \text{T}$

does not work at all! If we use your distribution to evaluate the claims, we would have that only 9 and 10 have the correct truth-value! So no, you can't just 'invert' the solution here.

OK, so how many False's can we have?

Note that having six or more False statements makes 2, 4, 6, 8, and 10 all become True.... and so immediately you can no longer have six or more False statements. So, you cannot have six or more False statements.

OK, but now consider: If 1 is False, then 1 has at most four True statements below it, and therefore at least five False statements below itself, giving a total of at least six False statements. But we already established that that is impossible, so 1 cannot be False. So, we know that 1 has to be True. But that forces 3,5,7, and 9 to be True as well. And that in turn forces 10 to be False. Now if 8 would be True, 2,4, and 6 would all have to be False, but now we have a problem with 4. So, 8 is False. That forces 4 to be True. That makes 2 False, and finally 6 has to be True.

So, we have in fact now established that there is exactly one and only one possible solution to this puzzle!

Answer 2

You can solve the problem via integer linear programming as follows. For $i\in\{1,\dots,10\}$, let binary decision variable $x_i$ indicate whether statement $i$ is true. The problem is to maximize $\sum_{i=1}^{10} x_i$ subject to \begin{align} x_1 = 1 &\implies \sum_{i=2}^{10} x_i \ge 5 \\ x_2 = 1 &\implies \sum_{i=3}^{10} (1 - x_i) \ge 4 \\ x_3 = 1 &\implies \sum_{i=4}^{10} x_i \ge 3 \\ x_4 = 1 &\implies \sum_{i=5}^{10} (1 - x_i) \ge 2 \\ x_5 = 1 &\implies \sum_{i=6}^{10} x_i \ge 1 \\ x_6 = 1 &\implies \sum_{i=1}^5 (1 - x_i) \ge 1 \\ x_7 = 1 &\implies \sum_{i=1}^6 x_i \ge 2 \\ x_8 = 1 &\implies \sum_{i=1}^7 (1 - x_i) \ge 3 \\ x_9 = 1 &\implies \sum_{i=1}^8 x_i \ge 4 \\ x_{10} = 1 &\implies \sum_{i=1}^9 (1 - x_i) \ge 5 \end{align} These logical implications can be linearized as follows: \begin{align} \sum_{i=2}^{10} x_i &\ge 5 x_1 \tag1 \\ \sum_{i=3}^{10} (1 - x_i) &\ge 4 x_2 \tag2 \\ \sum_{i=4}^{10} x_i &\ge 3 x_3 \tag3 \\ \sum_{i=5}^{10} (1 - x_i) &\ge 2 x_4 \tag4 \\ \sum_{i=6}^{10} x_i &\ge 1 x_5 \tag5 \\ \sum_{i=1}^5 (1 - x_i) &\ge 1 x_6 \tag6 \\ \sum_{i=1}^6 x_i &\ge 2 x_7 \tag7 \\ \sum_{i=1}^7 (1 - x_i) &\ge 3 x_8 \tag8 \\ \sum_{i=1}^8 x_i &\ge 4 x_9 \tag9 \\ \sum_{i=1}^9 (1 - x_i) &\ge 5 x_{10} \tag{10} \end{align} The unique optimal solution turns out to be $x=(1,0,1,1,1,1,1,0,1,0)$, with objective value $7$. The linear programming relaxation has optimal objective value $23/3$, which implies integer upper bound $\lfloor 23/3 \rfloor = 7$. An optimal dual solution provides a short certificate of optimality. Explicitly, multiply constraints $(6)$, $(8)$, and $(10)$ by $-8/15$, $-4/15$, and $-1/5$, respectively, and add these to the valid constraints $\frac{8}{15}x_7 \le \frac{8}{15}$ and $\frac{4}{5}x_9 \le \frac{4}{5}$ to obtain $\sum_{i=1}^{10} x_i \le \frac{23}{3}$.

Answer 3

It often helps to assume the most restrictive thing because it is easiest to reach a contradiction and make progress. If we assume 5 is false, then 6-10 are all false and 10 tells us 1-5 must be false. Then 1,3 are false and 2,4 are true but this contradicts 7 being false, so 5 is true.

Now assume 6 is false. Then 1-5 are all true and 2 tells us 7-10 are false. Again 7 makes a contradiction, so 6 is true.

This makes 7 true, which makes 3 true, which makes 9 true, which makes 1 true. Then 10 is false and 8 is false. That makes 4 true and 2 false. The only consistent assignment is 2,8,10 false and the others true. You can check that this is consistent with all the data.