Discrete Math question

Factual Questions
1

From Discrete Mathematics and Its Applications: Seventh Edition

The answer the book gives to this is that statement 99 is true and the rest are false, but I cannot figure out how you get to that conclusion.

In the next problem, they change the “Exactly” to “At least,” which changes the answer to statements 1 through 50 being true and 51 through 100 being false. Again, I don’t see any sort of clues here that should lead me to this conclusion.

I’m taking a course in Discrete Math at my local university. This is not required homework, but inquiring minds want to know!

2

Hint: All 100 statements are mutually exclusive, since they all claim a different number of true statements. Given that, how many of them could be true?

3

For the second problem, if any one statement is true, then so are all the preceding statements. Which is the last statement that could be true?

4

[QUOTE=Discrete Mathematics and Its Applications: Seventh Edition]
The nth statement in a list of 100 statements is “Exactly n of the statements in this list are false.”

What conclusions can you draw from these statements?
[/QUOTE]

Counterexample. Let n be 2.

Statement 1: “1 + 3 = 456”.
Statement 2: “Exactly 2 of the statements in this list are false.”
Statement 3: “George Washington was born in 1492.”
Statement 4: “Japan won World War 2 by invading Poland.”
Statement 5: “The Boeing 737 is a type of aircraft.”
Statement 6: “Obama won a gold medal in skating at the 2010 Winter Olympic Games in Vancouver.”
Statement 7: “The square root of 4565 is -1/3.”
Statement 8: “1+1=2”
Statement 9: “3 squared is 9.”
Statements 8-100: <various true statements>

There. Statement 2 is that exactly 2 statements in the list are false, but this is clearly not the case. Statements 1, 3, 4, and 6, and 7 are clearly false, therefore Statement 2 is also false. However, statements 5, 8, and 9 are true, and this contradicts the book which claims that they are false. QED. I revoke the author’s degrees.

5

It would of been clearer if they’d started the exercise with “For all n…”

6

This is what I thought too, that n = some specific number, and all the other statements are arbitrary statements.

7

Thank you! The light bulb came on when I read this.

Like robert_columbia, I was assuming that only the nth statement was making a claim about the number of true statements, not that all of them were making similar claims.

8

But what does the wisserteenth statement say?

9

That wisserteen of the statements are false, of course.

10

John Jacob Jingleheimer Schmidt (1964) established in a PhD dissertation that the number of false statements must be less than wisserteen unless the set of statements also conforms to Howard’s (1933) Eleventy-Oneth Logical Model (as cited in Schmidt, 1964).

References

Schmidt, J. J. J. (1964). I know you are, but what am I? (Doctoral dissertation). Cambridge, MA: MIT.

11

The list is

  1. Exactly 1 of the statements in this list are false.
  2. Exactly 2 of the statements in this list are false.
  3. Exactly 3 of the statements in this list are false.

Etc

  1. Exactly 99 of the statements in this list are false.

  2. Exactly 100 of the statements in this list are false.
    Try having all 100 are false.
    So the 100th is statement is paradoxical. IF all 100 are false, then the 100th is not false… Its not clear how to handle this.
    But look at the list of statements, 1 to 100.
    There cannot be more than one that is true, because they each specify a different number.

If exactly 1 is true, then 99 are false, which matches to line 99.

The problem with the question is we know line 100 is paradoxical. paradoxically correct solutions are paradoxical…

12

This statement is false.

13

I once bought a French logic puzzle magazine; many of its logic puzzles were preceded with a meta-statement like
Each of the following statements is either true or false.

Such a meta-statement is needed to make some of these puzzles valid. I thought it was wise of the French to include that admonition, which is usually omitted in similar English-language puzzles.

14

I’m not sure what paradox you’re seeing here. There’s an inherent contradiction in having all 100 lines be false. That is how we know all 100 lines are not false. Isn’t that how proof by contradiction works?

15

Discussion of truth and falsehood may be dragging in issues not necessary for understanding the intended content of this problem. We can rephrase it, if we like.

The (first) problem is equivalent to this:
There are 100 balls in a row, each either black or white.
For each n in 1 through 100, the following holds: Either (the number of white balls is n, and the nth ball is black) or (the number of white balls is not n, and the nth ball is white)

