Brain Teaser(s)

Error message

Deprecated function: implode(): Passing glue string after array is deprecated. Swap the parameters in drupal_get_feeds() (line 394 of /var/www/pied-piper.ermarian.net/includes/common.inc).

Pages

Author	Topic: Brain Teaser(s)
Dintiradan Guardian Member # 6670	written Friday, February 9 2007 12:22 Profile Homepage #0 I was inflicted with this in my algorithms assignment a week ago, and there's no reason why you shouldn't be as well. (Yes, yes, it's handed in now. Shesh.) quote: Suppose we have n identical electronic chips that are capable of testing each other (e.g., microprocessors) using a test setup (a hardware device, and an accompanying diagnostic program) that can test two chips at a time. When the testing device is loaded, each chip tests the other, and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the answer of a bad chip cannot be trusted. Thus, the four possible outcomes of a test are as follows: Now, consider the problem of developing an efficient recursive algorithm to find a single good chip from among n chips, assuming that more than n/2 of the chips are good. To achieve the required efficiency, at the end of each call, the recursive algorithm should reduce a problem of a given input size, say n′ chips, to a problem of size no more than (n′/2) + ǫ, where ǫ is a small constant (that is, the reduced problem has nearly half the input size) by performing no more than ⌊n′/2⌋ pairwise tests. Or, rewritten in more classical terms: quote: You are stranded on an island inhabited by Knights and Knaves. Knights always tell the truth, while Knaves give unreliable answers. You need to find a Knight to help you, and you know that there are more Knights than Knaves on this island. The only way you can possibly tell the identical Knights and Knaves apart is by putting them in pairs and having them say what their partner is. From their answers, how can you pick out at least one Knight from the islanders? Have fun. -------------------- Oh, yeah. It appears that my post count is now one thousand. Apparently, this is a big deal, or something. You're not allowed to congratulate me until you solve the problem. [ Wednesday, February 14, 2007 11:46: Message edited by: Dintiradan ] Posts: 1509 \| Registered: Tuesday, January 10 2006 08:00
Faint Piping of Two Demoniac Flutes Guardian Member # 5360	written Friday, February 9 2007 12:38 Profile #1 Congratulations on the post count. -------------------- May the fires of Undeath burn in your soul, and consume it. Posts: 1636 \| Registered: Wednesday, January 5 2005 08:00
Zeviz Nuke and Pave Member # 24	written Friday, February 9 2007 14:09 Profile Homepage #2 Congratulations on making 1000 funny signatures. You've proven that it's possible to have a posting gimmick that is fun without being annoying and never gets old. * spoiler of puzzle answer * Here is the answer to your puzzle: Take a chip and test it against every other chip. If there are at least forty nine chips that gave you good-good result, we know that your test chip is good, because all fifty chips can't be lying (there are at most forty nine bad chips). If there are only fourty eight or less chips that gave you good-good result, we know that all of them are bad, along with your test chip, because there have to be at least fifty one good chips out there. So take all the chips that indicated your current chip as bad, and go on to second iteration. For each iteration, you can stop as soon as you get (n-1 - 50) good-good results, because that's enough to prove that your test chip for that iteration is good. * end of spoiler * [ Friday, February 09, 2007 14:11: Message edited by: Zeviz ] -------------------- Be careful with a word, as you would with a sword, For it too has the power to kill. However well placed word, unlike a well placed sword, Can also have the power to heal. Posts: 2649 \| Registered: Wednesday, October 3 2001 07:00
Archmage Alex Skip to My Lou Member # 40	written Friday, February 9 2007 14:41 Profile Homepage #3 -------------------- Take the Personality Test! Deep down, you wish you were a stick figure. Posts: 1629 \| Registered: Wednesday, October 3 2001 07:00
Khoth Post Navel Trauma ^_^ Member # 67	written Friday, February 9 2007 16:48 Profile Homepage #4 Zeviz: Nice, but you use too many comparisons. with n chips, you're using n-1 comparisons (worst-case) per iteration (and n/2 best case). Not that I have a solution... -------------------- Barcoorah: I even did it to a big dorset ram. desperance.net - Don't follow this link Posts: 1798 \| Registered: Thursday, October 4 2001 07:00
Slarty Raven v. Writing Desk Member # 261	written Friday, February 9 2007 18:15 Profile Homepage #5 This was fun to work on. I think I've got the idea, but there is a major hiccup. For each iteration, 1. Perform [N/2] pairwise tests with each chip being involved in exactly one test. If there are an odd number of chips, one chip will be left out. 2. Throw out ALL chip pairs that do not produce mutual positive results. You are guaranteed to be left with a set of chips that meets the original criteria -- more good chips than bad chips. This works because mutual positives are produced by either good-good pairs or (sometimes) bad-bad pairs. With an even number of chips, it is impossible to have as many bad-bad pairs as good-good pairs. (Try it -- match up as many bad-good pairs as you can, and you will have one good-good pair left. If you make a bad-bad pair, you also have to make an extra good-good pair.) With an odd number of chips, the same thing is true except for the possibility of getting zero mutual positive pairs -- only good-bad pairs. In this case, the leftover chip is good and you are done. Special cases also need to be defined for when you have only 3 chips left (a mutual positive result means you need to throw out the leftover chip) and only 2 chips left (both must be good chips). In practice this will usually work since the bad-bad pairs will only produce mutual positive results 1 in 4 times. In theory, however, you could encounter the problematic result, in any given iteration, of ALL mutual positive results -- or even mostly mutual positive results, which is not efficient enough for the spirit of the specifications given. The solution is to set a quota of mutual positive pairs, equal to half the number of tests you can perform, rounded up. If this quota is full, put the untested chips aside and begin peforming tests that treat the tested chip pairs as whole units. (i.e. choose two chips from different tested pairs. If those chips test mutual positive, all four chips involved are either good or bad. If they don't test mutual positive, you either have 2 good and 2 bad chips, or 4 bad chips.) At first glance this is like a new iteration with less information -- you know you have somewhere between 2 and all the good chips, instead of somewhere between half and all of them. However, there are also two new outs. If all these chips test mutually positive, they must all be good, as there couldn't be that many bad chips in the round; so you are done. And if all the links are not mutually positive, you can toss the whole pile and just keep the ones you put aside. If some of the links are negative and some are positive, you are in a new situation as well, because you have thrown out some additional bad chips. This is significant because it means the maximum length a chain of mutually positive testing chips can have without all being good is reduced. Link together all the tested chips in this way, throwing out any pair-pairs (or pair-pair-pairs, etc.) that do not test mutually positive. So all the chips that remain are the same, either all good or all bad. You should have one test left. Take any of the tested chips and test it with one of the chips you already put aside. If the result is a mutual positive, they exceed the max number of bad chips you could have left, so they must all be good, and you are done. If it isn't, then... ...then you're stuck. And I'm stuck. So this isn't a solution after all. But it might have some of the right elements, so I'll leave this here for the sake of collaboration. -------------------- Slarty vs. Desk • Desk vs. Slarty • Timeline of Ermarian • G4 Strategy Central Posts: 3560 \| Registered: Wednesday, November 7 2001 08:00
moonear Infiltrator Member # 5410	written Friday, February 9 2007 20:35 Profile #6 I refuse to congratulate you. -------------------- "Dikiyoba ... is demon ... drives people mad and ... do all sorts of strange things." "You Spiderwebbians are mad, mad, mad as March hares." Posts: 687 \| Registered: Wednesday, January 19 2005 08:00
Amyth Shaper Member # 7472	written Friday, February 9 2007 21:32 Profile Homepage #7 Congrataulations. I won't do that algorithm, though. -------------------- I tried to think of something witty to put here. Needless to say, I failed. Posts: 2686 \| Registered: Friday, September 8 2006 07:00
Dikiyoba Councilor Member # 6600	written Friday, February 9 2007 21:58 Profile Homepage #8 You have Dikiyoba's congratulations, whether you want it or not. :P Posts: 4346 \| Registered: Friday, December 23 2005 08:00
Student of Trinity Electric Sheep One Member # 3431	written Friday, February 9 2007 23:18 Profile #9 Somehow an efficiency constraint makes me lose all interest in a problem (unless, of course, I really have to do it). It's as if one of the main things I like about puzzles is the freedom to explore a line of thought, and just keep going with it, wandering my way to an answer no matter how convoluted the path ends up being. Once I get an answer, I'm happy to try to tweak it to greater efficiency or clarity. But ensuring that the solution thus reached satisfies some global optimality constraint somehow disgusts me. Of course I know very well that efficiency matters a lot, especially with algorithms. It's just a job I'd really prefer to outsource. But here's a sort of dumb-ass solution based on extrapolation from the cases of 6 and 4 chips. For N chips, test N/2 pairs, and then just as Slarty suggested, discard all M pairs that do not show "double positive" results. That leaves us with (N/2)-M pairs, where M < N/2 because the number of discarded pairs M must be less than or equal to the number of bad chips, which we know is less than N/2. The maximum number of bad chips we can have left is less than N/2 - M, because there were less than N/2 bad in total, and we must have tossed out at least M bad ones. But these remaining bad chips must be in pairs. So we now have N/2-M pairs, of which B are both bad, and the rest both good; and B is less than N/4-M/2. So now the step I propose beyond Slarty: discard one chip from each of the remaining pairs, which are all either both-good or both-bad. This leaves a set of N/2 - M chips, of which no more than B < N/4-M/2 can be bad. This is the same problem we started with, except reduced by at least a factor of 2 in size. Rinse, lather, and repeat. What I haven't bothered about here is what happens if at any stage we have an odd number of chips. I bet that can be worked out by fiddling somehow. [ Saturday, February 10, 2007 00:58: Message edited by: Student of Trinity ] -------------------- We're not doing cool. We're doing pretty. Posts: 3335 \| Registered: Thursday, September 4 2003 07:00
Dintiradan Guardian Member # 6670	written Sunday, February 11 2007 14:39 Profile Homepage #10 By Zeviz: quote: Congratulations on making 1000 funny signatures. You've proven that it's possible to have a posting gimmick that is fun without being annoying and never gets old. Thanks. The current theme is comics and comedians, so they should stay funny for a little while longer yet. SoT's improvement on Slarty's method is the solution, as far as I know. Of course, the devil's in the details of figuring out the odd case. You're not out of the woods yet. I'll try round up some more brain teasers and such problems; no point letting a good thread go to waste. And I've decided that post #2000 will require people to solve the Travelling Salesman problem before congratulating me. -------------------- Rat: A man has a fox, a chicken, and some corn. He has to take them all across a river. He can only take one of the items at a time in his boat. However, if he leaves the fox alone with the chicken, the fox will eat the chicken. If he leaves the chicken alone with the corn, the chicken will eat the corn. What should he do? Pig: Buy a bigger boat. Rat: ... Pig: It's not that hard if you think about it. - Pearls Before Swine Posts: 1509 \| Registered: Tuesday, January 10 2006 08:00
Slarty Raven v. Writing Desk Member # 261	written Sunday, February 11 2007 20:17 Profile Homepage #11 Doh!!! It seems so obvious now. Nice one SoT. The odd case should be quite simple, shouldn't it? Tossing non-dual-positive pairs will always toss at least as many bad chips as good. The remaining dual-positive pairs plus the odd chip out will be at least 50% good chips, so tossing one from each pair will maintain that ratio. So you can just keep the odd chip out. The only circumstance in which it would require you to go to a new iteration with greater than 50% of the remaining chips is if you have an odd number and every single pair is dual-positive -- so, unless I'm mistaken, the "small constant" the problem asks for can be one. [ Sunday, February 11, 2007 20:23: Message edited by: Hashi the Drug-Sniffing Canine ] -------------------- Slarty vs. Desk • Desk vs. Slarty • Timeline of Ermarian • G4 Strategy Central Posts: 3560 \| Registered: Wednesday, November 7 2001 08:00
Dintiradan Guardian Member # 6670	written Wednesday, February 14 2007 11:51 Profile Homepage #12 Bump. Take a chessboard and cut it into two triangles and two trapezoids, then rearrange the pieces as below. Note that the top board has area 8 * 8 = 64, while the bottom board has area 13 * 5 = 65. Explain. -------------------- You guys go ahead. I'm just going to harvest his kidneys and I'll catch up. - Belkar (OotS #101) Posts: 1509 \| Registered: Tuesday, January 10 2006 08:00
Student of Trinity Electric Sheep One Member # 3431	written Wednesday, February 14 2007 12:22 Profile #13 I've seen this one explained before. If you don't want to hack up your chessboard, it will work with a piece of graph paper. -------------------- We're not doing cool. We're doing pretty. Posts: 3335 \| Registered: Thursday, September 4 2003 07:00
Garrison Agent Member # 2820	written Wednesday, February 14 2007 12:45 Profile #14 The "extra" square appears because the lines do not end up matching perfectly. I never realized this was possible with any standard chessboard, which rekindles my interest in this puzzle. To anyone baffled by this, notice that the angles added together in the rearrangement do not yield perfect right angles. -------------------- Thuryl: I mean, most of us don't go around consuming our own bodily fluids, no matter how delicious they are. ==== Alorael: War and violence would end if we all had each other's babies! ==== Drakefyre: Those are hideous mangos. Posts: 1415 \| Registered: Thursday, March 27 2003 08:00
wz. As Infiltrator Member # 3040	written Thursday, February 15 2007 11:13 Profile #15 It works nicely because 5, 8, and 13 are consecutive Fibonacci numbers. The trick would also work, for instance, with a 13x13 board rearranging to an 8x21 rectangle. For any n, F(n)^2 - F(n-1)F(n+1) = +/- 1. The rearranged rectangle has a stretched out parallelogram in the middle with area 1. Depending on which Fibonacci numbers you start with the rectangle will have either an extra unit or will be missing a unit. -------------------- 5.0.1.0.0.0.0.1.0... Posts: 508* \| Registered: Thursday, May 29 2003 07:00
Dryth'tor Lifecrafter Member # 7331	written Thursday, February 15 2007 14:34 Profile Homepage #16 quote: Originally written by Dintiradan: And I've decided that post #2000 will require people to solve the Travelling Salesman problem before congratulating me. In terms of getting rid of them, in terms of getting rid of them politely, or in terms of torturing them verbally? I could write a book on How To Get Rid Of Telemarketers. And I like your little Graemlin. [ Thursday, February 15, 2007 14:34: Message edited by: Sarasaphilia ] -------------------- You Shall Die Laughing: http://www.worfthecat.ermarian.net/converted The Roost: www.roost01.proboards104.com. Birds of a feather flock together. Posts: 794 \| Registered: Thursday, July 27 2006 07:00
Faint Piping of Two Demoniac Flutes Guardian Member # 5360	written Thursday, February 15 2007 14:41 Profile #17 And watch that not work, either. -------------------- May the fires of Undeath burn in your soul, and consume it. Posts: 1636 \| Registered: Wednesday, January 5 2005 08:00
Dryth'tor Lifecrafter Member # 7331	written Thursday, February 15 2007 14:43 Profile Homepage #18 Which not work? -------------------- You Shall Die Laughing: http://www.worfthecat.ermarian.net/converted The Roost: www.roost01.proboards104.com. Birds of a feather flock together. Posts: 794 \| Registered: Thursday, July 27 2006 07:00
Faint Piping of Two Demoniac Flutes Guardian Member # 5360	written Thursday, February 15 2007 14:44 Profile #19 Eh? Both of them. -------------------- May the fires of Undeath burn in your soul, and consume it. Posts: 1636 \| Registered: Wednesday, January 5 2005 08:00
Zeviz Nuke and Pave Member # 24	written Thursday, February 15 2007 14:46 Profile Homepage #20 quote: Originally written by Sarasaphilia: quote: Originally written by Dintiradan: And I've decided that post #2000 will require people to solve the Travelling Salesman problem before congratulating me. In terms of getting rid of them, in terms of getting rid of them politely, or in terms of torturing them verbally? I could write a book on How To Get Rid Of Telemarketers. And I like your little Graemlin. Try googling "Traveling Salesman Problem". It's a problem in algorithm design, asking to figure out the fastest way to visit all cities, returning to the starting location, given a "graph" of cities connected by roads of various length. The trick is that there is no "fast" solution to this kind of problems: all known algorithms take exponentially longer as the number of cities increases. Traveling Salesman Problem (TSP) is an example of NP-complete problems, which means that a fast way to solve this would also provide a fast way to solve many other unsolvable problems. -------------------- Be careful with a word, as you would with a sword, For it too has the power to kill. However well placed word, unlike a well placed sword, Can also have the power to heal. Posts: 2649 \| Registered: Wednesday, October 3 2001 07:00
Dryth'tor Lifecrafter Member # 7331	written Thursday, February 15 2007 15:16 Profile Homepage #21 quote: Originally written by Nalyd Twisted: Eh? Both of them. All of my methods work equally well. The last one is the best. -------------------- You Shall Die Laughing: http://www.worfthecat.ermarian.net/converted The Roost: www.roost01.proboards104.com. Birds of a feather flock together. Posts: 794 \| Registered: Thursday, July 27 2006 07:00
Faint Piping of Two Demoniac Flutes Guardian Member # 5360	written Thursday, February 15 2007 16:26 Profile #22 Oh, no the book and Dinti's attempt to stop the congratulations coming before the solution. -------------------- May the fires of Undeath burn in your soul, and consume it. Posts: 1636 \| Registered: Wednesday, January 5 2005 08:00
Dintiradan Guardian Member # 6670	written Friday, February 16 2007 11:27 Profile Homepage #23 Aw, shucks. I was hoping at least one person would take a look at the problem and declare, "Well, obviously 64 = 65." It's fun when they do that. wz.As has it right; it's based on Cassini's identity. Quick, someone else come up with a brain teaser. We can't let those incorrigible rating threads take over General! -------------------- I had no idea you had put so many ranks in Reverse Psychology. - Redcloak (OotS #106) Posts: 1509 \| Registered: Tuesday, January 10 2006 08:00
Dryth'tor Lifecrafter Member # 7331	written Friday, February 16 2007 12:23 Profile Homepage #24 Here you are. Not in the same category as the previous ones, but it came up under Google search for brain teasers. First, you look at the dot in the middle. Keep your eyes on the dot, and move your head away from the dot, and then closer to the dot. Post what you notice. And on a side note, this is going to be my last post for a while. I know you'll all miss me. I've a trip scheduled for 5 pm today to Cold Lake with my RCAC squadron. And I get to be Group 2IC! Yay! -------------------- You Shall Die Laughing: http://www.worfthecat.ermarian.net/converted The Roost: www.roost01.proboards104.com. Birds of a feather flock together. Posts: 794 \| Registered: Thursday, July 27 2006 07:00