BJC AP CSP Unit 5 Lab 4*

BJC AP CSP Unit 5 Lab 4

Unsolvable & Undecidable Problems

(Get your pen/cils out)

Multiple Choice

There's an island with two large families. One family (unlike normal people) can tell only the truth. This Truth-teller family can't ever make false statements, even by mistake. The other family, the False-Tellers, is just as reliable: they can't make true statements ever.

You meet two of its people, Diego and Zoey. Diego says, "Zoey and I are from the same family." Which family is Zoey from?

Don't spoil it for others!

• The Truth-Tellers

• The False-Tellers

• Could be either

• Not possible

Diego said, "Zoey and I are from the same family."

• Diego might be a Truth-Teller. Which, according to Diego, means Zoey is a Truth-Teller.

• Diego might be a False-Teller. Which means he lied, so Zoey is from a different family, the Truth-Teller.

Proof by Contradiction:

A two-step proof that something is false, by...

• assuming that it's true

• showing how the assumption leads to the impossible (a logical contradiction)

Diego said, "Zoey and I are from the same family."

We know Zoey is a Truth-Teller.

• Diego might be a Truth-Teller. Which, according to Diego, means Zoey is a Truth-Teller. No contradiction.

• Diego might be a False-Teller. Which means he lied, so Zoey is from a different family, the Truth-Teller. No contradiction.

Diego said, "Zoey and I are from the same family."

Assumption: Zoey is a False-Teller.

• Possibility 1: Diego is a Truth-Teller. Which, according to Diego, means Zoey is a Truth-Teller. Contradiction.

• Possibility 2: Diego is a False-Teller. Which means he lied, so Zoey is from a different family, the Truth-Teller. Contradiction.

• If all possibilities lead to contradictions, one of the assumptions must be wrong. Therefore, Zoey may be a Truth-Teller.

Multiple Choice

Same scenario with the Truth-tellers and the False-Tellers, and you meet two of its people, Diego and Zoey.

Diego says, "Zoey and I are from the same family." Which family is Diego from?

• The Truth-Tellers

• The False-Tellers

• Could be either

• Not possible

You meet two people, Diego & Zoey, who's either a Truth-teller or False-teller.

Diego says, "Zoey and I are from the same family." Which family is Diego from?

• If Zoey is a Truth-teller, Diego would say that no natter what. (Work it out for yourself why that is. Hint: Assume Diego is from one of the families & see where that leads)

• If Zoey is a False-teller, Diego wouldn't say that whether he's a Truth-teller or not.

• So, we can't determine who Diego is.

Multiple Choice

Imagine you meet someone named Derek on the island and you ask him if he's from the Truth-teller family. What does he answer?

• Yes

• No

• Could be either (not enough info)

• Universe explodes

Imagine you meet someone named Derek on the island and you ask him if he's from the Truth-teller family. What does he answer?

• Derek might be a Truth-Teller, which means he'd answer yes.

• Derek might be a False-Teller, which means the right answer is no. Since he always lies, he'd answer yes.

Multiple Choice

Imagine you meet Fabby on the island and you ask them if they're from the False-teller family. What do they answer?

• Yes

• No

• Could be either (not enough info)

• Universe explodes

Imagine you meet Fabby on the island and you ask them if they're from the False-teller family. What do they answer?

• Fabby might be a Truth-Teller, which means he'd answer no.

• Fabby might be a False-Teller, which means the right answer is yes. Since he always lies, he'd answer no.

Multiple Choice

"The statement I'm making right now is false."

That statement was ...

• Provably True

• Provably False

• Undecidable

  (There's no algorithm we can follow to determine the statement's truthfulness.)

• Self-Contradictory (paradoxical/nonsensical)

Open Ended

Challenge: What true/false question(s) can you ask an islander to determine which family they're from?

Don't spoil it for others!

Assignments

• APClassroom.collegeboard.org: "5.4 Undecidable & Random", 10 Q's

• Albert.io: "Robots", 7 Q's

• Albert.io: "5.4 Undecidable & Random", 13 Q's