Interesting Graphs and Puzzles for Problem-Solving Enthusiasts
Explore various scenarios involving graph theory and puzzles like handshakes at a party, a tricky river crossing situation with multiple constraints, a jug measuring problem, and the classic Rubik's cube challenge. Also, ponder over a cash exchange problem faced by a group dining at a restaurant. These thought-provoking scenarios will surely engage problem-solving enthusiasts.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Graphs and Trees More examples on Total degree of a graph Applications of Graphs
Handshakes at a party Mike and Katie go to a dinner party with four other couples; each person there shakes hands with everyone he or she doesn t know. Later, Mike does a survey and discovers that every one of the nine other attendees shook hands with different number of people. How many people did Katie shake hands with?
The whim of three girls Three girls, each with her father, go hiking. They come to a river. One boat, able to carry two persons at a time, is at their disposal. Crossing would be simple, except for the girls whim: none is willing to be in the boat or ashore with one or two strange fathers unless her own father is present too. How do they all get across?
Jugs example Two jugs A and B have capacities of 3 quarts and 5 quarts, respectively. Can you use the jugs to measure out exactly 1 quart of water, while obeying the following restrictions: You may fill either jug to capacity from a water tap; You may empty the contents of either jug into a drain; You may pour water from either jug into the other.
Rubiks cube Rubik's cube is a deceptively simple-looking puzzle. It is a cube with nine tiles on each face. In its solved state, each of the sides is made up of tiles of the same color, with a different color for each side. Each of the tiles is actually part of a small cube, called a "cubie." Each face of the cube (made up of nine cubies) can be rotated. The mechanical genius of the puzzle is that the same cubie can be rotated from multiple sides. A corner cubie can move with three sides; an edge cubie moves with two sides. The basic goal is to take a cube whose sides have been randomly rotated and figure out how to get it back to the initial solved state.
Rubiks cube rubcub_lg Rotations rubix_cube Solved state
Cash exchange problem (by Michael Baker) Suppose a group of 6 people are going out to dinner at a restaurant. They all place their orders to the waitress but forget to tell her to put them all on separate checks. However, they all want to pay for their bills individually and without causing the hassle for the waitress to go back and split the checks. Unfortunately, they don t all have exact change. Is it possible for the 6 people to redistribute money among themselves so that they each pay exactly what they owe, without the waitress bringing back change?
Cash exchange problem (cont.) The following chart shows what their bill is and what type of money they have. Number of bills of each type People Due $1 $5 $10 $20 1 $16 0 0 2 0 2 $12 5 1 0 1 3 $17 3 0 0 1 4 $17 0 2 1 0 5 $15 0 1 0 1 6 $13 4 0 1 0
