General Q: You are on an island where there are two villages. The people of one village always tell the truth, and the people of the other always lie. You arrive at a fork in the road; one path leads to village of the truth-tellers, the other leads to village of the liars. You don't know which path is which. There is a native there, but you do not know from which tribe he is. What one question can ask the native to determine the correct path to the truth-telling village? A: Solution Q: You have two ordinary dice. On each face of each die is a base-10 digit. How can you assign a digit to each face such that the two dice together can enumerate every possible day of a month? For example, to represent the first day of a month, you'd need to have a 0 on one die and a 1 on the other to produce the combination 01. You must use both dice for every date. A: Solution Q: You have three boxes: one contains apples, one contains oranges, and one contains both apples and oranges. The labels on the boxes are accidentally mixed up, and each of the boxes is labeled wrong. You are allowed only to remove one fruit from one box. You cannot look into the box. How can you determine the correct contents of each box? A: Solution Q: Three surgeons must take turns operating on a patient, but they only have two pairs of surgical gloves among them. Each of these four people has a different, highly communicable skin disease. How can the surgeons operate without anyone infecting anyone else? The surgeons must use both hands while operating. A: Solution Q: You are given a chessboard with the upper-left and lower-right squares removed. Is it possible to tile this chessboard with 2x1 dominoes perfectly? Prove your answer. A: Solution Q: You have 100 light switches in a row. Each switch is connected to a light bulb. All the bulbs are initially off. You throw a ball at the set of switches, and as it bounces, it hits and flips every switch. You bounce a second ball, and it hits and flips every other switch. You bounce a third ball, and it hits and flips every third switch, and so on. How many light bulbs will be on after you bounce 100 balls? A: Solution Q: A census taker goes to a home, a woman answers the door, and he asks her a few questions. "Do you have any children?" "Yes," she says, "I have three." "What are their ages?" "Well, the product of their ages is 36," she replies enigmatically. "I'm sorry, but that's not enough information," says the census taker. "Well, the sum of their ages is the same as our street address." The census taker turns his head and looks at the number on the house, thinks for some time and responds, "I'm sorry, but that's still not enough information." "Well, my oldest child likes chocolate ice cream." The census taker thanks the woman and leaves. How old are each of the children? A: Solution Q: You and two other infallible logicians are standing in a line, all facing the same forward. You are at the front of the line and cannot see the other two people. The middle person can only see you, and the rear person can see both of you. A salesman comes by selling hats. He has a 3 white hats and 2 red hats. Each of you buys a hat from him, and he puts a random hat on each of your heads. None of you can see what color hat you are wearing. The salesman then says, "If any one of you can determine what color hat is on your own head, all of you can have the hats for free." He asks the rear person, "What color hat are you wearing?" The rear person responds, "I don't know." He asks the middle person, "What color hat are you wearing?" He also responds, "I don't know." What color hat are you wearing? A: Solution Q: There is a small village on an island in which the natives have either blue eyes or brown eyes. The village has no mirrors or reflective objects on it, and by law no villager can reveal another villager's eye color. By tradition, any villager who discovers he/she has blue eyes must jump into a volcano that night. One day a group of explorers visits the village. Before they leave, they inform the villagers that at least one of them has blue eyes. Assuming all the villagers are infallible logicians and that every day each villager encounters all other villagers, what happens? A: Solution Q: You and your spouse go to a party with four other couples. At this party, people shake hands, but no one shakes his/her own hand nor the hand of his/her spouse. After the party, you ask each of the other nine people with how many people they shook hands, and each gives you a different answer. With how many people did your spouse shake hands? A: Solution Q: You are given two strings. Each is known to burn completely in exactly 1 hour. The strings are non-homogeneous, so they don't burn uniformly (90% of one string could burn in 10 minutes while the remaining 10% could burn in 50 minutes). Using just these two strings and a lighter, how can you measure out 45 minutes? A: Solution Q: You are given a red rectangle. Pasted on top of the red rectangle is a smaller, blue rectangle. The blue rectangle can be placed in any position and with any orientation, so long as it is totally within the bounds of the red one. Given a straight edge and a knife, how can you cut the combined rectangles into two parts such that each part has the same area of red and blue as the other part? A: Solution Q: You are in a room with four light switches. Only one of them controls a lightbulb in another room, which is not visible from the switches. How can you determine which switch controls the lightbulb if you are only able to check the lightbulb once? A: Solution Q: There are 3 orcs and 3 hobbits on one side of a river. They wish to cross, but they only have one boat. The boat can only seat two people (including the person manning the boat). Including the person in the boat, if there are more orcs than hobbits on a side of the river at any time, the orcs will overpower the hobbits and eat them. There always has to be someone manning the boat for each trip across, and all the hobbits must survive. How can this be done? A: Solution Q: It is night-time, and four people must cross a bridge to avoid being eaten by a grue. They only have one flashlight among them. The bridge is rickety, so a maximum of only two people can cross at a time. Any party who crosses must have the flashlight with them. The flashlight must be carried back and forth. Each person walks at a different speed: one person takes 1 minute to cross; another person takes 2 minutes; another, 5; another, 10. When two people cross together they walk at the slower man's pace. How can the four people cross in 17 minutes? A: Solution Q: A particular butcher can weigh meats from 1 kg through 40 kg. He has a balance and four weights. What are the weights? A: Solution Q: You are given 9 balls and a balance. Each ball weighs the same as the others, except for one, which is known to be heavier than the rest. The balls are otherwise indistinguishable from each other. Using the balance only twice, how can you determine which ball is the heavy one? A: Solution Q: You are given 12 balls and a balance. Each ball weighs the same as the others, except for one. The balls are otherwise indistinguishable from each other. Using the balance only three times, how can you determine which ball is the odd one and if it's lighter or heavier than the rest? A: Solution --------------------------------------------------------------------------- Programming Q: How can you swap the contents of two registers without using any additional memory? A: Solution Q: In ANSI C, is the following statement <expr>++; always equivalent to <expr> = <expr> + 1; where <expr> is any legal left-hand-side expression? A: Solution Q: In ANSI C, is every for loop equivalent to a while loop? In other words, can we always rewrite: for (<init>; <test>; <increment>) { <body> } as: <init>; while (<test>) { <body> <increment>; } Why or why not? A: Solution Q: Is it theoretically possible to devise a lossless compression algorithm that is guaranteed to compress any file by at least 1 bit? A: Solution Q: You want to create a doubly-linked list in C that you can traverse in either direction in a constant amount of time per step. Each node, however, can only occupy 64 bits--32 bits for the data, and 32 bits for a pointer to another node. How can this be done? Nodes possibly could be allocated in random locations in memory, at the whims of malloc. You may not allocate additional memory dependent on the length of the list. You may allocate additional memory, however, provided that it is a constant amount. Hint: This cannot be done in Java. A: Solution [collected from various sources] ___________________________________________________________________________ page updated: 2000-11-25 home copyright (c) 2000 james d. lin |