Given this information, what can you conclude about the sequence of colors of the balls?

Answer: The 99th ball is black and all the other balls are white.

16

It may be easier to understand the question if we start with a similar one which is shorter, so you can see all the statements:

  1. Exactly 1 of the statements in this list are false.
  2. Exactly 2 of the statements in this list are false.
  3. Exactly 3 of the statements in this list are false.
  4. Exactly 4 of the statements in this list are false.
  5. Exactly 5 of the statements in this list are false.
  6. Exactly 6 of the statements in this list are false.
  7. Exactly 7 of the statements in this list are false.
  8. Exactly 8 of the statements in this list are false.
  9. Exactly 9 of the statements in this list are false.
  10. Exactly 10 of the statements in this list are false.

So what’s the only statement on this list that could possibly be true? First, note that each of the ten statements contradict all of the others. It’s impossible for more than one of them to be true at the same time. So which of these statements is claiming that at most one statement is true? It’s clearly either statement 9 or statement 10. But statement 10 claims that all ten statements are false, which means that it’s saying that the statement “Exactly 10 of the statements in this list are false” is false, which means that at least one statement is true, which contradicts what statement 10 is saying. So statement 9 must be true. This says that statements 1 to 8 and statement 10 are false and statement 9 is true.

Similarly, look at the following ten statements:

  1. At least 1 of the statements in this list are false.
  2. At least 2 of the statements in this list are false.
  3. At least 3 of the statements in this list are false.
  4. At least 4 of the statements in this list are false.
  5. At least 5 of the statements in this list are false.
  6. At least 6 of the statements in this list are false.
  7. At least 7 of the statements in this list are false.
  8. At least 8 of the statements in this list are false.
  9. At least 9 of the statements in this list are false.
  10. At least 10 of the statements in this list are false.

Note the following:

If statement 10 is true, then statements 1 to 9 must also be true.
If statement 9 is true, then statements 1 to 8 must also be true.
If statement 8 is true, then statements 1 to 7 must also be true.
If statement 7 is true, then statements 1 to 6 must also be true.
If statement 6 is true, then statements 1 to 5 must also be true.
If statement 5 is true, then statements 1 to 4 must also be true.
If statement 4 is true, then statements 1 to 3 must also be true.
If statement 3 is true, then statements 1 to 2 must also be true.
If statement 2 is true, then statement 1 must also be true.

Statement 10 can’t be true, since it would say that it’s false itself, so that’s contradictory. So at least one statement is false.

Statement 9 can’t be true, since it would say that it’s false itself, so that’s contradictory. So at least two statements are false.

Statement 8 can’t be true, since it would say that it’s false itself, so that’s contradictory. So at least three statements are false.

Statement 7 can’t be true, since it would say that it’s false itself, so that’s contradictory. So at least four statements are false.

Statement 6 can’t be true, since it would say that it’s false itself, so that’s contradictory. So at least five statements are false.

Statement 5 could be true. If statement 5 is true, it says that statements 1 to 4 are true. So statements 1 to 5 are true and statements 6 to 10 are false.

17

Is it not just the upperlimit minus one?
In this case it’s n=99 but if you had 1,000,000 statements then n=999,999.
It doesn’t seem like maths at all to me, just logical thinking. :dubious:

18

That’s what maths is. :cool:

19

Of course, the question requires that you buy into the premise that statements that refer to their own validity can be unambiguously true or false, and that there’s a non paradoxical solution, which in this case, there is. However, that isn’t the case, and there are probably infinite variations of the liars paradox you could build with this overall structure. For instance:

A: “George Washington was born in 1492.”
B: “The square root of 9 is 3”
C: “Exactly one of these three statements is true”

A is clearly false, and B is clearly true. C therefore must be false iff it is true.

20

Right; this is is why I suggested rephrasing to avoid such issues. The mathematical content of these questions amounts to “Suppose the array of values A is a fixed point of the operator F. What can you conclude about A?”. Of course, this could be asked of operators with 0 fixed points (in which case, “You can conclude anything you want; this never actually happens”), or with multiple fixed points (in which case, “You can’t conclude definitively what A is, but you can narrow it down to the following possibilities”). But, in this case, it’s asked using an operator with a unique fixed point.