Problem Solving

Reasoning

• Minesweeper
  • change of paradigm (something can be done)
  • understanding definitions
  • implication, proof, proof by cases, proof by contradiction
  • prove that you must guess
  • What is a proposition/theorem
• Paint By Numbers
  • Describe a theorem here, a strategy
• fill in the digits (ie send+more=money), algebraf
• Apples and Oranges puzzle:
  • You have three boxes of fruit. One contains just apples, one contains just oranges, and one contains a mixture of both. Each box is labeled -- one says "apples," one says "oranges," and one says "apples and oranges." However, it is known that none of the boxes are labeled correctly. How can you label the boxes correctly if you are only allowed to take and look at just one piece of fruit from just one of the boxes?
• Three hats puzzle:
  • Three men, members of a safari, are captured by cannibals in the jungle. The men are given one chance to escape with their lives. The men are lined up and bound to stakes such that one man can see the backs of the other two, the middle man can see the back of the front man, and the front man can't see anybody. The men are shown five hats, three of which are black and two of which are white. Then the men are blindfolded, and one of the five hats is placed on each man's head. The remaining two hats are hidden away. The blindfolds are removed. The men are told that if just one of the men can guess what hat he's wearing, they may all go free. Time passes. Finally, the front man, who can't see anyone, correctly guesses the color of his hat. What color was it, and how did he guess correctly?
• Discrete reasoning puzzles

Quantifiers

• Chess Puzzles
• How do you say 'There are an infinite number of primes'? How do you prove it?

Proof

• Prove that area of A is the same as the area of B
• Prove that every diameter based triangle is a 90 degree triangle
• Irrational Numbers: Consider the following proof

  The proof that square root of 2 is irrational:  Let's suppose √2 was a rational number.  Then we can write it √2  = a/b where a, b are whole numbers, b not zero.  We additionally make it so that this a/b is simplified to the lowest terms, since that can obviously be done with any fraction. It follows that 2 = a2/b2,  or  a2 = 2 * b2.  So the square of a is an even number since it is two times something.  From this we can know that a itself is also an even number.  Why?  Because it can't be odd; if a itself was odd, then a * a would be odd too.  Odd number times odd number is always odd.  Check if you don't believe that! Okay, if a itself is an even number, then a is 2 times some other whole number, or a = 2k where k is this other number.  We don't need to know exactly what k is; it won't matter.  Soon is coming the contradiction: If we substitute a = 2k into the original equation 2 = a2/b2, this is what we get: 2 = (2k)2/b2 2 = 4k2/b2 2*b2 = 4k2 b2 = 2k2. This means b2 is even, from which follows again that b itself is an even number!!! WHY is that a contradiction? Because we started the whole process saying that a/b is simplified to the lowest terms, and now it turns out that a and be would both be even. So √2 cannot be rational.

• Modify the above proof to prove that √3 is irrational
• Modify the above proof (in the same way) to prove that √4 is irrational

Algorithms

• Steak and grill problem:
  
  Steaks take 10 minutes to cook (5 min/side), each grill holds 1 steak at a time.
• Chess
  • Checkmate problems (start at the end): 3 queens, 2 queens, 1 queen, queen+rook, 2 rooks, 2 knights, bishop+knight, bishop+bishop, rook+bishop, rook+knight
  • Write down algorithm for a few of the above
  • Have your classmates carry out your algorithm
  • Is your algorithm correct?
• Untangling the circle
• Elephant Spin Out puzzle
• 20 numbers puzzle (No Crunch)
  • state simple problem and solve
  • write up algorithm as a subroutine
  • have other group carry this out
  • proof of correctness
  • Under what conditions will this subroutine work? Under what conditions will it not work?
  • Can this be used to 'almost' solve the puzzle?

Algorithms Again!

• Straight edge and compass constructions
  • Construct a perpendicular bisector to a given line segment
  • Given line segment x construct 4x, 1/2 x
  • construct an equilateral triangle (60, 60, 60)
  • construct an isosceles triangle (90, 45, 45)
  • given any triangle, construct a largest square inside, based on one side of the triangle
  • given two circles, find a common tangent
• Turing Machines
  • Alan Turing
  • Turing Machines
  • Connection to modern computing (Java)
  • Definitions: accepting, rejecting computations, computing a function
  • Hello Turing Machine Description
  • Exercises:
    • Hello World
    • Recognize even length strings
    • Binary numbers representing even numbers
    • recognize 0^n 1^n
    • palindromes (over tape alphabet {0,1})
    • add 1 in unary
    • add 1 in binary
    • add two binary numbers
  • Turing Machine Simulator (local download) from Binghamton
  • A turing machine simulator(Java applet), and another one, JFlap, And another one JCT, Another Java applet

Problem Solving

• A philosophy of Problem Solving
• 1-50000 puzzle
  Extensions?
• Mastermind
  State some related problems, describe how they are related to the original problem.
• Learning Chess: Some related problems
  • Smaller board, fewer pieces
  • Checkmate problems in the algorithms section above
• Three jugs puzzle: There are three water jugs, which can hold 8, 5 and 3 gallons of water respectively. The first jug is full, and the other two are empty. It is necessary to divide the water into two equal portions, that is, to put exactly four gallons into both the 8 and 5 gallon jugs. The only operation allowed is to pour some or all of the contents of one jug into another.
  Can the water be divided into two equal portions? How?
• Working backwards: Rush hour puzzle.
• Crossing a river
  • Fox Duck and Corn
    
    The farmer is taking his fox, duck and corn to market. He is currently stuck on the left bank of a major river. The good news is that he has a boat available. The bad news is that the boat will only hold him and one other item for each crossing.
    
    He dare not leave the duck alone with the corn (corn would get eaten) or the duck alone with the fox (duck would get eaten). Also the farmer knows from prior experience that he cannot leave the corn alone on the right bank of the river since a large flock of crows is waiting to devour it.
    
    Can you help the farmer get everything across the river safely?
  • The Beatles have to be at a concert across the river in 17 minutes. The problem is that the bridge across the river is very weak and is strong enough to hold only two people at a time (only two people can cross at a time). They have only one flashlight and anybody crossing the river must have the flashlight at all times. John can cross the bridge in 1 minute, Paul needs 2 minutes, George needs 5 minutes and Ringo needs 10. Can they make it to the concert in time? If so, how?
    
    
  • Two men and two women stand on the banks of the river Calledin. They would like to get on the other side with a boat. Unfortunately, the boat can only carry as much as two people.
    
    The 4 people can not cross the river at the same speed. One women is able to cross it in 5 minutes and the other in 10. The men can cross it in 20 and 25 minutes. (This means that if a men is in the boat, the minimum cross time - one way - will be 20 minutes.)
    
    How can they cross the river in one hour ?

References

• Binary Arts
• Curious Numbers
• rec.puzzles archive
• Puzzles
• AMS
• uticpc
• Neto's programming contests page
• Chess and some Chess Puzzles, and some more Chess puzzles Chesscorner.com
• http://www.HomeschoolMath.net