create account | help/FAQ | contact | links | search | IRC | site news
 Everything Diaries Technology Science Culture Politics Media News Internet Op-Ed Fiction Meta MLP

 Puzzles! By bgalehouse in ScienceFri Jan 21, 2005 at 11:14:27 AM EST Tags: Culture (all tags) My officemates and I have taken to occasionally trading mind benders. While math graduate students might tend to such recreations more than others, we also like to believe that they have, or should have, universal appeal. Besides, I've heard a few from programmers also. Here are a few of my favorites. The difficulty is of course rather subjective. Do you have a favorite puzzle?

24 - Arithmetic - Hard

Using each of the numbers 1,3,4,6 create an expression which evaluates to 24. You may use any of the four standard arithmetic operations *,+,-,/ and parenthesis. You must use each of the numbers exactly once. You need not use any other numbers. It can also be done with 3,3,8,8.

Lockers - Number theory - Medium Easy

There are one hundred lockers in a row, all closed. Student number one walks by and opens every lockers. Student number two walks by and closes the even numbers. Student number three touches every third locker - locker numbers 3,6,9,12, etc. When he touches an open locker he closes it, when he touches a closed locker he opens in. Student number four changes every fourth locker. This continues for 100 students with student number n changing locker numbers n, 2n, 3n, etc. Which lockers are open and which are closed after this process?

The Monkey and the Coconuts - Number theory - Hard

5 sailors are shipwrecked on a deserted island. All they have to eat are coconuts, and they decide to divide them evenly tomorrow. They pile up all the coconuts in one big pile to sit overnight. That night, the first sailor wakes up and decides to take his share. He divides the coconuts into 5 equal piles, and has one left over which he throws to the monkey. He hides his pile, and puts back together the remaining 4 piles. Later that night, the second sailor wakes, makes 5 piles, again has one left over for the monkey and again hides his 'share'. In the course of the night each of the 5 sailors does this. So each has hidden some coconuts and the monkey has hidden five. The next morning, they divide the non-hidden coconuts into 5 piles but this time there are no extras for the monkey. How many coconuts were there?

Array Initialization - Programming - Medium

You've an algorithm which expects an n by n array initialized to zero. However, it typically only requires O(n) to run. You've memory to spare, but you'd like to avoid the n^2 initialization time each run. Describe a set of data-structures and provide the operations read, write, and clear. When used, they should look just like they were accessing a 2-d n by n array. However, all should have constant runtime (time independent of n).

Rectangles - Various - Very Hard

