Authentic Personal message at 01:32:31 on Mon Apr 15 1991 From: Eric A Lehman on EGGHEAD.MIT.EDU To: mosquito@ATHENA.MIT.EDU Gosh, let's see... Suppose I have a bunch of blocks (unit cubes) that I can assemble into a cube. Is it possible to arrange the same set of blocks into an octahedron-like shape? (Do you know what I mean by "octahedron-like"? the volumes of the first few are 1, 7, 25, and 63...) Someone says he thinks the answer is "no", but can't prove it. Do you know the game xmines? Authentic Personal message at 01:33:14 on Mon Apr 15 1991 From: Eric A Lehman on EGGHEAD.MIT.EDU To: mosquito@ATHENA.MIT.EDU Hey, do you know how to find the median of a set of numbers in linear time? Authentic Personal message at 01:35:26 on Mon Apr 15 1991 From: Eric A Lehman on EGGHEAD.MIT.EDU To: mosquito@ATHENA.MIT.EDU You know the problem of finding the distance between two points randomly placed on a square (expected distance, that is)? I think there is an elegant solution, but I don't know it. Here's a derivative: In terms of the previous answer, what is the average distance (expected) between pairs of points if I put down n points on the square? Authentic Personal message at 01:37:04 on Mon Apr 15 1991 From: Eric A Lehman on EGGHEAD.MIT.EDU To: mosquito@ATHENA.MIT.EDU (== denotes congruence) What values of n (0...124) can satisfy the congruence n == x^100 (mod 125)? Give as short a proof as possible. === Suppose you put them into a tree like this: each node would have *smaller *larger numsmaller numlarger initialized to nil,nil,0,0. You have the root node assigned to the first one. You take the next one, and do a compare. If it's smaller, point the *smaller at it. Then increment numsmaller. Also, keep track of how many are in the set if you don't already know that. Similarly, if it's larger, point *larger at it, etc. You have now taken linear time to put this tree together. You look at numsmaller and compare it with the total/2 to see which way you should go. You go down the appropriate branch, etc. avg of this step: log n ish, worst case: n ish (Actually you don't need numlarger, but that's okay . ealehman: Message sent Authentic Personal message at 01:45:06 on Mon Apr 15 1991 From: Eric A Lehman on EGGHEAD.MIT.EDU To: mosquito@ATHENA.MIT.EDU On the octahedron problem: Does there is exist a number which is both a perfect cube and an octahedral-number. median: Yes, there are no bounds on the numbers (!) Here is an xmines puzzle that came up while I was writing a program to play the game. My method is this: For each square on the boundary, guess that the square is a mine. Apply the rules below until no futher conclusions can be made or a contradiction is reached. If a contradiction is reached, conclude that the square is acutally safe. If there is no contradiction, try supposing that the square is safe. Apply the rules below again. If you get a contradiction, conclude the square is actually a mine. Otherwise it is indeterminate. Rules: If the number of a square = number of adjacent unknowns + number of uncovered adjacent mines, conclude that all the unknown squares are mines. If the number of a square = number of uncovered adjacent mines, conclude that all the adjacent unknown squares are safe. I apply these rules recursively, so all the "obvious" conclusions are reached. The question is this: Is this technique perfect? Aside from certain ... (forget that) Is is ever possible to make a logical inference which is not detectable by this method? (Aside: The major weakness of the game-playing program at the moment is that is doesn't guess well at all :) ) The weather thing is :)