1. At least 1 statement among these 2n+1 are true.
2. At least 3 statements among these 2n+1 are false.
3. At least 5 statements among these 2n+1 are true.
...
2n. At least (4n-1) statments among these 2n+1 are false.
2n+1. At least (4n+1) statements among these 2n+1 are true.

How many statements are true? Which?

First, its important to note that this problem isn't defined for all n.  For example, consider n = 4.  there are 4 statements referring to more than 9 statements, so they must all be false, which means statement 2) is true (at least 3 false), which means 1) is true (at least 1 true).  This also forces 3) and 5) to be false (at least 5 true, and at least 9 true).  So far we have 2 true statements, 6 false statements, and statement 4) (at least 7 false) is undecided.  suppose 4) is false, that makes 7 false statements, which makes 4) true which leaves 6 false statements which makes 4) false, and round and round we go.  Thus, this is a circular case where the validity of statement 4) is undefined. 

Now, consider assigning each statement a t or f according to the type of statement to which it refers.  Note that is a statement is true, then all previous statement of the same type (t or f) is also true.  Thus, we can determine exactly which statements are true if we can determine the last (highest numbered) statement of each type.   

Here's a table of some early values of n: the number of true, false, and undefined statements, and the number of true statements of each type (t and f):

• n    false  undef.  true:  t     f 
• ----------------------------------
• 0       1                 0     1    0
• 1       2                 1     1    0
• 2       3                 2     1    1
• 3       5                 2     1    1
• 4       6        1       2     1    1
• 5       8                 3     1    2
• 6       10               3     1    2
• 7       10      2       3     1    2
• 8       12               5     2    3
• 9       14               5     2    3
• 10     15               6     2    4
• 11     17               6     2    4
• 12     18      1       6     2    4
• 13     20               7     2    5
• 14     22               7     2    5
• 15     22      2       7     2    5
• 16     24               9     3    6
• 17     26               9     3    6
• 18     27               10   3    7
• 19     29               10   3    7
• 20     30      1       10    3    7
• 21     32               11   3    8
• 22     34               11   3    8
• 23     34      2       11    3    8
• 24     36               13    4    9
• 25     38               13    4    9
• ...

I don't have a closed-form proof, but looking at the table it's apparent that there's a linear pattern emerging with a period of 8. 

For n = 0, the result is undefined; for n = 1, statement 1) is the only true statement.  For each nonnegative integer n, the number of true statements (Tn) = the number of true t statements (Ttn) + the number of true f statements (Tfn).  Using square brackets ([]) to mean "round down", we have:

• Ttn = [n/8] + 1
• Tfn = [(3n-2)/8] +1
• Tn = [n/8] + [(3n-2)/8] +2

Since knowing the number of true statements in each category (t and f) determines exactly which statements are true, this solves the puzzle. //

Posted by josh on 2005-06-29 21:31:35