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: There are numerous answers to this question, but asking the native, "Which path leads to your village?" is probably the simplest. 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: We must enumerate the numbers 1 through 31. 1 and 2 must be on each of the dice so that the combinations 11 and 22 can be produced. Since neither die can have all of the digits 1 through 9, each die must also have the digit 0. This leaves three faces remaining on each die. We can assign 3, 4, 5 to the remaining faces on one die and 6, 7, 8 to the remaining faces of the other. Since 6 can double is an upside-down 9, and since no day of the month requires both a 6 and a 9 simultaneously, we can substitute one for the other. 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: Since no box is labeled correctly, the box labeled "Apples and Oranges" must either be completely full of apples or completely full of oranges. By removing a fruit from that box, its contents can be determined, and determining the contents of the other two boxes follows easily. 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: It is important to note that two pairs of gloves have four surfaces. 1. Surgeon A puts on glove pair #1, then puts on glove pair #2, and operates. 2. Surgeon B uses glove pair #2 and operates. 3. Surgeon C takes glove pair #1, turns them inside-out, then puts on glove pair #2, and operates. 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: The upper-left and lower-right squares are both white; with them removed, the board has more black squares than white. Since each domino must cover exactly one white square and one black square, it is impossible to tile this chessboard with dominoes. 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: Ten. Only switches that are hit an odd number of times will be on. The i-th switch is hit by the j-th ball if and only if j divides i. Thus, the i-th switch is hit an odd number of times if and only if i has an odd number of factors. Therefore i must be a square number. There are exactly 10 square numbers from 1 through 100. 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: 9, 2, 2. Since the product of the children's ages is 36, we have the following possibilities: 36, 1, 1 18, 2, 1 12, 3, 1 9, 4, 1 9, 2, 2 6, 6, 1 6, 3, 2 4, 3, 3 Since the sum of the children's ages is the same as the street address and since the census taker knows the address, the only reason he'd need still more information is if more than one set of ages sum to it. Therefore, the children's ages are either 9, 2, 2 or 6, 6, 1. Since the oldest child likes chocolate ice cream, that means that one child is older than the other two, and thus the ages must be 9, 2, 2. 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: Since the rear person doesn't know what color hat he's wearing, you and the middle person cannot both be wearing red hats. Therefore you and the middle person can either both be wearing white hats or only one of you can be wearing a red hat. Since the middle person doesn't know what hat he's wearing, you cannot be wearing a red hat. Thus, you must be wearing a white hat. 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: If there are N villagers with blue eyes, each blue-eyed villager will jump into the volcano on the Nth night afterward. We can prove this by induction: Suppose only one villager has blue eyes. When he sees that no one else in the village has blue eyes, he can deduce that he has blue eyes, and he will jump into the volcano that night. Assume that N villagers have blue eyes and would jump into the volcano on the Nth night. Based on this assumption, if there were instead N+1 villagers with blue eyes, would they then jump into the volcano on the the N+1st night? Since each of the blue-eyed villagers would see N other blue-eyed villagers, each would expect these N to jump into the volcano on the Nth night and would not jump into it himself. Hence, none of these villagers would jump into the volcano on the Nth night. On the N+1st day, when they each see that the N other blue-eyed villagers is still alive, each could then deduce that he is himself blue-eyed, and each of the blue-eyed villagers would jump into the volcano that night. 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: Four. Since no person could his/her own hand nor the hand of his/her spouse, the maximum number of people with whom a person could have shaken hands is 8. Since each of the nine people gave a different answer, one person must have shaken hands with 0 people; another must shaken hands with 1 person; another, 2; another, 3; and so on, through 8. The person who shook hands with 8 people shook hands with everyone except him-/her-self and his/her spouse. Therefore, the only person who could have made 0 handshakes must be the spouse. Similarly, the person who shook hands with 7 people must be married to the person who shook hands with only 1 person. We can deduce that a person who shook hands with N people must be married to the person who shook hands with (8 - N) people. Therefore, the person who shook hands with 4 people must be married to someone who also shook hands with 4 people. Since everyone other than yourself shook hands a unique number of times, this couple must be you and your spouse. Thus, your spouse must have shaken hands with 4 people. 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: Light both ends of the first string and one end of the second string simultaneously. When the first string has completed burning, light the remaining end of the second string. When the second string has completed burning, 45 minutes have elapsed. 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: Cut along a line that passes through the centers of both rectangles. Any line that passes through the center of a rectangle divides it into two parts of equal area. Thus, a line that passes through the centers of both rectangles must divide each of the them into two parts of equal areas. 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: Turn two switches on for a long time, and turn the second one off. Turn one of the remaining switches on, and check the room. If the lightbulb is on and hot, it is controlled by the first switch. If the lightbulb is off and hot, the second switch. If the lighbulb is on and cold, the third switch. Otherwise, the lightbulb is off and cold and is controlled by the fourth switch. 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: Two orcs go across, one orc returns. Two orcs go across, one orc returns. Two hobbits go across, one hobbit and one orc return. Two hobbits go across, one orc returns. Two orcs go across, one orc returns. Two orcs go across. 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: The 1-minute and 2-minute people cross. The 1-minute person returns. The 5-minute and 10-minute people cross. The 2-minute person returns. The 1-minute and 2-minute people cross. 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: 1 kg, 3 kg, 9 kg, 27 kg. These values correspond to powers of 3. 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: Divide the balls into three groups, three balls in each. Weigh the one group against another. If one group weighs more than the other, obviously the heavy ball is in the heavier group. If they weigh the same, the heavy ball is in the unweighed group. Using the balls in the heavy group, weigh one ball against another. If one ball weighs more than the other, obviously the heavy ball is the heavier one. If they both weigh the same, the heavy ball is the unweighed ball. 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: Let X > Y denote X weighs more than Y Let uppercase letters denote balls that are unknown Let lowercase letters denote balls that are known to be normal Balls: ABCD EFGH IJKL 1. ABCD vs. EFGH if (ABCD == EFGH) // IJKL is odd 2. IJ vs. aK if (IJ == aK) // L is odd 3. a vs L if (a == L) [impossible] if (a > L) L is light if (a < L) L is heavy if (IJ > aK) // IJ is heavy or K is light 3. I vs J if (I == J) K is light if (I > J) I is heavy if (I < J) J is heavy if (IJ < aK) // IJ is light or K is heavy 3. [...] if (ABCD > EFGH) // ABCD is heavy or EFGH is light 2. ABE vs CFi if (ABE == CFi) // D is heavy or GH is light 3. [...] if (ABE > CFi) // AB is heavy or F is light 3. [...] if (ABE < CFi) // C is heavy or E is light 3. a vs C if (a == C) E is light if (a > C) [impossible] if (a < C) C is heavy if (ABCD < EFGH) 2. [...] --------------------------------------------------------------------------- Programming Q: How can you swap the contents of two registers without using any additional memory? A: In pseudo-assembly: $t0 <- $t0 xor $t1 $t1 <- $t0 xor $t1 $t0 <- $t0 xor $t1 In C: a ^= b; b ^= a; a ^= b; 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: No. <expr>++ evaluates <expr> only once. This is problematic when there are side-effects from evaluation. For example, consider the following function: int* foo(int* x, int* y) { *y = *y + 1; return x; } Now compare the value of a variable y after int x = 0, y = 0; (*foo(&x, &y))++; with: int x = 0, y = 0; *foo(&x, &y) = *foo(&x, &y) + 1; 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: No, for and while loops are not always equivalent. If there is a continue statement in <body>, the for loop will always perform the increment before proceeding to the next iteration, whereas the while loop will not. Q: Is it theoretically possible to devise a lossless compression algorithm that is guaranteed to compress any file by at least 1 bit? A: No. If such an algorithm existed, we could continuously recompress compressed files and eventually obtain 0-bit files! Here's the more formal proof: Suppose there exists a lossless algorithm that can compress any file by exactly 1 bit. Take 2^n distinct files, each of n bits, and compress each of them. We now have 2^n distinct files represented using only n-1 bits. By the pigeonhole principle, at least two of the compressed files must be identical. Therefore these files cannot be decompressed back into distinct files, and the algorithm cannot be lossless. 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: In each node, store the data field as you normally would. Take the addresses of the previous node and the next node, XOR them together, and store the result in the pointer field. As you traverse the list, you can keep track of the last node from which you came. Taking the XOR of that address and the current pointer field will give you the next address in your current traversal direction. [collected from various sources] ___________________________________________________________________________ page updated: 2000-11-25 home copyright (c) 2000 james d. lin |