# Extremely hard prime factor based true-false statements [closed]

Let us suppose there are $n$ statements on the list. Each statement may be true or false. The first statement declares:

I am true.

Therefore, it could be true, or it could be false.

After this, for every statement $k$, $2\leq k\leq n$, let $p_k$ be the smallest prime factor of $k$. Every statement $k$ declares:

The number of false statements on this list is $\geq n(\frac{p_k-1}{p_k})$

What is the minimum and maximum possible value of $n$? (such the system is consistent)

Notes

1. Decimals are rounded up.

2. A set of statements may have more than one way of being consistent, but there must exist atleast one.

• Do I understand right that statement $k$ says that the number of True statements on the list is $\lfloor n/p_k \rfloor$? – xnor Apr 21 '15 at 10:07
• This problem looks to me like a pure math problem, with no kind of dress that makes it look like a puzzle. Just my opinion, though. – leoll2 Apr 21 '15 at 11:27
• Surely $n=1$ is the minimum possible value of $n$. If not, $n=2$ also works. – Ben Frankel Apr 21 '15 at 11:47
• @BenFrankel the puzzle states $2 \le k \le n$, so $n$ must be at least $2$. – Ian MacDonald Apr 21 '15 at 12:46
• I voted to close, but for a slightly different reason. I'm OK with the how the question is posed without a story, and it's similar to a classic liars and truthtellers as is common for puzzles except without the people. But, the solution seems pretty straightforward and it the first thing one might try, not something particularly clever. Too much of the solving effort is in unpacking the math in the problem statement, and that's what makes it feel like a math problem. – xnor Apr 21 '15 at 19:33

The minimum value of $n$ is $2$.
There is no maximum value of $n$.

Proof: (minimum)

When $n = 2$, we are presented with a list of statements:

$S_1$: I am true.
$S_2$: The number of false statements in this list is $1$.

$\therefore$ because the statements resolve consistently when $S_1$ is false, the minimum value for $n$ must be $2$.

Proof: (maximum)

Consider an $n > 2$. $n$ is either even or odd.

For every even $m$, $p_k = 2$, making the $S_m$ statement:

$S_m$: The number of false statements in this list is $n(\frac{2-1}{2}) = \frac{n}{2}$.

When $n$ is even, then also:

$S_n$: The number of false statements in this list is $\frac{n}{2}$.

Making each even-numbered true and each odd-numbered statement false makes $\frac{n}{2}$ statements false, agreeing with each even statement. In order for this list to not be consistent, one of the odd-numbered statements must also be true, but any odd-numbered statement will have a $p_k > 2$ since $2$ does not divide any odd number and $1$ is not prime.

Because we can always choose a larger even $n$, there is no maximum value of $n$.

Note: A similar argument could be made about odd numbers that would satisfy the conditions under the revised $\ge n(\frac{p_k-1}{p_k})$.

• how can (pk-1)/pk be equal to 1? – leoll2 Apr 21 '15 at 12:40
• @leoll2 The ceiling function rounds up. See the original puzzle note #1. – Ian MacDonald Apr 21 '15 at 12:42
• Ah, so 3/4 means that 1 statement is false, and not that 75% of the statements are false? Hmmm, this problem isn't that interesting, so... – leoll2 Apr 21 '15 at 12:45
• @leoll2 I agree that it isn't interesting, but it's the question as stated. If this isn't what the OP intended, he should clarify the question. – Ian MacDonald Apr 21 '15 at 13:25
• @IanMacDonald I meant 3/4 of the statements are false, not 3/4th of a statement is false. – ghosts_in_the_code Apr 21 '15 at 14:51

I may be confused. If so correct me.

## Minimum:

$n=1$ is consistent. The only statement is "I am true" and this can be either true or false without contradiction.

## Maximum:

There is no maximum. For any $n$ just have all of the even statements be true while all of the odds are false, then there are $\lceil\frac{n}{2}\rceil$ false statements and $\lfloor\frac{n}{2}\rfloor$ true statements which agrees with what the even statements say.

• If 1/2 statements are false then also 1/3 statements are false? Or does it have to be exact. – Ben Frankel Apr 21 '15 at 11:57
• n>1 so n=1 isn't acceptable – leoll2 Apr 21 '15 at 12:39
• @leoll2, I don't see where that is stated. It might be implied by "After this, for every $k$, $2 \le k \le n$, ..." but I don't think so. (for every doesn't imply existence) – Ben Frankel Apr 21 '15 at 12:55
• k>=2, n>=k, therefore n>=2 – leoll2 Apr 21 '15 at 13:03
• @leoll2, That assumes the existence of such $k$, which is not implied by "for every". You can say "every integer whose square is 2 is a Mersenne prime" and it would be true. – Ben Frankel Apr 21 '15 at 13:32

$P_2$=2
$\frac{P_2-1}{P_2}=\frac{1}{2}$