Author |
Topic: True or false list (Read 6391 times) |
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
True or false list
« on: Dec 16th, 2002, 8:01pm » |
Quote Modify
|
Consider a list of 2000 statements: 1) Exactly one statement on this list is false. 2) Exactly two statements on this list are false. 3) Exactly three statements on this list are false. . . . 2000) Exactly 2000 statements on this list are false. Which statements are true and which are false? What happens if you replace "exactly" with "at least"? What happens if you replace "exactly" with "at most"? What happens in all three cases if you replace "false" with "true"? Note: The "exactly . . . false" problem was posed by David L. Silverman for 1969 statements in the January, 1969 issue of the Journal of Recreational Mathematics. I got the problem from Martin Gardner's "Knotted Doughnuts and Other Mathematical Entertainments", where he discusses it and some of the variants above. (Modified to fix the error pointed out by J.S. in the next post. Thanks!)
|
« Last Edit: Dec 17th, 2002, 3:17pm by Icarus » |
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: True or false list
« Reply #1 on: Dec 16th, 2002, 8:58pm » |
Quote Modify
|
Ooooo...fancy. (When you said 'What happens in all three cases if you replace 'true' with 'false'?' did you mean 'replace false with true'?) Okay. For the exactly x are false variant: As far as I can tell, only "Exactly 1999 are false" is true. The rest are false. For the exactly x are true variant: AFAICT, only "Exactly 1 is true" is true. The rest are false. At least x are true: Every one could be true. Actually, I think it could be any combination of statements 1 through x being true, and x + 1 through 2000 being false.
|
|
IP Logged |
|
|
|
Paul Hammond
Newbie
Posts: 29
|
|
Re: True or false list
« Reply #2 on: Dec 17th, 2002, 1:25pm » |
Quote Modify
|
At least x are false: Statements 1-1000 are true, 1001-2000 are false, because if statement n is true then statement(n-1) must be true. At most x are false: Statement 2000 must be true, therefore Statement 1999 must be true, etc. So they're all true. At most x are true: Statement 2000 must be true, therefore Statement 1 must be false, therefore Statement 1999 must be true... [etc.] ...therefore Statement 999 must be false, therefore Statement 1001 must be true. Statement 1000 is neither true nor false; if it were true that would give us 1001 true statements i.e. it would be self-contradictory. Likewise, if it were false that would give us 1000 true statements, so it would be true.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: True or false list
« Reply #3 on: Dec 17th, 2002, 3:23pm » |
Quote Modify
|
Okay, now what happens if you add statement 0 ("None of these statements is false") to the front of the list?
|
|
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: True or false list
« Reply #4 on: Dec 19th, 2002, 12:08pm » |
Quote Modify
|
Are we to assume that all of the statements have a definite truth value of "true" or "false"? If you take away that restriction, then there are (I think) a plenitude of answers.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: True or false list
« Reply #5 on: Dec 19th, 2002, 3:47pm » |
Quote Modify
|
**Shudder** I've already been down that road with Tim (see the All sigs are false thread), and I'm not sure I want to try it again. Some cases may come up with contradictions, and as Jeremiah points out, in the original puzzle one of the situations has multiple solutions. But other than that, let's stick with true or false! Though if you have found something interesting...
|
|
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
i_m_n_idiot
Newbie
Posts: 6
|
|
Re: True or false list
« Reply #6 on: Jan 4th, 2003, 9:17pm » |
Quote Modify
|
statement 2000 is false
|
|
IP Logged |
|
|
|
|