At least $N$ false statements

Let $N$ and $M$ be two integers with $M\ge N\ge2$.

There is a list of altogether $M$ statements that is divided into three parts: the first part consists only of the first statement; the second part consists of the $N-1$ statements with numbers from $2$ up to $N$; the third (possibly empty) part consists of the remaining statements with numbers from $N+1$ up to $M$.

The first part of the list declares:

Statement 1: Not all the statements on this list are false.

The statement with number $n$ with $2\le n\le N$ in the second part says:

Statement n: All statements with a number divisible by $n$ are false.

The statement with number $k$ with $N+1\le k\le M$ in the third part may be arbitrary.

Statement k: (Contents is left to the choice of the puzzle solver.)

Determine (in dependence on $N$) the minimum value of $M$ for which this system of statements does not yield a paradox.

• @Gamow They could be any statements. They could be true or false. They could be dependent or independent. Feb 12 '15 at 17:17
• I tried to improve the wording and the presentation of the puzzle, but the question in the end is unclear. If I have messed something up, then please revert my edit. Feb 12 '15 at 17:37
• @Gamow No, this is exactly what I meant. Feb 13 '15 at 15:11

(1) No statement $n$ with $2\le n\le N$ in the second part can be true, as it would imply its own falseness.

Every statement in the second part of the list is false.

(2) As statement $n$ with $2\le n\le N$ in the second part is false, we conclude that not all statements with a number divisible by $n$ are false. Equivalently, there exists some statement with a number divisible by $n$ that is true. Clearly, this true statement with a number divisible by $n$ must be in the third part of the list. We conclude:

For every $n$ with $2\le n\le N$, there is some true statement in the third part of the list, whose number is divisible by $n$.

(3) Now for $n=N$, the above discussion implies that the third part of the list contains a true statement whose number is divisible by $N$. This implies $M\ge2N$.

(4) If $M=2N$, then we can find the following true/false pattern for the list:

• The first statement is TRUE.
• All statements in the second part are FALSE.
• All statements in the third part are TRUE (let us say that they state $1+1=2$).

Since every number $n$ with $2\le n\le N$ has a multiple in the range $N+1,N+2,\ldots,2N$, the truth values are compatible and do not yield a paradox.

The answer is that the minimum value is $M=2N$.

• Correct answer! Only one correction: The statements in part 2 could all be true, since the statements in part 3 are true, and have divisible numbers. Feb 13 '15 at 15:34

N can be as small as 2.

1 Not all statements are false (true)
2 Every statement divisible by 2 is false (false) N
3 Every statement divisible by 3 is true (true)
4 Every statement divisible by 4 is true (true) M

Essentially, for your highest N, you have to have a higher 2*N that is true. Between N and M, every prime will need to be true.

• Wait, don't they all have to read "is false" not "is true"? Feb 12 '15 at 18:58
• Nah, it was changed. See statement K in the question. Feb 12 '15 at 19:01
• oh! I see now. My bad Feb 12 '15 at 19:06

The minimum value of M is N+1.

Statement 1 to (n-1) says : Not all statements in this list are false.

If the first statements are true it does not put any requirements on the rest of the list, as it itself is true. If the first statements are false then all statements must be false, thus the second part of statements must be true. Since the statements in the second part they themselves imply they are false this leads to a paradox.

Therefore all statements in the first part are true.

Statement n to N: All statements divisible by n are false. (can be true or false) Statement N+1=M: ..abritrary.. (can be true or false)

I don't think there are any possible values for M and N that don't trap us in a paradox

if M=2 and N=2

1) Not all the statements on the list are false.

2) Every 2nd statement is false

obviously we have a paradox because if 2) is declaring itself to be false then it's true

am I missing the question entirely?

• 2 is not declaring itself to be false. If 2) is false and, say, 32) is true then 2) is still 'wrong' but not paradoxically so, because it's not in fact the case that every 2nd statement is false.. Feb 12 '15 at 18:31
• you are absolutely right, I jumped to this conclusion way too fast Feb 12 '15 at 18:58