A rectangle is divided into smaller rectangles. Each of the smaller rectangles has the property that at least one of the sides has integer length. Show that the large rectangle has the same property. I've seen a particularly simple argument involving calculus, and found a not too long one involving number theory. I'm told that there are other proofs. While a bit abstract I think this one is cool for having multiple not obviously related solutions.

 Display: Threaded Minimal Nested Flat Flat Unthreaded Sort: Unrated, then Highest Highest Rated First Lowest Rated First Ignore Ratings Newest First Oldest First
 Puzzles! | 198 comments (193 topical, 5 editorial, 0 hidden)
 Hard (2.75 / 4) (#1) by Booji Boy on Thu Jan 20, 2005 at 02:53:01 PM EST

 6/(1-(3/4)) = 24 Can I have a free MacMini too?
 Oh yeah... (none / 0) (#2) by Booji Boy on Thu Jan 20, 2005 at 02:58:49 PM EST

 8/(3-(8/3)) = 24 too Can I have an iPod Shuffle as well? [ Parent ]
 Don't Forget.. (1.00 / 3) (#65) by karson on Fri Jan 21, 2005 at 11:45:51 AM EST

 (8 * 8) / 3 + 3 = 24 [ Parent ]
 Huh? (none / 0) (#98) by Legion303 on Sat Jan 22, 2005 at 01:56:55 AM EST

 Only if you truncate everything after the decimal point. [ Parent ]
 similarly... (none / 1) (#101) by pb on Sat Jan 22, 2005 at 05:36:14 AM EST

 1 / 3 + 6 * 4 = 24 Yay C! --- "See what the drooling, ravening, flesh-eating hordes^W^W^W^WKuro5hin.org readers have to say." -- pwhysall[ Parent ]
 Very good (none / 0) (#3) by bgalehouse on Thu Jan 20, 2005 at 03:00:20 PM EST

 Unfortunatly, I've no Mac Minis to hand out. Also of course, it is hard to gloat about how fast you got it to people who haven't had the chance to spend time thinking about it. Allways the problem with posting solutions quickly. [ Parent ]
 Haven't gloated yet... (none / 0) (#4) by Booji Boy on Thu Jan 20, 2005 at 03:11:18 PM EST

 Besides, those are the easy ones, the rest need a pencil. I certainly wasn't quick on the ball with the apple giveaways earlier, this must make up for it. [ Parent ]
 How about... (none / 1) (#31) by ubernostrum on Thu Jan 20, 2005 at 09:59:40 PM EST

 (14-6)*3 = 24? Or are we not allowed to create multi-digit numbers? -- You cooin' with my bird?[ Parent ]
 You're right (none / 0) (#57) by Booji Boy on Fri Jan 21, 2005 at 09:26:30 AM EST

 Who's to say that + isn't concactenation. [ Parent ]
 This ain't... (none / 0) (#70) by BJH on Fri Jan 21, 2005 at 12:55:15 PM EST

 ...C++ - no overloading allowed! -- Roses are red, violets are blue. I'm schizophrenic, and so am I. -- Oscar Levant ‮[ Parent ]
 Problem states operators are arithmetic. [n/t] (none / 0) (#137) by Fon2d2 on Mon Jan 24, 2005 at 10:57:52 AM EST

 [ Parent ]
 The 24 Game, Now In Stores! (none / 0) (#73) by DLWormwood on Fri Jan 21, 2005 at 01:23:19 PM EST

 Also of course, it is hard to gloat about how fast you got it to people who haven't had the chance to spend time thinking about it. I had to give up. The fraction threw me off... :-( I used to have a deck of cards with four numbers on them for playing this game. (Note the numbers on the front page.) However, IIRC, the rules that came with the deck I had stipulated that no solutions required fractions, so 1,3,4,6 and 3,3,8,8 wouldn't be in such a deck. The company has since made decks with fractional calculations. Your numbers would have been three dot difficulty... -- Those who complain about affect & effect on k5 should be disemvoweled[ Parent ]
 Before 24 (none / 0) (#111) by bgalehouse on Sat Jan 22, 2005 at 12:58:18 PM EST

 Or at least, before I heard of 24, there was Equations, and before Equations there was wff-n-proof. [ Parent ]
 Coconuts (none / 0) (#5) by CivisHumanus on Thu Jan 20, 2005 at 03:46:11 PM EST

 They had 3121 coconuts in the beginning.
 I think there were more nt (none / 0) (#37) by Big Sexxy Joe on Thu Jan 20, 2005 at 11:05:11 PM EST

 I'm like Jesus, only better. Democracy Now! - your daily, uncensored, corporate-free grassroots news hour[ Parent ]
 Lockers (none / 0) (#6) by CivisHumanus on Thu Jan 20, 2005 at 04:46:43 PM EST

 Lockers 2, 5, 10, 17, 26, 37, 50, 65 and 82 are open. The rest are closed.
 Your index is off by +1 [nt] (none / 0) (#8) by gumbo on Thu Jan 20, 2005 at 04:54:56 PM EST

 [ Parent ]
 Umm...no, yours is (none / 0) (#9) by CivisHumanus on Thu Jan 20, 2005 at 05:53:19 PM EST

 Lockers are numbered 1 through 100. Students are also numbered 1 through 100. Neither are zero-based. [ Parent ]
 Oh golly (none / 0) (#10) by gumbo on Thu Jan 20, 2005 at 06:04:51 PM EST

 I wonder what "(i + 1)" could possibly mean? [ Parent ]
 Right you are... (none / 1) (#16) by CivisHumanus on Thu Jan 20, 2005 at 07:08:44 PM EST

 I was off by one...     int i, student;         unsigned char locker[101];     for(i = 0; i <= 100; i++)         locker[i] = 0;     for(student = 1; student <= 100; student++)         for(i = student; i <= 100; i+=student)                 locker[i] = ~locker[i];     for(i = 1; i <= 100; i++)         {         printf("%x ", locker[i]);         if(!(i%10))    printf("\n");     } [ Parent ]
 You may want to notice (none / 0) (#11) by i on Thu Jan 20, 2005 at 06:31:09 PM EST

 that student 1 opens locker 1, and nobody closes it afterwards. Student 2 closes locker 2, and nobody opens it afterwards. —and we have a contradicton according to our assumptions and the factor theorem[ Parent ]
 It was only after I got the answers (none / 0) (#13) by gumbo on Thu Jan 20, 2005 at 06:49:45 PM EST

 that I realized you can deduce the results from factorization. So I still fail it. [ Parent ]
 Lockers (2.00 / 2) (#7) by gumbo on Thu Jan 20, 2005 at 04:49:18 PM EST

 import java.util.Arrays; public class Lockers{     public static void main(String args[]){         boolean lockers[] = new boolean[100];         Arrays.fill(lockers, true);         int student = 2;         while(student < 101){             for(int i=0; i
 Pathetic. (none / 1) (#27) by Dr Gonzo on Thu Jan 20, 2005 at 08:51:54 PM EST

 Way to use your brain there... not. The point of these is not to brute-force the problem with a computer program. "I felt the warmth spread across my lap as her bladder let loose." - MichaelCrawford[ Parent ]
 Yeah yeah (none / 0) (#29) by gumbo on Thu Jan 20, 2005 at 09:30:41 PM EST

 I know. But when you have a hammer ... It was too easy to code not to have a look at the answers. [ Parent ]
 lockers visualized (3.00 / 2) (#42) by felixrayman on Fri Jan 21, 2005 at 01:12:56 AM EST

 Here's one that prints out a visualization of what's going on (you'll need a display with >= 100 columns) : public class P {         private static int lockerCount = 100;         private static boolean [] lockers = new boolean[lockerCount];         public static void main ( String args[] )         {                 for( int i = 1; i <= lockerCount; i++ )                 {                         int j = i;                         while( j <= lockerCount )                         {                                 lockers[j-1] = !lockers[j-1];                                 j += i;                         }                         printLockers();                 }         }         private static void printLockers()         {                 StringBuffer buf = new StringBuffer();                 for( int i = 0; i < lockerCount; i++ )                 {                         buf.append( lockers[i] ? "o" : " " );                 }                 System.out.println( buf );         } } Apologies to the Luddite below known as Dr Gonzo, but we are programmers, and we are a tool-using culture. We don't do any thinking that a computer can do for us. In this case, a few lines of code quickly leads to the realization best described in comment #30. Call Donald Rumsfeld and tell him our sorry asses are ready to go home. Tell him to come spend a night in our building. - Pfc. Matthew C. O'Dell[ Parent ]
 That's cool (none / 0) (#62) by gumbo on Fri Jan 21, 2005 at 11:16:55 AM EST

 You can see the logic behind the solution much more clearly with that one. [ Parent ]
 Why use Java for this?!?! AHHH!! (none / 1) (#143) by Peaker on Mon Jan 24, 2005 at 05:15:17 PM EST

 Isn't this easier: def main():     lockers = [True] * 100     for student in xrange(2, 101):         for i in xrange(len(lockers)):             if (i+1) % student == 0:                 lockers[i] = not lockers[i]         print "Student Number: ", student, lockers if __name__ == '__main__':     main() [ Parent ]
 another way (3.00 / 2) (#12) by BottleRocket on Thu Jan 20, 2005 at 06:33:16 PM EST

 (1^3)*6*4 \$ . . . . . \$ . . . . . \$ . . . . . \$. ₩ . . . . . ¥ . . . . . € . . . . . § . . . . . £. . . . * . . . . . * . . . . . * . . . . . * . . . . . *\$ . . . . . ♀ . . . . . ♀ . . . . . ♀ . . . . . ♀ . . . . . ♀ . . . . . \$ Yes I do download [child pornography], but I don't keep it any longer than I need to, so it can yield insight as to how to find more. --MDC\$ . . . . . ♀ . . . . . ♀ . . . . . ♀ . . . . . ♀ . . . . . ♀ . . . . . \$. . . . * . . . . . * . . . . . * . . . . . * . . . . . *. ₩ . . . . . ¥ . . . . . € . . . . . § . . . . . £\$ . . . . . \$ . . . . . \$ . . . . . \$\$B R Σ III\$
 No exponentiation! (none / 0) (#17) by bgalehouse on Thu Jan 20, 2005 at 07:12:47 PM EST

 Violates the statement of the problem. In spite of the speed with which an answer was posted, as stated it can take quite some time to solve. As it happens, the answer is unique. [ Parent ]
 Just curious.. (none / 0) (#28) by spooky wookie on Thu Jan 20, 2005 at 09:02:43 PM EST

 How long time did it take you to solve it? [ Parent ]
 Under Fives minutes of staring (none / 0) (#58) by Booji Boy on Fri Jan 21, 2005 at 09:28:46 AM EST

 Once I realised that it would require some division by a fraction to get the number up to 24, it took a few seconds. [ Parent ]
 Why not? (none / 0) (#95) by Thought Assassin on Fri Jan 21, 2005 at 11:38:16 PM EST

 If you're writing it down on paper, you don't use the ^ symbol, so I don't think it's any more of a violation of the problem statement than the answer (I suspect) you are looking for, just a slightly different violation. Another answer that feels like about the same level of violation to me:  / 4 \ (      ) * 6 * 1  \ 3 / [ Parent ]
 But I'm wrong (none / 0) (#96) by Thought Assassin on Fri Jan 21, 2005 at 11:42:00 PM EST

 Your answer didn't violate the statement in the way I thought it did: (14-6)*3 That would be why you went to the trouble of calling them numbers, instead of digits. Silly me. [ Parent ]
 Waitwaitwaitwait! (none / 1) (#14) by Lisa Dawn on Thu Jan 20, 2005 at 06:57:04 PM EST

 The next morning, they divide the coconuts into 5 piles but this time there are no extras for the monkey. How many coconuts were there? All the coconuts, or just the remaining ones? Because (x - 5) % 5 = x % 5, which would destroy any hopes of a solution if they retotaled the coconuts, minus what they'd thrown to the monkey. Or did I miss something?
 The remaining ones. (none / 0) (#15) by bgalehouse on Thu Jan 20, 2005 at 07:06:44 PM EST

 I'll go edit to try to make this more clear. [ Parent ]
 Okay, I was worried... (none / 0) (#18) by Lisa Dawn on Thu Jan 20, 2005 at 07:17:31 PM EST

 that this was an example of an inconsistency within arithmetic. [ Parent ]
 Get those brains smoking! (3.00 / 2) (#19) by Ptyx on Thu Jan 20, 2005 at 07:24:53 PM EST

 http://www.ocf.berkeley.edu/~wwu/riddles/intro.shtml Some of them are really evil. -- "On voudrais parfois être cannibale, moins pour le plaisir de dévorer tel ou tel que pour celui de le vomir... " Cioran
 Nice one. (none / 1) (#21) by i on Thu Jan 20, 2005 at 07:37:04 PM EST

 With 24. Took me a while :) —and we have a contradicton according to our assumptions and the factor theorem
 An odd phenomenon with puzzle solving (none / 0) (#121) by gmol on Sun Jan 23, 2005 at 02:09:30 AM EST

 I tried that puzzle for an hour yesterday and couldn't come up with the answer. I spent some time thinking about it today and still couldn't get it. I read your post and thought "damn other people don't seem to be having a problem", scrolled up and the answer came to me in under a second when I saw the numbers again. [ Parent ]
 Car talk! And the ever-famous coconuts (3.00 / 2) (#22) by MostlyHarmless on Thu Jan 20, 2005 at 07:38:53 PM EST

 [Oops, reposted as topical. My apologies. Feel free to rate the other one down, or whatever] If you like light puzzles that require trickery without necessarily employing advanced math (although sometimes they do) you should be listening to Car Talk, or at least reading their weekly puzzler online. In particular, this puzzler, about extracting mangoes from a garden, is a similar setup to the coconuts problem. Speaking of coconuts - the problem is famous enough that MathWorld gives it the mandatory obfuscation. But the best presentation of that that I've seen has to be in the Mathematical Magpie, a collection of fiction and miscellany having to do with math. There's a whole elaborate setup involving competing for a contract and distracting the competition with math problems and so forth. I'm not sure where you can find the book other than amazon.com (the edition I have is old, maybe from the 70s), but it's definitely worth trying to get your hands on it. -- "Nevertheless, that is the theorem." - Tom Stoppard
 Regarding Mangos (none / 0) (#88) by mindstrm on Fri Jan 21, 2005 at 06:57:59 PM EST

 First, there are a few problems with the mango puzzle. http://www.cartalk.com/content/puzzler/transcripts/20106 First, Mangos are like Apricots, there are so many ripening all at once that they literally rot  on the side of the road, having fallen out of their trees. You can't give them away. Why people would flock to a certain mango tree is a real puzzler, they are all super sweet when ripe. Second, it is much more common to see people eating unripe "green" mangos, with salt and lemon. (it's quite yummy) Those having never visited mango growing regions likely wouldn't know this. A ripe mango is a wasted mango. Third, unless something was missing from the puzzler (say, that a guard had to be left with at least one mango himself), only two mangos would be required.  Half (1) goes to each guard, and the guard gives 1 back, leaving you with two again. Repeat. [ Parent ]
 You are correct, sir (none / 0) (#115) by PylonHead on Sat Jan 22, 2005 at 04:02:17 PM EST

 Except the first guard you encounter on the way back, having realized that he had been tricked, will beat the living crap out of you, and take both your mangos. Probably eat them with a little salt and lemon. [ Parent ]
 Here is another puzzle (3.00 / 2) (#24) by nollidj on Thu Jan 20, 2005 at 07:59:37 PM EST

 I'll post it in a journal if this story goes under. I solved it using java.math.BigInteger (because Perl's "arbitrarily long numbers" failed it), and I have some partially-worked-out arithmetic solutions (involving tricks with numbers divisible by nine or eleven and the like), so: Form an integer by running together (in order) all the integers from 1 to 1979 (inclusive). What is the remainder you get from dividing this by 1980?
 I'll think about it. (none / 0) (#25) by bgalehouse on Thu Jan 20, 2005 at 08:12:47 PM EST

 I assume that this can be done with pencil and paper? None of mine requires a computer, or even more than a page or two of paper. [ Parent ]
 I was the first in my family to solve it (none / 0) (#26) by nollidj on Thu Jan 20, 2005 at 08:40:17 PM EST

 This was told by an uncle to my father in '80 or '81, and it had been passed around where the uncle worked (some place to do with ECE or other fields of engineering). It should be solvable with pencil and paper, as back then there weren't exactly a ton of hand-held calculators or personal computers that could do that sort of computation easily. Given the context in which the question was asked, too, I would say that it should be solvable with just ordinary factorization or something. I think rules like these and some pencilwork should do it, but I just cracked a laptop and punched out a solution when I first heard the problem. Now that I've posted it here, I'll see about finding a more human solution.
 SPOILER (none / 1) (#33) by ubernostrum on Thu Jan 20, 2005 at 10:08:04 PM EST

 The easy way: 1979 + 1 = 1980 1978 + 2 = 1980 ...etc... 991 + 989 = 1980 Which leaves 990 all by itself. -- You cooin' with my bird?[ Parent ]
 You fail it. (none / 0) (#94) by mge on Fri Jan 21, 2005 at 11:03:36 PM EST

 You do realize this isn't what the question asked. Right? [ Parent ]
 You fail it. (none / 0) (#99) by ubernostrum on Sat Jan 22, 2005 at 03:38:12 AM EST

 You did read my other comments in this thread about ten seconds later. Right? -- You cooin' with my bird?[ Parent ]
 Wait. (none / 1) (#34) by ubernostrum on Thu Jan 20, 2005 at 10:13:29 PM EST

 What do you mean by "running together"? -- You cooin' with my bird?[ Parent ]
 String concatenation (none / 0) (#36) by nollidj on Thu Jan 20, 2005 at 11:01:20 PM EST

 I.e., here's the solution programmed in Java: asdf.java: ``` public class asdf{ public static void main(String[] args){ `````` StringBuffer sb = new StringBuffer(); for(int i = 1; i <= 1979; i++) sb.append(i); java.math.BigInteger I = new java.math.BigInteger(sb.toString()); java.math.BigInteger num = new java.math.BigInteger("1980"); System.out.println("That huge number modulo 1980 is " + I.remainder(num)); } `````` } ``` Now, as for how a human would do it...? I have been told that the original problem statement went so far as to say that you should be able to do this in, at most, one page of paper and that you needn't write out the whole 6809-digit number.
 And, just because I can, in Python: (3.00 / 2) (#46) by jonathan_ingram on Fri Jan 21, 2005 at 02:40:28 AM EST

 ```bignum = "".join([str(x) for x in range(1,1980)]) print "Remainder modulo 1980 is",bignum%1980 ``` -- Jon[ Parent ]
 You know nothing! (none / 0) (#47) by jonathan_ingram on Fri Jan 21, 2005 at 02:46:57 AM EST

 Idiot! (Just getting the insult in first, so people won't hit me for the obvious error I made in the above) -- Jon[ Parent ]
 A mistake... (none / 0) (#92) by chuhwi on Fri Jan 21, 2005 at 10:08:26 PM EST

 I think you meant to say: bignum = long("".join([str(x) for x in range(1,1980)])) [ Parent ]
 Python one liner (correct, and terse) (none / 0) (#103) by ChadN on Sat Jan 22, 2005 at 08:10:53 AM EST

 Just because I like to have the corrected version written explicitly for posterity, here's my one-liner. python -c 'print int("".join([str(i) for i in range(1980)]))%1980' This got me thinking, though, about looking for a similar puzzle w/ hexadecimal digits, where the remainder would spell out funny words... So far, no luck: funny_word_fragments = ["dead", "beef", "babe", "feed", "f00d", "b1ff", "1337", "baad", "b00b"] def puzzle(n):     return hex(int("".join([str(i) for i in xrange(n)]))%n) for n in xrange(1,2**20):     remainder_str = puzzle(n)     for word in funny_word_fragments:         if word in remainder_str:             print remainder_str, word, n [ Parent ]
 Doesn't require any paper. (none / 0) (#32) by ubernostrum on Thu Jan 20, 2005 at 10:06:23 PM EST

 Hint: read a biography of Gauss. -- You cooin' with my bird?[ Parent ]
 I, too, misread the problem that way (none / 0) (#44) by curien on Fri Jan 21, 2005 at 02:22:41 AM EST

 and had a solution before I realized I had made a mistake. -- This sig is umop apisdn.[ Parent ]
 Um...um...um...um... ! (none / 0) (#51) by Lisa Dawn on Fri Jan 21, 2005 at 04:03:34 AM EST

 My first guess is '20', but by the same logic, it could be 2 or 200 because I may have the wrong alignment. Also, I could be off by 1, so that means, 1, 2, 10, 20, 100, 200, or 1000. I'll think more on that and post my revised guess later. [ Parent ]
 Oh, screw that. (none / 0) (#53) by Lisa Dawn on Fri Jan 21, 2005 at 04:18:42 AM EST

 I was going with a reduced long division hack, but I just realized that working it out in the head is like working out the number of days left before your 1023984719028347102938471189212938047109278340217481273649812th birthday. Although, a long division hack is still do-able. You just need to be very very clever. [ Parent ]
 Perl works fine (none / 0) (#81) by athom on Fri Jan 21, 2005 at 02:47:43 PM EST

 perl -MMath::BigInt -le 'print Math::BigInt->new(join"",1..1979)->bmod(1980)' [ Parent ]
 A Mathematica one-liner (none / 0) (#85) by jmf on Fri Jan 21, 2005 at 05:24:37 PM EST

 The following one-liner, while perhaps longer than it would be in Perl, also works: `Mod[ToExpression[StringJoin[ToString /@ Range[1979]]], 1980]` And the answer is... 1179. [ Parent ]
 Python version (3.00 / 2) (#106) by MarkByers on Sat Jan 22, 2005 at 10:26:34 AM EST

 `int("".join(map(str, range(1,1980))))%1980` 1179 [ Parent ]
 Locker answer (3.00 / 2) (#30) by Big Sexxy Joe on Thu Jan 20, 2005 at 09:37:25 PM EST

 Spoiler below.  Ready? For any locker n, it is opened or closed once for each factor it has.  If a number has an even number of factors it will end closed.  If it has an odd number of factors it will be open. Most numbers have an even number of factors.  The only ones with an odd number of factors are perfect squares.  This is because you multiply two factors together to get the orginal number.  The square root of the number multiplied by itself to get the orginal number.  So if the square root is an integer it has an odd number of factors. Since there are ten perfect squares less than or equal to 100, the answer is 10. I'm like Jesus, only better. Democracy Now! - your daily, uncensored, corporate-free grassroots news hour
 Programming problem (3.00 / 2) (#35) by jimrandomh on Thu Jan 20, 2005 at 10:29:48 PM EST

 The programming problem is much harder than you label it (suggesting that you made a mistake). The bit about it being a 2-d array is superfluous; what you're asking for is a data structure with O(1) initialization, O(1) lookups, and O(1) inserts. Hash tables have either O(n) initialization or O(log n) inserts. (You have to either initialize a big table up front, or expand the table and re-hash things as you go.) All tree-related structures have O(log n) reads. And this isn't even considering that the unspecified algorithm could be "write and read N values from a random chapter of Bob's Hash Function Degenerate Cases Dictionary", in which case guaranteeing anything better than O(log n) read, O(log n) write (using a tree structure) is basically impossible. -- CalcRogue: TI-89, 92+, PalmOS, Windows and Linux.
 Not so, my friend! (none / 1) (#43) by evanbd on Fri Jan 21, 2005 at 02:01:34 AM EST

 You need the following data structures: int[n][n] data; int[n][n] valid; int mark_valid; init() {   for (int i = 0; i < n; i++)     for (int j = 0; j < n; j++)     {       valid[i][j] = 0;     }   mark_valid = 1; } clear() {   mark_valid++; } read(i, j) {   if (mark[i][j] == mark_valid)     return data[i][j];   else     return 0; } write(d, i, j) {   data[i][j] = d;   mark[i][j] = mark_valid; } And this will guarantee O(1) operation on read(), write(), and clear, even in the face of BHFDCD chapters. [ Parent ]
 integer wrap-around? (none / 0) (#55) by dimaq on Fri Jan 21, 2005 at 08:21:03 AM EST

 [ Parent ]
 What about them? (none / 0) (#77) by evanbd on Fri Jan 21, 2005 at 01:55:39 PM EST

 If you're competent and implementing this, you can tell whether it's a concern. Avoiding it is trivial, and if you shift to 64 bit marks it's completely irrelevant no matter what program you're writing. Also, frequently you can get some sort of guarantee that there will be a write() to every element at least once per 2^32 clear()'s, which also makes it not matter. [ Parent ]
 I am extremely puzzled (none / 0) (#56) by mcherm on Fri Jan 21, 2005 at 08:26:16 AM EST

 The goal of the problem is to avoid a N^2 initialization cost. Your solution has an init() method which is patently N^2. What am I supposed to make of this? -- Michael Chermside[ Parent ]
 It is possible without that. (none / 0) (#63) by bgalehouse on Fri Jan 21, 2005 at 11:37:14 AM EST

 It is possible to do without the initial N^2 array initialization cost. Suppose that java integer arrays begin life filled with random values. Or just pretend that we are writing in C. However, I perhaps didn't phrase the question clearly enough. [ Parent ]
 Well... (none / 0) (#79) by evanbd on Fri Jan 21, 2005 at 02:05:51 PM EST

 Setup time wasn't included in the problem statement, so I just used a solution I've written code for before ;) For many cases where this sort of thing comes up, it's perfectly fine to have O(n^2) one-time init cost; if the number of times you intend to run the algorithm exceeds n, then the init cost is small. Otherwise...  well, you could replace my pair of arrays with a pair of hashtables, and have a rather good sparse array implementation.  That avoids the init cost at the cost of a O(1) increase in time on read() and write().  Which one is actually faster is going to depend on the specifics of usage. [ Parent ]
 Not true (none / 0) (#107) by offline on Sat Jan 22, 2005 at 10:42:23 AM EST

 In fact, the init() time was specifically claimed as the motivation for the problem.  So, an n2 init time is not really acceptable as part of a solution. Chris Rose ----- Fly, you fools![ Parent ]
 mark[][] == valid[][]? (none / 0) (#104) by cloudboi on Sat Jan 22, 2005 at 08:44:39 AM EST

 I assume this was just a typo and that you really intended your mark array to be the valid array, right? -cb [ Parent ]
 my solution in C (none / 0) (#118) by ChadN on Sat Jan 22, 2005 at 08:14:05 PM EST

 That is what makes it a good problem. (none / 0) (#66) by bgalehouse on Fri Jan 21, 2005 at 11:47:50 AM EST

 So many of the standard structures don't seem to work. I first heard it from a C.S. prof. He agreed with my answer, and I'm in any case rather sure about it. Perhaps the error is in my difficulty assesment. I believe it took me a day or two. As opposed to the 24 problem which I gave up and cheated on, and the rectangles problem which I got a few weeks after hearing it. Now, if you want an exceptionaly hard programming problem: It is rather straightforward to make a queue from two stacks. In such a way as to have amortized constant runtime. That is, we have an O(n) bound on the time to execute any n puts and gets. Just do the obvious thing and think about how many times you ever touch at bit of data. I have been told, but never did prove, that it is possible to have strict constant time on each put and get if you use a larger (but fixed) number of stacks and enough ingenuity. [ Parent ]
 How is n^2 relevant (none / 0) (#71) by maniac1860 on Fri Jan 21, 2005 at 01:03:14 PM EST

 I think you missed his point. As long as all operations have to be in constant time, the fact that the array is n^2 is irrelevant. It might as well be of size n^n since n can't exist in any of the operations on the array. [ Parent ]
 Yes yes, (none / 0) (#74) by bgalehouse on Fri Jan 21, 2005 at 01:37:32 PM EST

 Well, maybe the n^2 is a bit of misdirection masquerading as justification for the problem. The comment that I meant to respond to didn't seem to talk about that though, especially with respect to a potential error. I was just trying to reassure him that there is a solution. At least, the only mistake I've found so far in the statement makes it easier not harder. Specifically, in the original problem it is basically an init function instead of a clear and it's calls for space are assumed to return in constant time, but the space returned is filled with unknown data. So the provided solution isn't quite what was expected, though perhaps within the constraints that I actualy stated. [ Parent ]
 malloc is O(n) (3.00 / 2) (#87) by jimrandomh on Fri Jan 21, 2005 at 06:17:02 PM EST

 Memory allocation isn't O(1) on any hardware that I know of; every page you ask for from the OS means an MMU operation. You can get around this by re-using the same region of memory over multiple runs, of course, but the assumption that malloc is O(1) is false. And the clear function has the same problem: freeing memory is likely to be O(n) as well. -- CalcRogue: TI-89, 92+, PalmOS, Windows and Linux.[ Parent ]
 You don't have to use malloc. (none / 1) (#109) by i on Sat Jan 22, 2005 at 12:37:15 PM EST

 Memory allocation and deallocation are O(1) as long as all your data structures are of the same size. —and we have a contradicton according to our assumptions and the factor theorem[ Parent ]
 Address space issue (none / 1) (#120) by jimrandomh on Sat Jan 22, 2005 at 10:41:54 PM EST

 Memory allocation can only be O(1) if the memory you're allocating is already in your address space (that is, if you freed something of similar size earlier). The first time you allocate, though, you must request n bytes from the OS so you have some space to allocate into. The OS has to map n/pagesize pages of memory into your program's address space, and for each page it maps it must do O(1) work. Thus, memory allocation is O(n). There's no way around it. -- CalcRogue: TI-89, 92+, PalmOS, Windows and Linux.[ Parent ]
 Not every OS has pages. (none / 0) (#123) by i on Sun Jan 23, 2005 at 04:25:55 AM EST

 Look at your sig :) Anyway, I only need to allocate from the OS once, so it's amortised O(1) in any case. —and we have a contradicton according to our assumptions and the factor theorem[ Parent ]
 Solution? (none / 0) (#93) by mge on Fri Jan 21, 2005 at 10:16:35 PM EST

 I think that you can two it in two (or are you saying that doing it easy, proving it is hard?) Algorithm: Two Stacks, S1 and S2 On Enqueue: Push item onto S1 On Dequeue (precondition, S1 and S2 are not both empty): If S2 is empty, enter a loop.  While S1 has an element, pop that element and push it onto S1. (here S2 now has items in it):  Pop S2 Every Item is pushed twice (once onto S1 and once onto S2) and popped twice (once from S1 and once from S2)  All these basic operations are O(1). Do I win, or did you want something else? [ Parent ]
 The obvious part. (none / 0) (#108) by bgalehouse on Sat Jan 22, 2005 at 12:29:04 PM EST

 I said it was easy with two stacks and amortized constant runtime. However, this solution has an arbitrarily long runtime for pop - sometimes that pop operation takes a long time. The hard problem is to use additional stacks and ingenuity to have a constant time bound on each individual operation i.e. no looping. [ Parent ]
 Hash table is a solution (none / 0) (#126) by Arkaein on Sun Jan 23, 2005 at 10:46:39 AM EST

 I'm really surprised there is actually an argument over this, given the likely number of programmers and computer scientists on this site, hash tables are definitely the way to go (or a way, not saying it is a unique solution). First of all arrays are right out. Initializing an n x n array cannot be done in order n, and initialization of some sort is required to know whether a particular index has been visitied already during the algorithm. I've actually dealt with problems like this. In visualization and analysis of 3D models acquired from range data (basically using 3D scanners that produce a pointcloud), operations which test for collisions or point overlap often utilize a 3D hash table in addition to tree based search structures. 3D space is sparse so you never use a 3D array to track surface points. You store points in a dense linear array and mark spatial positions using a 3D hash table. Creating the hash table is O(n) (to achieve optimal O(1) perfromance for insertion and lookup the table should be on the order of the size of the number of points), insertion and lookup are O(1). With the given problem things are easier because we already have integer "coordinates" (in 3D you must scale and truncate 3D coordinates to get integer values suitable for hashing on a cubic grid). We create a hash table as a length N array of pointers (initially null) in O(n) time. Next we run the given algorithm. Because it runs in O(n) time it must make O(n) or fewer array operations, meaning most of the array will not even be used. This is the key. We can build our hash table accessor function (which I'll call table.get(x, y)), such that if the algorithm queries a value at coordinate not stored in the table, get() calls insert(x, y, 0). Because each of these ops runs in O(1) time, the main part of the algorithm will run in O(n). Also interesting to note is that the problem statement says that the computer has memory to spare, implying that the data structure used in lieu of a standard aray might be large. Because the hash table is O(n) size (size n array with linked lists containing a total of n nodes) it is likely spaller than the sparesely filled n x n array which might otherwise be used. I haven't gone into the exact hashing process for 2D coordinates, anyone who really wants details just say so and I'll fill in the gaps. ---- The ultimate plays for Madden 2005[ Parent ]
 O(N) > O(1) (none / 0) (#164) by bugmaster on Tue Jan 25, 2005 at 08:46:39 PM EST

 We create a hash table as a length N array of pointers (initially null) in O(n) time. Doesn't this mean that your initialization time is O(N) ? This does not satisfy the O(1) requirement of the original problem. >|<*:=[ Parent ]
 hash table (none / 0) (#174) by Arkaein on Thu Jan 27, 2005 at 09:08:40 AM EST

 One time setup of the hash table is O(n). Insertion of each value done during the runtime of the main algorithm is (1). The goal is to achieve O(n) total, and to avoid O(n * n) which would be necessary to init a full n * n array. ---- The ultimate plays for Madden 2005[ Parent ]
 Some puzzles for you. (3.00 / 3) (#39) by jd on Thu Jan 20, 2005 at 11:34:31 PM EST

 The first one is actually quite easy. A sailing ship circumnavigates the world. Which part of the ship travels the furthest? There are only five regular solids. (A regular solid is one in which all sides are the same shape and size.) Without looking it up, can you show this to be true? Action and reaction are equal and opposite. Photons have momentum. Given the shape of a typical car headlight and the angle it shines the light over, how bright would a car's headlights need to be to propell the car backwards? (Assume the car's mass is M.) Draw any random set of shapes you like over any scale you like. There is an absolute maximum number of colours you need to use to fill in each shape and be absolutely guaranteed that no two adjacent shapes will have the same colour. How many colours do you need? A computer monitor or TV uses a mix of red, green and blue to represent different colours. However, the eye doesn't see red, green and blue equally. Assuming a "true colour" display (256 intensities of each), how many colours can you actually see? Find a colour - any colour - that can not be produced on such a display. Then find a different colour that can not be produced on any RGB display, however many intensities it can produce. There is a simple game that many children are shown. You have three services - gas, electricity and water, and three houses. Draw these on a piece of paper in any way you like (other than they cannot touch or overlap). Draw lines from each service to each house, such that no lines intersect. It turns out it can't be done in two dimensions. You have to have three. But here's a nasty twist for you. Find an extension to the problem that can't be solved in less than four dimensions.
 First one (none / 0) (#45) by curien on Fri Jan 21, 2005 at 02:35:46 AM EST

 The side closest to the equator. -- This sig is umop apisdn.[ Parent ]
 Hmn (none / 0) (#48) by nollidj on Fri Jan 21, 2005 at 03:32:57 AM EST

 Not the crow's nest (or, if there isn't one, the top of the main mast)?
 I misread (none / 0) (#52) by curien on Fri Jan 21, 2005 at 04:13:01 AM EST

 or misremembered what I read or whatever. I thought he said "which side of the boat..." I guess it depends on the dimensions of the ship. -- This sig is umop apisdn.[ Parent ]
 Um... (none / 0) (#49) by Lisa Dawn on Fri Jan 21, 2005 at 03:46:04 AM EST

 The mast? [ Parent ]
 Shapes (none / 0) (#67) by bgalehouse on Fri Jan 21, 2005 at 12:00:10 PM EST

 For shapes on a piece of paper, this is answered by a rather famous theorm. The theorm is hard and was proved using computer assistance. As far as I know there isn't a more elegant proof available. In 3 dimensions, no number of colors is sufficient. Showing this is a little puzzle in itself. Also, regarding the car, don't we need to know coefficient of static friction? And what about the intensity of the tail lights. Or am I missing something? [ Parent ]
 Shapes / "x color map theory" (none / 1) (#68) by Wally Fenderson on Fri Jan 21, 2005 at 12:49:32 PM EST

 But the number changes if you have a flat surface (such as a map) or if you tackle the problem on the serface of a sphere (Like a globe)... LOAD "SIG",8,1[ Parent ]
 Globe versus plane. (none / 0) (#91) by bgalehouse on Fri Jan 21, 2005 at 09:03:09 PM EST

 I don't think that there a difference between a plane and a sphere. One can draw a figure on a sphere which requires x colors. So the number for a sphere is at least x. On the other hand, if you have a diagram on a sphere, you can poke a hole in the interior of one area and flatten out the sphere. E.G. the standard Cauchy sphere projection onto the plane. I suppose that on a torus or similar handlebody the extra connectivity probably means more colors are required. But topologically the sphere and the plane are almost the same, and this problem doesn't involve compactness. [ Parent ]
 Holes (none / 0) (#122) by Spendocrat on Sun Jan 23, 2005 at 03:20:46 AM EST

 You only need more colours once you start poking holes into your objects. IIRC, you need 11 colours for a torus. [ Parent ]
 Physics problem is impossible (none / 0) (#69) by awgsilyari on Fri Jan 21, 2005 at 12:50:04 PM EST

 It would be trivial, except that you've said nothing about friction. Without friction, the answer is that any amount of light at all would propel the car backward. With friction, it would be precisely enough light to create a force equal to the static friction of the tires on the roadway. There isn't enough information. The map coloring problem is easy: 4 colors. Well, easy in the sense that recalling the correct answer from memory is easy :-) The RGB problem is easy to figure out once you realize that some colors in the human visual gamut actually require negative values of G to represent in RGB space. -------- Please direct SPAM to john@neuralnw.com [ Parent ]
 Negative values of G? (none / 0) (#136) by Fon2d2 on Mon Jan 24, 2005 at 10:47:25 AM EST

 I've never heard of that. Can you elaborate or show some supporting links. I would find that very interesting. [ Parent ]
 Absolutely. (none / 0) (#142) by awgsilyari on Mon Jan 24, 2005 at 04:17:19 PM EST

 This probably isn't the BEST link out there, but it's the first one I found in Google that had a reasonably complete explanation. And I got something slightly wrong... It is RED which sometimes takes on negative values, not GREEN. Anyway, the idea is, it isn't possible to produce EVERY color that a human can perceive by mixing purely POSITIVE amounts of R, G, and B. There are some colors that can't be produced that way. This is ultimately due to the way the human eye works. -------- Please direct SPAM to john@neuralnw.com [ Parent ]
 Not a very thorough explanation, (none / 0) (#157) by Fon2d2 on Tue Jan 25, 2005 at 09:58:02 AM EST

 but I think I get it. The choice of the three primaries isn't perfect and the blue primary was probably chosen where the red cone has another small sensitivity hump corresponding somewhat with the blue cone's sensitivity. Thus it would take an additional negative value of R to counteract the R added from the choice for B and reproduce all of the spectral colors. None of that's explitily stated of course. It just shows the R line dipping below zero without any real explanation. Anyway, if you fancy yourself pretty knowledgable on color theory, you should take a look at the Gavrik paper. It's something I stumbled across a long time ago in my endless quest to understand color. I had to read it a couple times before I understood what it was saying. Once I did, I was highly intrigued and wanted to determine the veracity of its statements, but I have no real way of doing that. I have searched for other sites that discuss what this paper discusses and found nothing. Its content is too technical to discuss with any of my friends (I have tried). Personally I think the paper pretty well covers its bases and is only a few key steps away from convincing me. It basically just needs independant verification. You may be wondering why I don't just tell you what it's about, but there's a very good reason for that. I'm only willing to discuss if you're first able to understand it on your own. If you would like to discuss it, reply to this post and I will email you, or I'll reply with my email. [ Parent ]
 Solids (none / 0) (#76) by kallisti on Fri Jan 21, 2005 at 01:50:25 PM EST

 Easy to prove by exhaustion. You need at least 3 faces at a corner to have shape and the angles cannot add up to 360 or more degrees, or it would be flat. So, triangles = 60 deg, allowing 3,4 or 5 (tetrahedon, octahedron and icosahedron). Squares (90deg) only 3 (cube), Pentagons (72deg) only 3 (dodecahedron), 3 hexagons are 360 deg so it ends there. You didn't specify convex, which means the Kepler-Poinsot solids would also qualify. This gives you an extra 4. I cofess I did look up Kepler for the link, but not the proof. [ Parent ]
 Also (none / 0) (#80) by bgalehouse on Fri Jan 21, 2005 at 02:36:13 PM EST

 He stated that the faces are the same, not that the faces are regular polygons. So for example there are quite a few rohmbic polyhedra which qualify as stated. This problem bothered me because I remembered assmebling a model of one of these as a kid. But I didn't want to look it up... [ Parent ]
 Colours: (none / 0) (#82) by Dr Caleb on Fri Jan 21, 2005 at 03:00:21 PM EST

 Ultraviolet, infrared. ;-). 255R - 0G - 0B only produces light to ~450nm. Vive Le Canada - For Canadians who give a shit about their country. There is no K5 cabal.[ Parent ]
 Map coloring: (none / 0) (#86) by mindstrm on Fri Jan 21, 2005 at 05:40:07 PM EST

 "Draw any random set of shapes you like over any scale you like. There is an absolute maximum number of colours you need to use to fill in each shape and be absolutely guaranteed that no two adjacent shapes will have the same colour. How many colours do you need?" Two answers: Answer one: If you meant minimum, and not maximum, any 2d surface can be colored as you described using four colors. However, if we are assigning colors to shapes randomly, and putting no thought into it, then you will need a minimum of colors equal to the number of shapes to ensure no two regions have the same color. [ Parent ]
 Answers (3.00 / 5) (#89) by jimrandomh on Fri Jan 21, 2005 at 06:58:58 PM EST

 A sailing ship circumnavigates the world. Which part of the ship travels the furthest? The crew. There are only five regular solids. (A regular solid is one in which all sides are the same shape and size.) Without looking it up, can you show this to be true? d4, d6, d8, d12, d20. The d10, d30 and d100 aren't regular, and if there were any other regular solids Wizards of the Coast would manufacture them. Action and reaction are equal and opposite. Photons have momentum. Given the shape of a typical car headlight and the angle it shines the light over, how bright would a car's headlights need to be to propell the car backwards? (Assume the car's mass is M.) No amount of light is sufficient; you forgot to release the parking brake. Draw any random set of shapes you like over any scale you like. There is an absolute maximum number of colours you need to use to fill in each shape and be absolutely guaranteed that no two adjacent shapes will have the same colour. How many colours do you need? Two, because you can mix them in various proportions. Or one, if you count the color of the paper you drew on. Alternatively, you might draw the shapes over pre-colored regions, in which case you don't need any colors. A computer monitor or TV uses a mix of red, green and blue to represent different colours. However, the eye doesn't see red, green and blue equally. Assuming a "true colour" display (256 intensities of each), how many colours can you actually see? Find a colour - any colour - that can not be produced on such a display. Then find a different colour that can not be produced on any RGB display, however many intensities it can produce. Black cannot be produced on any RGB display, however many intensities it can produce, because the RGB display itself emits black-body radiation. There is a simple game that many children are shown. You have three services - gas, electricity and water, and three houses. Draw these on a piece of paper in any way you like (other than they cannot touch or overlap). Draw lines from each service to each house, such that no lines intersect. It turns out it can't be done in two dimensions. You have to have three. But here's a nasty twist for you. Find an extension to the problem that can't be solved in less than four dimensions. You have three services - DSL, cable, and optical fiber. Draw lines from each service to each house. It turns out it can't be done in three dimensions. -- CalcRogue: TI-89, 92+, PalmOS, Windows and Linux.[ Parent ]
 Number Theory (none / 1) (#41) by Armada on Fri Jan 21, 2005 at 01:05:11 AM EST

 Everyone knows the high school rule of adding digits to determine if a number is divisible by three. What few know is how well summing digits works with prime numbers. Specifically: twin primes. In fact, I have created two twin prime generators based on fundamentals with summing (and multiplying) digits. Unfortunately, due to my lack of programming expertise, I've been unable to test any primes past 1700 digits. I used to believe it would go on indefinitely, and even thought for a while I could prove the twin-prime conjecture, but it "misses" twin primes on a regular basis. Here's where I started in high school: Suppose sumd(x) is the sum of the digits of integer "x". As long as X is a whole number greater than 0: sumd(x^2) will always equal 1, 4, 7, or 9. sumd(x^3) will always equal 1, 8, or 9. I would encourage those of you who actually work with number theory to look into this more. I've even designed hashes based off such a trick. It's really cool, but unfortunately, I don't think there's much there. I've been told that creating prime number generators up to 1000 digits is relatively easy, but they all fail eventually at some point. Still, summing digits is simple and fun and there's a lot of cool stuff to learn from it, I wish they did more research into it.
 Not quite... (none / 0) (#97) by Legion303 on Sat Jan 22, 2005 at 01:31:09 AM EST

 "Suppose sumd(x) is the sum of the digits of integer "x". As long as X is a whole number greater than 0: sumd(x^2) will always equal 1, 4, 7, or 9." Your formula is incomplete. Take x=8 as a counterexample. "sumd(x^3) will always equal 1, 8, or 9." x=4. [ Parent ]
 He probably means the single-digit sum. (none / 0) (#116) by i on Sat Jan 22, 2005 at 04:48:49 PM EST

 In which case he's right. —and we have a contradicton according to our assumptions and the factor theorem[ Parent ]
 sorry, need to clarify (none / 0) (#127) by Armada on Sun Jan 23, 2005 at 01:54:23 PM EST

 sumd(x) means sum the digits of x. Then, if there is still more than 1 digit, add those digits. And continue to do that indefinitely. Here are numbers that are divisible by 3 simply by looking at them: The reason why is that adding the digits gets you a 3, 6, or 9. This is nothing new. But look at number 189. 1 + 8 + 9 = 18. You can't stop there though, you have to add those digits. (Well, you CAN stop there, but for sumd()'s purposes, I'm saying you cannot. 1 + 8 = 9. [ Parent ]
 Whoops (none / 0) (#133) by Legion303 on Mon Jan 24, 2005 at 08:03:57 AM EST

 Bahahaha. And I've even worked with this operation before. I'd already assumed you meant single-digit sums, but I was taking 6+4=10 and discarding the 1 instead of continuing the operation. D'oh! [ Parent ]
 mod 9 (none / 1) (#128) by hhumbert on Sun Jan 23, 2005 at 03:37:27 PM EST

 The single-digit sumd function is equivalent to the number mod 9 (or, more generally, to the number mod (b-1) if you are working with base b numbers). This is easy to show: the number a1a2a3a4...an is equivalent to 10^(n-1)*a1 + 10^(n-2)*a2+...+10^0*an Now when we take this number mod 9, we can distribute the mod 9 out over the sums and products, so that each 10^k turns out to be the product of k factors of (10 mod 9) = 1.  Thus we get a1+a2+a3+...an for the sum mod 9. I'm curious as to how you applied this to hashes. [ Parent ]
 Game of 4 (3.00 / 4) (#54) by SocratesGhost on Fri Jan 21, 2005 at 07:36:36 AM EST

 This is something to do while waiting in line or while on a long drive. Use exactly four 4's in any combination to create as many numbers as possible using whatever mathematical operators you choose. For example: 0 = 44! - 44! 1 = 4^4 / 4^4 and so on. (Yes, I know there are simpler ways to do the examples, I'm just demonstrating that you can use more than just the basic operators.) -Soc I drank what?
 Solution. (3.00 / 6) (#117) by i on Sat Jan 22, 2005 at 05:40:39 PM EST

 n=-logsqrt(4)logsqrt(4)(sqrt(sqrt(sqrt(...(sqrt(4/sqrt(4)))...)))) There are n+3 square roots total, two of which are in the log bases and one is in the denominator. —and we have a contradicton according to our assumptions and the factor theorem[ Parent ]
 clever. (none / 0) (#124) by coderlemming on Sun Jan 23, 2005 at 06:17:20 AM EST

 I thought this was a joke at first.  Then I actually worked it through... very interesting.  However, I have to wonder if it's cheating?  There's an implied   2 in the sqrt operator. Ok, now, on to the reals ;) --Go be impersonally used as an organic semen collector!  (porkchop_d_clown)[ Parent ]
 No joke sirree. (none / 1) (#125) by i on Sun Jan 23, 2005 at 07:39:36 AM EST

 Here's a derivation for the sceptically minded. -logsqrt(4)logsqrt(4)(sqrt(sqrt(sqrt(...(sqrt(4/sqrt(4)))...)))) = -log2log2(sqrt(sqrt(sqrt(...(sqrt(2))...)))) = -log2log2(...((21/2)1/2)...)1/2 = -log2log221/2n = -log2(1/2n) = log22n = n Whether it should be considered cheating or not, I don't know. —and we have a contradicton according to our assumptions and the factor theorem[ Parent ]
 Yes, I think so. (none / 0) (#135) by Fon2d2 on Mon Jan 24, 2005 at 10:40:00 AM EST

 Implied 2 in "4 to the 1/2". [ Parent ]
 coconut monkeys (none / 1) (#59) by zenofchai on Fri Jan 21, 2005 at 09:31:09 AM EST

 x % 5 = 1 (x % 5) % 5 = 1 ((x % 5) % 5) % 5 = 1 (((x % 5) % 5) % 5) % 5 = 1 ((((x  % 5) % 5) % 5) % 5) % 5 = 1 (((((x % 5) % 5) % 5) % 5) % 5) % 5 = 0 Okay, that is the information as I read it from the verbage -- being stupid and wrong! This appears to be a paradox as substituting the equality statement in step 5 into step 6 results in stating "1 % 5 = 0" which is false. But then you notice the "trick" -- the sailors put back the remainder and take out the one for the monkey. x % 5 = 1 (x - (x % 5) - 1) % 5 = 1 (x - ((x - (x % 5) - 1) % 5) - 1) % 5 = 1 (x - ((x - ((x - (x % 5) - 1) % 5) - 1) % 5) - 1) % 5 = 1 (x - ((x - ((x - ((x - (x % 5) - 1) % 5) - 1) % 5) - 1) % 5) - 1) % 5 = 1 (x - ((x - ((x - ((x - ((x - (x % 5) - 1) % 5) - 1) % 5) - 1) % 5) - 1) % 5) - 1) % 5 = 0 Can anybody tell me if I'm on the right track here? -- The K5 Interactive Political Compass SVG Graph
 oops, typos galore (none / 0) (#60) by zenofchai on Fri Jan 21, 2005 at 09:33:02 AM EST

 totally screwed up the second set of "correct" information, using "%" where I meant "/" for all but the right-most "%" in every line. And even then I think I not only am wrong, but need to get back to work. -- The K5 Interactive Political Compass SVG Graph[ Parent ]
 Here's the way I worked it out (none / 0) (#61) by CivisHumanus on Fri Jan 21, 2005 at 11:07:38 AM EST

 (1)  a = 5b + 1 (2) 4b = 5c + 1 (3) 4c = 5d + 1 (4) 4d = 5e + 1 (5) 4e = 5f + 1 (6) 4f = 5g From these six statements, substitute the value of f  = 5g/4 in (5), the value of e = 5*(5g/4) + 1 in (4), the value of d in (3), the value of c in (2), finally the value of b in (1), and you are left with the following equation : a = (15625g + 8404)/1024 run the following code (brute force)     float g, a;     g=0;         while(1)         {             a = ((15625 * g) + 8404)/1024;             if(a - (floor(a)) == 0)             {                 printf("a = %f, g = %fn", a, g);                 break;             }             g++;         } and you get the values g = 204 and a = 3121. [ Parent ]
 yeah (none / 1) (#64) by zenofchai on Fri Jan 21, 2005 at 11:45:42 AM EST

 in my notebook i scrawled out your statements 1-6 almost identically but i didn't see the "elegant" way of finding the solution (non brute force) although I considered your exact code implementation in a moment of weakness. -- The K5 Interactive Political Compass SVG Graph[ Parent ]
 more coconuts (none / 1) (#83) by jmf on Fri Jan 21, 2005 at 05:08:17 PM EST

 In fact, there is not a unique answer to this question. You can have 3121 + 15625 n coconuts, where n is any non-negative integer. The "brute force" solution clearly only finds the smallest, but this ambiguity is obvious from your equation. [ Parent ]
 Correct (none / 0) (#141) by CivisHumanus on Mon Jan 24, 2005 at 03:48:51 PM EST

 In theory, this problem has an infinite number of solutions. [ Parent ]
 Array initalization solution (2.00 / 3) (#72) by interjay on Fri Jan 21, 2005 at 01:05:44 PM EST

 See my solution which was previously made here. It was for a 1-dimensional array but obviously would be the same for 2 dimensions.
 Very good (none / 0) (#75) by bgalehouse on Fri Jan 21, 2005 at 01:46:42 PM EST

 That is the solution that I know, up to trivial variation. Only a few puzzles left unanswered, for all that this takes the mystery out of them. [ Parent ]
 I you like this sort of thing (none / 0) (#78) by kallisti on Fri Jan 21, 2005 at 02:00:33 PM EST

 Try some stuff by Raymond Smullyan. Some extremely tricky logic puzzles that will give you a real workout in Godel theory and combinatorics. His early books are easier ("What is the Name of This Book?"), other good ones: Lady or the Tiger - general logic, excellent Godelian lock problem To Mock a Mockingbird - all about combinatorial math Forever Undecided - predicate logic and Godel (detect a theme?) Satan, Cantor and Infinity - some of everything His philosophy stuff is highly entertaining, too.
 the tetrahedra problem. (none / 0) (#84) by gzt on Fri Jan 21, 2005 at 05:19:09 PM EST

 How many congruent regular tetrahedra can be packed around a vertex?
 Hmm (1.33 / 3) (#90) by trhurler on Fri Jan 21, 2005 at 08:44:52 PM EST

 Your memory allocation problem is REALLY easy. The rectangles proof is intuitively obvious. I was never any good at coming up with acceptable formal proofs, but this is a sit and stare problem if you ask me. Anyone who can't convince himself with visual aids must be a retard, and anyone who needs the visual aids isn't too bright. But yes, it is probably hard to prove. Who cares? I can write a one line perl script that solves the lockers problem. Problems solvable by such means are not "hard" in my book. But in any case, I thought of a simple solution while writing this paragraph. Lockers with an even number of factors will be closed. Lockers with an odd number of factors will be open. The 24 problem can be solved by brute force, and generally will be; there's no magical solution. As such, if I wanted to waste more than a minute's time on it, I'd write a program to evaluate all the possibilities(minus some that obviously won't work) until it found the answer. Really, the only one of these I like is the monkey and coconuts one. I could figure it out, but I know there's an easier way, and I'm not going to bother. :) -- 'God dammit, your posts make me hard.' --LilDebbie
 The elegant way (3.00 / 2) (#119) by rpresser on Sat Jan 22, 2005 at 09:32:00 PM EST

 is to use negative coconuts. Martin Gardner's column, "The Monkey and the Coconuts," reprinted in The Colossal Book of Mathematics (2001), goes through the problem in detail.  First he analyzes a version of the problem where the monkey does get a final coconut from the division in the morning (ending up with 6 coconuts), then he treats the version you give, where the monkey does not. The central part of the negative coconut idea is this (page 5): "Since N is divided six times into five piles, it is clear that 56 can be added to any answer to give the next highest answer.  In fact any multiple of 56 can be added, and similarly any multiple can be subtracted.... "The first sailor approaches the pile of -4 coconuts, tosses a positive coconut to the monkey ... thus leaving five negative coconuts. These he divides into five piles, a negative coconut in each. After he has hidden one pile, four negative coconuts remain -- exactly the same number that was there at the start! The other sailors go through the same ghostly ritual, the entire procedure ending with each sailor in possession of two negative coconuts, and the monkey ... with six positive coconuts. To find the answer that is the lowest positive integer, we now have only to add 15,625 to -4 to obtain 15,621, the solution we are seeking." Later, in the Answers section, he treats the problem where the monkey does not get a last coconut (page 7): "The number of coconuts in Ben Ames Williams's version of the problem is 3,121. We know from the analysis of the older version that 55 - 4, or 3121, is the smallest number that will permit five even divisions of the coconuts with one going to the monkey at each division. After these five divisions have been made, there will be 1020 coconuts left. This number happens to be evenly divisible by 5, which permits the sixth division in which no coconut goes to the monkey." ------------ "In terms of both hyperbolic overreaching and eventual wrongness, the Permanent [Republican] Majority has set a new, and truly difficult to beat, standard." --rusty[ Parent ]
 Combined logic and mathematics puzzle: (3.00 / 3) (#100) by esrever on Sat Jan 22, 2005 at 05:08:59 AM EST

 Don't know who gets credit for this one, but I was told it a while ago and subsequently spent some quite some time getting it solved.  Here you go... What we know:  * There are two numbers  * They are both positive integers  * They are both different from each other  * They are both larger than one  * The sum of the two numbers is less than or equal to 50 The product of the numbers is given to one Logician (who we will call 'P').  The sum of the numbers is given to another Logician (who we will call 'S').  Both Logicians are aware of the same information as us, as presented above.  P says "I don't know what the two numbers are.".  S responds with "Well, I already knew that.".  To which P replies "Well, in that case, I do know what the two numbers are.".  At that point S says "Oh, well, in that case, so do I.".  The puzzle is, of course, to find the two numbers that fit the information we have been given, and which also cause the statements of the Logicians to be true. After solving the logic puzzle I wrote a program to encapsulate the logic and work out the numbers for me -- I'm not really a high-end mathematical genius and I couldn't have done it without lots of pain, otherwise (just warning you :). Oh, and for bonus points, solve the puzzle (find all possible solutions) for sums of <= 2000 ;) Audit NTFS permissions on Windows
 Shall I post the solution and/or code? [nt] (none / 0) (#145) by esrever on Mon Jan 24, 2005 at 08:02:33 PM EST

 Hint (none / 0) (#166) by raga on Wed Jan 26, 2005 at 12:21:26 AM EST

 I personally think this puzzle is fair for non-mathematicians only if it is accompanied by the hint that Goldbach's Conjecture is required for the solution. cheers- raga [ Parent ]
 SOLUTION (none / 0) (#187) by esrever on Mon Jan 31, 2005 at 07:14:11 PM EST

 Cutting a cube (none / 0) (#102) by flo on Sat Jan 22, 2005 at 06:14:54 AM EST

 Here's a nice problem: You have a 3x3x3cm wooden cube, which you want to cut into 27 1x1x1cm cubes, using a large circular power saw (i.e. you can only cut in a plane). You can do this with 6 cuts if you do not rearrange the loose pieces between cuts. If you do rearrange the pieces, can you do this with 5 cuts or less? For example, you can cut a 1x1x4cm block into 4 1x1x1cm cubes with only 2 cuts if you rearrange the pieces after the first cut. --------- "Look upon my works, ye mighty, and despair!"
 Impossible (3.00 / 3) (#112) by Morkney on Sat Jan 22, 2005 at 01:07:51 PM EST

 No single cut can include two faces of the center cube. [ Parent ]
 Hey, good argument. [n/t] (none / 0) (#134) by Fon2d2 on Mon Jan 24, 2005 at 10:31:17 AM EST

 [ Parent ]
 Yup. (none / 0) (#195) by flo on Tue Feb 08, 2005 at 02:41:10 AM EST

 That's the nicer argument. A second, slightly longer one goes like this: After the first cut, whatever it is, you will be left with 2 pieces, one of which needs to be cut into 9, the other into 18 cubes. But you need at least 5 cuts to cut the bigger one into 18 cubes, as each cut at most doubles the number of pieces, and 24 = 16 < 18. --------- "Look upon my works, ye mighty, and despair!"[ Parent ]
 nitpick (none / 0) (#161) by fourseven on Tue Jan 25, 2005 at 02:01:22 PM EST

 technically, it's impossible no matter how many cuts you make, because the blade of the saw has finite thickness. each cut takes away some of the material (turning it to sawdust), so the 27 cubes will be < 1x1x1. but that's a cheap shot.. [ Parent ]
 I'm assuming (none / 0) (#194) by flo on Tue Feb 08, 2005 at 02:34:21 AM EST

 a platonic saw, of zero thickness. This is maths, not physics :) --------- "Look upon my works, ye mighty, and despair!"[ Parent ]
 I give up. (none / 0) (#105) by i on Sat Jan 22, 2005 at 09:04:15 AM EST

 What's the solution to the rectangles puzzle? —and we have a contradicton according to our assumptions and the factor theorem
 Rectangles. (none / 0) (#110) by bgalehouse on Sat Jan 22, 2005 at 12:43:59 PM EST

 I guess that this has been up long enough that I can post an answer or two. Rectangle spoilers, or at least very strong hints, follow: The calc method is to consider the integral of the function exp(2 pi i(x+y)) over a rectangle. Specifically, look for a way to split the integral and think about when that product is zero. The other method is a bit harder to explain. First note that the statement is true in the special case that all coordinates are of the form n/p for any fixed prime p. This is because the number of little squares is either divisible by p or it isn't. Then think about what happens when we approximate any given rectangle diagram by rounding each point to the nearest (n/p,m/p) intersection. [ Parent ]
 Speaking of math grad students... (none / 0) (#113) by Edward Carter on Sat Jan 22, 2005 at 02:30:24 PM EST

 I saw this problem once in a graduate real analysis class. [ Parent ]
 Darn. (none / 0) (#114) by i on Sat Jan 22, 2005 at 02:32:45 PM EST

 I feel stupid. —and we have a contradicton according to our assumptions and the factor theorem[ Parent ]
 Geometric Proof? (none / 0) (#148) by Raistlin on Mon Jan 24, 2005 at 08:56:44 PM EST

 As someone else posted this is very easy to convince yourself of, but probably doesn't count as a rigorous proof. Take a rectangle and cut it into two rectangles as stated. Now the integer unit sides are either parallel or perpendicular. If they are paralell, then their sum is an integer unit length as well. If they are perpendicular then one of them shares an integer unit side with the larger rectangle. Dose this count as a geometric proof? [ Parent ]
 Addendum (none / 0) (#149) by Raistlin on Mon Jan 24, 2005 at 08:59:07 PM EST

 Oh yea, repeat using induction for more than one subdivision. [ Parent ]
 This doesn't work. (none / 0) (#150) by i on Tue Jan 25, 2005 at 02:52:40 AM EST

 You dont have to cut along entire top-to-bottom or left-to-right lines. You can cut a rectangular corner piece off the big rectangle.  _ | |_ |___| I guess you still can can reason along these lines, but it gets hairy pretty quickly. —and we have a contradicton according to our assumptions and the factor theorem[ Parent ]
 Continue the cut (none / 0) (#154) by Raistlin on Tue Jan 25, 2005 at 08:56:48 AM EST

 The problem states that all the rectangles in the larger one have this property. The shape you have left isn't composed of rectangles yet. In your case, you can continue the cut perpendicular to the integer unit side, so you have at that point: _ |_|_ |___| or _ | |_ |_|_| Once you have that, put in the piece you cut out and continue as I have described. I agee that it gets hairy, but if you have a fully defined rectangle composed of subrectangles, there is a way you can grab the smallest one and grow it using induction into the containing rectangle. [ Parent ]
 simple proof (none / 1) (#167) by relief on Wed Jan 26, 2005 at 02:01:09 AM EST

 posted here because it's related to your proof. this is also related to the second proof posted by the author. consider every continuous line segment to be another rectangle of width zero. color every rectangle that has integer height blue. (this includes all horizontal line segments) color every other rectangle red. it should be easy to see that the top and bottom edges of the large rectangle will be connected by the color blue, otherwise the left and right edges of the large rectangle will be connected by the color red. ---------------------------- If you're afraid of eating chicken wings with my dick cheese as a condiment, you're a wuss.[ Parent ]
 Assumption is wrong (none / 0) (#189) by Hykin on Thu Feb 03, 2005 at 09:42:59 PM EST

 Your assertion that there must be an unbroken line from top to bottom is not true: AAAABB AAAABB DDCCBB DDCCBB DDEEEE DDEEEE The example I gave made also proved my method wrong. [ Parent ]
 Not a proof (none / 0) (#156) by bgalehouse on Tue Jan 25, 2005 at 09:57:05 AM EST

 I don't see how to make your induction work for these diagrams. I say this because your induction seems to always leave us with two rectangles with a common side length. This doesn't preclude some induction for working, but might help explain why any such induction will be a bit tricky. [ Parent ]
 The Dark Room. (none / 1) (#129) by grendelkhan on Sun Jan 23, 2005 at 10:07:40 PM EST

 Perhaps the only truly justifiable use of Flash I've ever seen is The Dark Room. Your goal is to leave the room. That's it. No instructions, no hints, no words anywhere. It's a terrifically fun puzzle, and gave me a sense of "damn, I'm smartish" when I finally completed it. Even lets you save your progress to come back to later. Give it a shot. It's an impressive achievement for Flash, even if you don't like the puzzle. --grendelkhan -- Laws do not persuade just because they threaten --Seneca
 wow (none / 0) (#140) by EMHMark3 on Mon Jan 24, 2005 at 02:13:35 PM EST

 That was one nice puzzle :) Hardest room was the red room imo -- couldn't figure that one out without drawing everything on a piece of paper. Once you see the pattern it's pretty easy though.. T H E   M A C H I N E   S T O P S[ Parent ]
 difficulty (none / 0) (#175) by Arkaein on Thu Jan 27, 2005 at 09:16:51 AM EST

 I thought this puzzle was really tough (not to mention stupid) when I followed your link and was confronted with a black white rectangle on a black background, where no action did anything. Users wishing to avoid this fate may want to follow this alternative link, at least on Linux and Mac, and maybe just if you don't run IE. ---- The ultimate plays for Madden 2005[ Parent ]
 One from college (none / 0) (#130) by IceTitan on Mon Jan 24, 2005 at 02:40:16 AM EST

 The class was Calc I. Someone had forgotten basic fractions and had reduced a two digit numerator, two digit denominator fraction by crossing out opposite numbers. The resulting fraction turned out to be mathematically correct even though you can't actually do this. The teacher, a grad student, gave us extra credit for finding the other fractions of this nature. Some used brute force and found some, but I came up with a more elegant formula. For a fraction formed as ab/cd, where a,b,c and d are single digit integers that ab/cd reduced equals a/d or b/c. I forget the algebra required to solve this, but still a neat little problem. Nuke 'em from orbit. It's the only way to be sure.
 Well... (none / 0) (#132) by curien on Mon Jan 24, 2005 at 08:01:27 AM EST

 ab/cd is really (10a + b)/(10c + d). We want a fraction where that is the same as a/c or b/d, so: 10a + b     a -------  = --- 10c + d     c 10ac + bc = 10ac + ad bc = ad and 10a + b     b -------  = --- 10c + d     d 10ad + bd = 10bc + bd ad = bc So, you can do this for any two-digit numerator and denominator ab/cd where ad = bc. Ex: 48/36. -- This sig is umop apisdn.[ Parent ]
 I knew I was forgetting something. (none / 0) (#138) by IceTitan on Mon Jan 24, 2005 at 11:03:22 AM EST

 Or more precisely didn't explain it too well. Let me try again. (10a+b)/(10c+a)=(b/10c) (10a+b)/(10b+c)=(10a/c) That should be right. Nuke 'em from orbit. It's the only way to be sure.[ Parent ]
 Oh, I see what you meant now (none / 0) (#151) by curien on Tue Jan 25, 2005 at 03:54:30 AM EST

 And the algebra's similarly easy once you phrase the question that way. :-) -- This sig is umop apisdn.[ Parent ]
 OK, now help me out. (none / 0) (#152) by IceTitan on Tue Jan 25, 2005 at 04:59:24 AM EST

 I've forgotten more algebra than I care to admit. Nuke 'em from orbit. It's the only way to be sure.[ Parent ]
 This is all well and good... (none / 0) (#131) by tonyenkiducx on Mon Jan 24, 2005 at 05:48:38 AM EST

 ..but Im a complete none-event when it comes to maths. Give me a good logic puzzle any day and I'll do pretty good, but figures has always escaped me.. I'd like to see the solutions in a bit though, maybe hidden in a sub-comment, so I can feel even more inferior. Tony@Work. Tony. I see a planet where love is foremost, where war is none existant. A planet of peace, and a planet of understanding. I see a planet called
 It's been done but... (none / 0) (#139) by sethadam1 on Mon Jan 24, 2005 at 01:21:28 PM EST

 Here's a simple PHP solution to the locker problem: The solution and the source
 Additional Puzzles (none / 1) (#144) by Raistlin on Mon Jan 24, 2005 at 08:02:28 PM EST

 This story is probably dead, but I have a couple favorites as well... An engineer dies and finds himself in Hell. Having lived a semi-decent life, the devil gives him the chance to play him at a game to get out. The game the devil presents is a perfectly round table and a sufficently large pile of pennies. The rules are that the players take turns placing pennies on the table. The pennies cannot overlap. The first player that can not place a penny on the table looses. The engineer accepts the devil's game, with the restriction that he gets to go first, and then proceeds to get out of Hell. How did he do it? Assume a cylindrical cake. Everyone knows you can cut it into 8 pieces with four cuts. Can you do it with 3? If there is icing on the top and you want icing on every piece, can you still do it in 3? (Hint: yes you can)
 Cake (none / 0) (#158) by sab39 on Tue Jan 25, 2005 at 01:08:15 PM EST

 I can only get it into seven pieces with icing on every piece. That's assuming that you actually want cake in every piece as well (or alternatively that the icing is infinitely thin and you can't do a cut horizontally through it), and that the icing is only on the top. And that the cuts must be straight. I think I can (almost) prove that you can only get seven pieces given these constraints: Each cut must be a plane and must not be parallel with the plane of the icing (we've established it can't go horizontally through the icing, and if it were below then the pieces under the cut would have no icing). Thus each cut must intersect the plane of the icing at a single straight line. So the problem reduces to "can you divide a circle into eight pieces by three lines". This is where my "proof" gets a little fuzzy. It's obvious to me that if you eliminate the "circle" restriction, the way to slice a plane into the most possible pieces using three lines is to have them form a triangle, which gives seven areas (the inside of the triangle, one along each side, and one expanding outwards from each vertex). The only question is whether it's possible to place the circle somehow above this shape, or pick the shape of the triangle, such that one of those areas ends up with two pieces because of the curvature of the circle. But since the circle is convex, I don't think this is possible either. In other words, I dispute your claim that you can make eight pieces with icing using three cuts, at least without trickery. -- "Forty-two" -- Deep Thought "Quinze" -- Amélie[ Parent ]
 Depends on your definition of trickery (none / 0) (#159) by Raistlin on Tue Jan 25, 2005 at 01:21:04 PM EST

 This was presented as a "think outside the box" kind of problem, so you'll probably think trickery is involved. The answer is simple enough that you might be able to argue otherwise. The "trick"? Stack it. [ Parent ]
 Damn! (none / 0) (#160) by sab39 on Tue Jan 25, 2005 at 01:38:13 PM EST

 That's evil. Love it! -- "Forty-two" -- Deep Thought "Quinze" -- Amélie[ Parent ]
 Of course you don't actually have to stack it (none / 0) (#162) by sab39 on Tue Jan 25, 2005 at 02:33:55 PM EST

 Being able to rearrange the pieces within the plane is comfortably enough to achieve the desired result (cut it into four pieces with two cuts, place all of them in a straight line, then do one long cut that intersects all of them). -- "Forty-two" -- Deep Thought "Quinze" -- Amélie[ Parent ]
 You need to define the cuts (none / 0) (#186) by Vilim on Sun Jan 30, 2005 at 05:46:30 PM EST

 You have to specify that the cuts must be straight, otherwise I can cut a cake into an infinite number of pieces by first making a spiral where the distance between successive cuts is infitesimally small, then make one straight cut through the center. [ Parent ]
 Combinatorics/Number Theory (none / 0) (#146) by Coryoth on Mon Jan 24, 2005 at 08:29:14 PM EST

 You are given the task of choosing 100 different numbers between 1 and 200.  Show that if one of the numbers you choose is less than 16, then there must be at least 2 numbers in your chosen 100 such that one is divisible by the other. You can muddle through this, but there is potentially a fairly simple elegant solution (which is the interesting one you should be looking for). Jedidiah.
 a perl solution for the 24 problem (none / 0) (#147) by flargx on Mon Jan 24, 2005 at 08:41:24 PM EST

 I was too lazy to do it by hand, so I slapped together some perl.  This is by no means the most efficient way (or even a good way,) but it works and it only took a couple minutes to write..  Just pass it however many numbers you want to use as command line arguments.  So, to solve the posted problems try: perl ./foo.pl 1 3 4 6 perl ./foo.pl 3 3 8 8 I'll leave it to you to figure out how to read the output: ---begin perl #!/usr/bin/env perl                                                                                                   use List::Util qw(shuffle); \$answer=0; srand(time()+\$\$); if(\$#ARGV==-1) { die "Give me args!\n"; } while(\$answer!=24) {     my @nums=();     \$str="";     foreach \$x (@ARGV) { push(@nums,\$x); }     while(\$#nums != 0)     {         \$op=int(rand(4));         @nums=shuffle(@nums);         \$n1=shift(@nums);         \$n2=shift(@nums);         if(\$op==0)         { \$str.="(\$n1 + \$n2), ";           push(@nums,\$n1+\$n2);  }         elsif(\$op==1)         {             \$str.="(\$n1 - \$n2), ";             push(@nums,\$n1-\$n2);  }         elsif(\$op==2)         { \$str.="(\$n1 * \$n2), ";           push(@nums,\$n1*\$n2);  }         elsif(\$op==3)         {             if(\$n2==0)             { \$str.= "(divzero) ";               next; }             \$str.="(\$n1 / \$n2), ";             push(@nums,\$n1/\$n2);         }     }     \$answer=sprintf("%f",\$nums[0]); }     print "\$str = \$answer\n"; --end perl sorry about the formatting getting all strange.
 Another lazy coder (none / 0) (#153) by Have A Nice Day on Tue Jan 25, 2005 at 08:37:28 AM EST

 Here's your monkeys: #include int main(){     int y=0,c=0,x=0,p1,p2,p3,p4,p5;     while(1){         c = (y * 5);         if(c){             c = c/4;             p5=y/4;         }            if (!(c % 5)){             p4=c+1;             c = ((c+1) * 5)/4;             p4=c-p4;             if (!(c % 5)){                 p3=c+1;                 c = ((c+1) * 5)/4;                 p3=c-p3;                 if (!(c % 5)){                     p2=c+1;                     c = ((c+1) * 5)/4;                     p2=c-p2;                     if (!(c % 5)){                         p1=c+1;                         c = ((c+1) * 5)/4;                         p1=c-p1;                         if (!(c % 5)){                             x = c + 1;                             break;                         }                     }                 }             }         }         y += 5;     }     printf( "starting number: %dnfinal number split evenly: %dn"         "Pirate 1 takes: %dnPirate 2 takes: %dnPirate 3 takes: %dn"         "Pirate 4 takes: %dnPirate 5 takes: %dnMonkey takes: 5n",         x,y,p1+y/5,p2+y/5,p3+y/5,p4+y/5,p5+y/5);     return 0; } I know it's cheating and not the point of the exercise, but computers are fantastic tools for people who can't remember their advanced maths courses any more. The output is: starting number: 3121 final number split evenly: 1020 Pirate 1 takes: 828 Pirate 2 takes: 703 Pirate 3 takes: 603 Pirate 4 takes: 523 Pirate 5 takes: 459 Monkey takes: 5 Am I right or am I wrong? -------------- Have A Nice Day may have reentered the building.
 even lazier (none / 0) (#192) by cnicolai on Fri Feb 04, 2005 at 07:38:25 PM EST

 >>> def share(n): ...    if (n-1) % 5: ...       raise Exception() ...    else: ...       return (4*(n-1))/5 ... >>> for n in range(100000): ...    try: ...       rest = share(share(share(share(share(n))))) ...       if ( (rest % 5) == 0 ): ...          print n, rest ...    except: ...       pass ... 3121 1020 18746 6140 34371 11260 49996 16380 65621 21500 81246 26620 96871 31740 [ Parent ]
 Coconuts == Fish ? (none / 0) (#155) by bugmaster on Tue Jan 25, 2005 at 09:12:31 AM EST

 Wasn't it Dirac who first offered an elegant solution to the coconut problem (only with fishermen and fish not coconuts) ? I am pretty sure that's true, especially considering that it was Dirac who predicted the positron... >|<*:=
 Didn't originate with Dirac (none / 0) (#163) by rpresser on Tue Jan 25, 2005 at 07:41:06 PM EST

 According to Martin Gardner, who told this story and gave the elegant solution, "This solution is sometimes attributed to the University of Cambridge physicist P.A.M. Dirac (1902-1984), but in reply to my query Professor Dirac wrote that he obtained the solution from J.H.C. Whitehead, professor of mathematics (and nephew of the famous philosopher). Professor Whitehead, answering a similar query, said that he got it from someone else, and I have not pursued the matter further." The Colossal Book of Mathematics, p. 5. ------------ "In terms of both hyperbolic overreaching and eventual wrongness, the Permanent [Republican] Majority has set a new, and truly difficult to beat, standard." --rusty[ Parent ]
 This is a good one (none / 0) (#165) by jambarama on Tue Jan 25, 2005 at 10:11:19 PM EST

 A gambler starts with \$100 and he plays a game as follows: For each bet he flips a coin, if it lands heads, he gets a dollar. If it lands tails he loses a dollar. He will only quit when he has no money at all, or if he has \$200. On average how many times will have have to play before he finishes? I've not found a nice way to do this, if you do, please email me at smg57 AT byu.edu and we can compare answers.
 Random walk. (none / 0) (#169) by cakoose on Wed Jan 26, 2005 at 03:29:43 PM EST

 This is called a "random walk". You can look it up in a probability textbook. [ Parent ]
 an answer, sort of (none / 0) (#171) by flargx on Wed Jan 26, 2005 at 03:47:29 PM EST

 As someone else replied, random walk is the way to go.  I'm too lazy to do math, so I did this instead: #!/usr/bin/env perl \$avg=0; \$navg=0; srand(time()+\$\$); while(1) {     \$cycle=0;     \$tot=100;     while(!(\$tot==0 || \$tot==200))     {         if(int(rand(2))) { \$tot++; }         else             { \$tot--; }         \$cycle++;     }     \$avg=(\$avg*\$navg+\$cycle)/(\$navg+1);     \$navg++;     printf("[\$navg] Reached %3.3d in %7.7d cycles [avg=%.2f]\n",\$tot,            \$cycle,\$avg); } -- And it seems to work out to around 10000ish [ Parent ]
 Wald's Lemma (none / 0) (#191) by escargot on Fri Feb 04, 2005 at 11:05:52 AM EST

 The problem can be solved using Wald's second lemma, since this particular random walk is a martingale. Let Z_i be the outcome of each coin flip, and S_n be total winnings at time n, and N be the stopping time in question, then E[N]=S[S_N^2]/E[Z_1]=1/2*40000=20000. -escargot [ Parent ]
 Coconut problem (spoiler) (none / 0) (#168) by dfenwick on Wed Jan 26, 2005 at 02:44:49 PM EST

 The coconut problem was fun to solve. The initial count is solvable for any number of sailors, and there are multiple solutions by simply adding NN+1 to the previous answer. The following formula is for the initial number of coconuts possible on the island: coconuts = SailorsSailors - (Sailors - 1) Thereafter, each answer is: coconutsn = coconutsn-1 + SailorsSailors + 1 The progression for 5 sailors looks like this: 3121 18746 (3121 + 15625) 34271 (18746 + 15625) 49996 (34271 + 15625) 65621 (49996 + 15625) 81246 (65621 + 15625) 96871 (81246 + 15625) And so on. So there really isn't a specific answer to the problem. If the question was "What is the smallest number of coconuts that were on the island?" the answer would be 3121. But the answer to the question as it was posed is there are an infinite number of answers to the problem (provided the island was big enough). :)
 Minor fix to coconut formula (none / 0) (#173) by dfenwick on Wed Jan 26, 2005 at 09:55:24 PM EST

 The formula: coconuts = SailorsSailors - (Sailors - 1) only works for odd numbers of sailors. For an even number of sailors, the formula is: coconuts = (SailorsSailors + 1 - SailorsSailors) - (Sailors - 1) I'd have to go back and do the math on why this is, but I believe it's about the constant distribution to the monkey per iteration that causes it. It also does not work for sailors = 2. Anyone have a more generalized formula for this? [ Parent ]
 Gardner's formulas (none / 1) (#180) by rpresser on Thu Jan 27, 2005 at 08:35:24 PM EST

 For the problem where the monkey gets a last distribution, he gives the formula N = nn+1 - (n - 1) where   N = initial number of coconuts   n = number of sailors For the problem where the last division comes out even, so the monkey gets no coconut that morning, he gives the formula   N = (1 + nk)nn - (n - 1)  for n even   N = (n - 1 + nk)nn - (n - 1)   for n odd "In both equations k is the parameter that can be any integer. In Williams's problem the number of men is 5, an odd number, so 5 is substituted for n in the first equation, and k is taken as 0 to obtain the lowest positive answer." For n=2, if k is taken as 0, this gives a result of N=2, which implies that in the morning there are no coconuts to divide.  If this answer is not allowed, setting k=1 gives the next answer of N=11, which works.  Likewise, when n=1, k has to be 2 if the man is to get any coconuts at all on each of the 2 divisions. Working in Excel, I did this as a table: ```  n   k             N   monkey  last sailor gets   first sailor gets  1   2             3   1                    1             1  2   1            11   2                    3             6  3   0            25   3                    5            10  4   0           765   4                  140           251  5   0          3121   5                  459           828  6   0        233275   6                28644         51899  7   0        823537   7                86645        157638  8   0     117440505   8             10809000      19724263  9   0     387420481   9             31690295      57959800 10   0   89999999991  10           6624890360   12138105959 ``` Now that's a lot of coconuts. ------------ "In terms of both hyperbolic overreaching and eventual wrongness, the Permanent [Republican] Majority has set a new, and truly difficult to beat, standard." --rusty[ Parent ]
 Excellent (none / 0) (#181) by dfenwick on Thu Jan 27, 2005 at 09:24:41 PM EST

 I didn't know someone had already proved it, but thank you for this. I did the math by hand and although I knew there was a different formula for odds/evens, I couldn't work out a definitive math for all cases including 1 and 2. Appreciate the feedback. [ Parent ]
 1926 (none / 0) (#183) by rpresser on Sat Jan 29, 2005 at 01:49:54 PM EST

 Gardner says the problem (in the no-coconuts-morning version) was published in the October 9, 1926 issue of The Saturday Evening Post, as part of a short story, and that the other version (where the monkey does get a morning coconut, making the problem easier to solve) is even older (though he gives no date). ------------ "In terms of both hyperbolic overreaching and eventual wrongness, the Permanent [Republican] Majority has set a new, and truly difficult to beat, standard." --rusty[ Parent ]
 are you sure about those numbers? (none / 0) (#184) by xpi0t0s on Sun Jan 30, 2005 at 07:47:13 AM EST

 > N=3121 first sailor gets 828 For 3120/5 I get 624, not 828. Or did I misunderstand something (not impossible)? [ Parent ]
 Yes, you missed something (none / 0) (#185) by rpresser on Sun Jan 30, 2005 at 11:46:42 AM EST

 In addition to the 1/5 he gets in the middle of the night, he also gets 1/5 of what was left in the morning after the other 4 sailors have stolen their portions. ------------ "In terms of both hyperbolic overreaching and eventual wrongness, the Permanent [Republican] Majority has set a new, and truly difficult to beat, standard." --rusty[ Parent ]
 I can't get the initialization one (none / 0) (#170) by p3d0 on Wed Jan 26, 2005 at 03:38:35 PM EST

 I'd like to know your answer for the initialization one. I'd wager it's wrong, or it presumes the existence of a primitive that can clear O(n) memory in constant time. Or, it could just be a trick question. The complexity of an algorithm is usually expressed in terms of the size of the input, so if you consider the array itself to be the input to this algorithm, I can clear it in O(1) time. :-) -- Patrick Doyle My comments do not reflect the opinions of my employer.
 It's doable. (none / 0) (#172) by i on Wed Jan 26, 2005 at 07:09:47 PM EST

 If your language insists on initialising all variables, it's hard to avoid O(n) the first time around, but after that, the clear operation can be easily made O(1). Search the comments in this article, there's a link to a solution in one of them :) —and we have a contradicton according to our assumptions and the factor theorem[ Parent ]
 Stupid me (none / 0) (#176) by p3d0 on Thu Jan 27, 2005 at 10:28:22 AM EST

 "Describe a set of data-structures and provide the operations..." I thought they had already provided the data structure: an array in the C sense. I didn't realize they were asking for a sparse array implementation. -- Patrick Doyle My comments do not reflect the opinions of my employer.[ Parent ]
 You don't need to rearrange it either (none / 0) (#177) by Psidefect on Thu Jan 27, 2005 at 04:11:50 PM EST

 As long as horizontal are allowed, you don't need to rearrange anything. Just cut into four with two cuts, then cut in a plane parallel to table top.
 Sorry, I'm a moron. (none / 0) (#178) by Psidefect on Thu Jan 27, 2005 at 04:21:36 PM EST

 The previous post was in response to sab39's comments here [ Parent ]
 Wow (none / 0) (#179) by Psidefect on Thu Jan 27, 2005 at 04:26:54 PM EST

 ...and I didn't read the problem correctly. My solution does not get icing on each piece. *puts the cork back on the fork* [ Parent ]
 Warriors and Explorers (none / 0) (#182) by k31 on Fri Jan 28, 2005 at 07:26:06 PM EST

 There's an old puzzle that goes something like this: There's a river, which can only be crossed by a canoe, which itself holds up to 3 people. A group of explorers and a group of warriors want to switch banks, but there is the contraint that if they are ever more warriors than expolorers either in the canoe or on either bank, then they will overpower and utterly destroy the explorers. What sequence will allow the two groups to exchange banks within this constraint? Your dollar is you only Word, the wrath of it your only fear. He who has an EAR to hear....
 Answers. (none / 0) (#188) by MELo on Wed Feb 02, 2005 at 05:09:29 PM EST

 Will you post the answers?
 Heres a puzzle for ya (none / 0) (#190) by GRiNGO on Fri Feb 04, 2005 at 07:15:03 AM EST

 The Rules are: *Only 2 persons on the raft at a time *The father can not stay with any of the daughters without their mother's presence *The mother can not stay with any of the sons without their father's presence *The thief (striped shirt) can not stay with any family member if the Policeman is not there *Only the Father, the Mother and the Policeman know how to operate the raft To start click on the big blue circle on the right. To move the people click on them. To move the raft click on the red circles. :thumb: http://www.gsart.com.br/midia/riverIQGame.swf -- "I send you to Baghdad a long time. Nobody find you. Do they care, buddy?" - Three Kings
 That was horrid (none / 0) (#193) by kerinsky on Fri Feb 04, 2005 at 10:46:04 PM EST

 I kept assuming that the prisoner could never be without the cop, not just that she couldn't be with civilians without a cop.  I mean I beat the puzzle and left the prisoner alone, on her own side of the river without the cop, TWICE!  What sort of moronic prisoner is this, she can just waddle off and go beat up civilians to her heart's content once the friggen cop is on the other side of the river!  Does she just have a deathwish in for this ONE family?!  If so what sort of moronic cop is transporting him with that family?! Absurd, patenly absurd! -=- A conclusion is simply the place where you got tired of thinking.[ Parent ]
 flash puzzles (none / 0) (#197) by afraser on Thu Feb 10, 2005 at 01:52:08 AM EST

 Does anyone know any other flash puzzles like this on the web? that one was fun. [ Parent ]
 Gargamel curses the smurfs... (none / 0) (#196) by afraser on Thu Feb 10, 2005 at 01:48:42 AM EST

 My favourite puzzle goes like this: Every day at noon, all the smurfs in the village meet in the center square to talk. Afterwards, they scatter and go about their business until the next day at noon. One day Gargamel throws a curse on all the smurfs (all n smurfs). First, he prevents *all* forms of communication between the smurfs. Second, he gives r smurfs red hats, and n-r smurfs white hats. Each smurf can see the color of every other smurf's hat. Each smurf can not see the color of his own hat. Gargamel says the spell will only be broken if on a particular day, all the smurfs with red hats spontaneously travel together to the top of a mountain. If any red-hatted smurf does not join the others, the curse will remain on the village forever (remember you can't see your own hat and nobody can tell you what color it is). Now, the smurfs are a mathematically deductive bunch and even though they can not communciate, they know that each smurf will do the right thing. How many days elapse before all the red-hatted smurfs travel together to the top of the mountain to break the curse?
 Puzzles! | 198 comments (193 topical, 5 editorial, 0 hidden)
 Display: Threaded Minimal Nested Flat Flat Unthreaded Sort: Unrated, then Highest Highest Rated First Lowest Rated First Ignore Ratings Newest First Oldest First

All trademarks and copyrights on this page are owned by their respective companies. The Rest © 2000 - Present Kuro5hin.org Inc.