Transcript Logic Puzzles: Origins, problems, and some yet unsolved.

Logic Puzzles:
Origins, problems, and games
GSS October 1, 2012
Peder Thompson
Origins of logic & logic puzzles
• Prehistoric development of formal
logic in China, India, Greece.
• Aristotle: looking for relations of
dependence which characterize
deductions. He distinguished the
validity of conclusions drawn from
assumptions from the truth of the
premises.
• Charles Dodgeson (Lewis Carroll):
The Game of Logic
• Raymond Smullyan
• Saul Kripke, 1960s, modal logic
Knights and knaves
• William and Richard are residents of the island of
knights and knaves.
• Question: William says “we are both knaves”
– Who is what?
• Solution: William is a knave:
– William can’t be a knight, since then he would be
lying, so William is a knave. But that means he is not
telling the truth, so they cannot both be knaves,
hence Richard is a knight.
Syllogisms
• Syllogisms: Given a list of premises, what can
be deduced from them?
– Example:
• Major premise: All humans are mortal.
• Minor premise: Socrates is human.
• Conclusion: Socrates is mortal.
– Another example:
• Major premise: All horses have hooves.
• Minor premise: No humans have hooves.
• Conclusion: Some humans are not horses.
More on syllogisms
• The conclusion only depends on the premises.
• Untrue conclusions can be drawn if the syllogism is not
used correctly:
– For example:
• Some animals can fly.
• All pigs are animals.
• Therefore, some pigs can fly.
– (Is there a way we can fix this? By either changing the hypothesis or conclusion?)
• Some supposed “syllogisms” are really just wordplay or
incorrect usage:
• Nobody is perfect.
• I am nobody.
• Therefore, I am perfect.
A (logical?) problem
• A man is stranded on an island covered in forest. One day, when the
wind is blowing from the west, lightning strikes the west end of the
island and sets fire to the forest. The fire is very violent, burning
everything in its path, and without intervention the fire will burn
the whole island, killing the man in the process. There are cliffs
around the island, so he cannot jump off. How can the man survive
the fire? (There are no buckets or any other means to put out the
fire)
A (not-so-good) Solution:
• The man picks up a piece of wood and lights it from the
fire on the west end of the island. He then quickly
carries it near the east end of the island and starts a
new fire. The wind will cause that fire to burn out the
eastern end and he can then shelter in the burnt area.
• (The man survives the fire, but dies of starvation, with
all the food in the forest burnt.)
That was annoying…
An example
• A frog is at the bottom of a 30 meter well. Each day he
summons enough energy for one 3 meter leap up the
well. Exhausted, he then hangs there for the rest of the
day. At night, while he is asleep, he slips 2 meters
backwards. How many days does it take him to escape
from the well?
• Note: Assume after the first leap that his hind legs are
exactly three meters up the well. His hind legs must
clear the well for him to escape.
• Solution: 28 days. Each day he makes it up another
meter, and then on the twenty seventh day he can leap
three meters and climb out.
Tic Tac Toe
• Can you place six X's on a Tic Tac Toe board
without making three-in-a-row in any
direction?
Try this one:
• Can you connect all nine dots with only four
straight line segments without losing contact
with the paper while drawing?
Some unsolved “logic” problems
• Grimm’s Conjecture:
– Grimm's conjecture states that to each element of a set of
consecutive composite numbers one can assign a distinct prime
that divides it.
• For example, for the range 242 to 250, one can assign distinct primes
as follows:
• 242: 11 243: 3 244: 61 245: 7 246: 41 247: 13 248: 31 249:
83 250: 5
• ABC Conjecture:
– Shinichi Mochizuki of Kyoto University?
• Twin Primes Conjecture
– The twin primes conjecture states that there are an infinite
number of pairs of primes of the form 2n-1, 2n+1. That is, they
differ by 2; for example, 41 and 43.
Contest time!
• Divide into small groups.
• These problems all have logical solutions (no
“trick questions”)
• Group with most points wins.
Questions
• Question 1:
• How many steps are required to break an m x
n bar of chocolate into 1 x 1 pieces? You can
break an existing piece of chocolate
horizontally or vertically. You cannot break
two or more pieces at once (so no cutting
through stacks).
• Question 2:
• A man is caught on the King's property. He is
brought before the King to be punished. The
King says, "You must give me a statement. If it
is true, you will killed by lions. If it is false, you
will be killed by trampling of wild buffalo.” But
in the end, the King has to let the man go.
What was the man's statement?
• Question 3:
• Four adventurers (Alex, Brook, Chris and
Dusty) need to cross a river in a small canoe.
The canoe can only carry 100kg. Alex weighs
90kg, Brook weighs 80kg, Chris weighs 60kg
and Dusty weighs 40 kg, and they have 20kg
of supplies. How do they get across?
Quick Round
• Fastest answer wins:
• Question 4:
• There are five gears connected in a row, the
first one is connected to the second one, the
second one is connected to the third one, and
so on. If the first gear is rotating clockwise
what direction is the fifth gear turning?
Tricky?
• Question 5:
• Two fathers took their sons fishing. Each man
and son caught one fish, but when they
returned to camp there were only 3 fish. How
could this be? (None of the fish were eaten,
lost, or thrown back.)
• Question 6:
• At a restaurant, how could you choose one
out of three desserts with equal probability
with the help of a coin?
• Question 7:
• A blind-folded man is handed a deck of 52
cards and told that exactly 10 of these cards
are facing up. How can he divide the cards
into two piles (possibly of different sizes) with
each pile having the same number of cards
facing up?
• Question 8:
• What mathematical symbol can be put
between 5 and 9, to get a number bigger than
5 and smaller than 9?
• Question 9:
• What’s wrong with the following “proof”?
Question 10:
• You are travelling down a country lane to a distant
village. You reach a fork in the road and find a pair of
identical twin sisters standing there. One standing on
the road to village and the other standing on the road to
neverland (of course, you don't know or see where each
road leads). One of the sisters always tells the truth and
the other always lies (of course, you don't know who is
lying). Both sisters know where the roads go. If you are
allowed to ask only one question to one of the sisters to
find the correct road to the village, what is your
question? (So explain why your question will make sure
to give you the correct road to the village.)
That’s all folks!
• Thanks!