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?

• 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."

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

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.

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

Multiple Choice

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

• Yes

• No

• Could be either (not enough info)

• Universe explodes

Multiple Choice

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

That statement was ...

• Provably True

  ("Zoey is a Truth-teller.")

• Provably False

  ("Zoey is a False-teller.")

• Undecidable

  ("Diego is a Truth-teller.")

• Self-Contradictory (nonsensical)

Challenge:

What T/F question can you ask an islander to determine which family they're from?

Draft it in the chat, and press [Enter] when instructed to do so.

Don't give away how you come up with the question.

Open Ended

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

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