Welcome to our community

Be a part of something great, join today!

Logic problem

TheBigBadBen

Active member
May 12, 2013
84
Consider the following sequence of statements:
$$
S_1: \text{at least 1 of the statements }S_1-S_n \text{ is false}\\
S_2: \text{at least 2 of the statements }S_1-S_n \text{ are false}\\
\vdots \\
S_n: \text{at least } n \text{ of the statements }S_1-S_n \text{ are false}
$$
Where $n$ is some integer.

Question: for which $n$ are these statements self-consistent? In those cases: what is the truth value of each statement?

I got this off of a blog I tend to frequent. I will wait before posting the solution this time.

EDIT:
Changed the question; I had written the statements wrong
 
Last edited:

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,774
Suppose $k$ out of $n$ statements are true.
Then $S_1$ up to $S_k$ have to be true and the rest has to be false.
This appears to be consistent for any $n$ and any $0\le k \le n$.
 

TheBigBadBen

Active member
May 12, 2013
84
Suppose $k$ out of $n$ statements are true.
Then $S_1$ up to $S_k$ have to be true and the rest has to be false.
This appears to be consistent for any $n$ and any $0\le k \le n$.
Sorry about that, you were absolutely right about the question as phrased.

However, this new version should prove to be a bit more interesting. This is what I had meant; I had accidentally written "true" instead of "false".
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,774
If $S_n$ is true, then $n$ statements are false, including $S_n$.
Therefore $S_n$ is false.

We now know that at least $1$ statement is false.
Therefore $S_1$ is true.
For $n=1$ this is a contradiction, and for $n=2$ this is a consistent solution.

For $n \ge 3$ we can say, that if $S_{n-1}$ were true, then $n-1$ statements are false.
Since $S_1$ is true, this implies that $S_{n-1}$ is false.
Therefore $S_{n-1}$ is false.

So at least $2$ statements are false.
Therefore $S_2$ is true.
For $n=3$ this is a contradiction, and for $n=4$ this is a consistent solution.

Etcetera.


In other words, we get a consistent consistent solution if and only if $n$ is even.
In that case $S_1$ up to $S_{n/2}$ are true and $S_{n/2+1}$ up to $S_{n}$ are false. $\qquad \blacksquare$
 

TheBigBadBen

Active member
May 12, 2013
84
If $S_n$ is true, then $n$ statements are false, including $S_n$.
Therefore $S_n$ is false.

We now know that at least $1$ statement is false.
Therefore $S_1$ is true.
For $n=1$ this is a contradiction, and for $n=2$ this is a consistent solution.

For $n \ge 3$ we can say, that if $S_{n-1}$ were true, then $n-1$ statements are false.
Since $S_1$ is true, this implies that $S_{n-1}$ is false.
Therefore $S_{n-1}$ is false.

So at least $2$ statements are false.
Therefore $S_2$ is true.
For $n=3$ this is a contradiction, and for $n=4$ this is a consistent solution.

Etcetera.


In other words, we get a consistent consistent solution if and only if $n$ is even.
In that case $S_1$ up to $S_{n/2}$ are true and $S_{n/2+1}$ up to $S_{n}$ are false. $\qquad \blacksquare$
Couldn't have phrased it better myself.

The source, for anybody interested:
The Parity Paradox – Futility Closet

I highly recommend the website as a time-wasting tool.