Friday Puzzle #7

20 10 2011

A train approaches an observer at the speed of 100 km/h.  The observer tosses a tennis ball at the speed of 100 km/h towards the train.  What will be the speed and direction of the tennis ball after it has bounced off of the collision with the train.  All idealizations apply (bouncing consumes no kinetic energy; front of train is flat and vertical; friction is ignored; train/ball weight ratio is practically infinite; etc.)



Solution To Friday Puzzle #6

9 10 2011

Let black squares have value 1 and white squares have value -1. The entire chessboard has now turned into a base -1 multiplication table of its first row and first column. For example, if a white first row square (having value -1) contains a pawn, and another first column square that is black (having value 1) contains a pawn, then the square on the intersectiong row and column will have value 1*-1 = -1 and hence will be white. Try it with other color combinations as well!

Creating the diagonally symmetric square pattern described in the puzzle is therefore equivalent to computing the square – the 2nd power – of the number designated by the first row. If the first row has 2 blacks and 4 whites then its value is 2*1 + 4*-1 = -2 , the square of which is 4 .  Effecticely this means that four more black squares (+1) are covered than white square (-1) by the complete pattern. Note that the 2nd power can never be negative which means that there can never be more white squares covered than black squares.

So the question of the smallest board containing a difference that is a prime numer is equivalent to asking for the smallest 2nd power of an integer that is a prime, which obviously does not exist. Hence my intended answer was that there is no solution.

However, one reader pointed out to me offline that a square with 1 pawn in (0,0) should qualify as an answer. Intriguing! Some googling quickly revealed that there have been different definitions historically of what is a prime number. The best explanation is provided by Wikipedia:

Most early Greeks did not not even consider 1 to be a number, so clearly did not consider it a prime. In the 19th century however, many mathematicians did consider the number 1 a prime. For example, Derrick Norman Lehmer’s list of primes up to 10,006,721, reprinted as late as 1956, started with 1 as its first prime. Henri Lebesgue is said to be the last professional mathematician to call 1 prime. Although a large body of mathematical work is also valid when calling 1 a prime, the fundamental theorem of arithmetic does not hold as stated. For example, the number 15 can be factored as 3 · 5 or 1 · 3 · 5. If 1 were admitted as a prime, these two presentations would be considered different factorizations of 15 into prime numbers, so the statement of that theorem would have to be modified.

For the reason stated in the last sentence of the above quotation (i.e. preserving unique factoring) the contemporary definition of a prime number explicitly excludes 1 from the set of primes. But because I failed to specify the definition of primes relevant to this puzzle, I feel compelled to accept her solution as a correct one.

Friday Puzzle #6

6 10 2011

A chess board has 8*8 squares with alternating black/white colors. The rows are labeled 1-8 and the columns are labeled A-H. The square A1 is black.

However, for the purpose of this week’s friday puzzle, let’s re-label the rows and columns with numbers starting from zero. Then, square (0,0) is black, as well as (1,1), (2,2), etc. Also, the chess board is not restricted to 8*8 squares, it can be arbitrarily large (yet finite), or N*N in size.

Then place pawns on the board according to the following rules:

  • Square (0,0) contains a pawn
  • If and only if square (0,X) contains a pawn, then square (X,0) contains a pawn
  • If and only if both squares (R,0) and (0,S) contain a pawn, then square (R,S) contains a pawn

When the pawns are correctly configured the total number of pawns will be a square number, and they will form a diagonally symmetric pattern. Some pawns will occupy a white square and others will occupy a black square. Call their difference the target.

The puzzle: What is the smallest board where a pattern can be created whose target is a prime number?

Solution To Friday Puzzle #5

3 10 2011

In short, the answer is Yes.  A 2*164 box can contain 329 bottles. I won’t dig into the math, but instead I’ll offer a link to Wolfram Demonstrations where the solution is nicely visualized.

Happy work week everyone!

Friday Puzzle #5

29 09 2011

A bottle has diameter of 1 unit.  A box having size 2*2 units can contain four bottles at most.  A box having size 2*3 units can contain six bottles at most. A box having size 2*4 units can contain eight bottles at most. Et cetera…

Is there a box having size 2*N units that can contain more than 2*N bottles? Can you suggest an upper limit for N? Can you compute and prove (or at least justify) a minimum value for N?

Factoring Integers In O(1) Time

27 09 2011

They say that factoring integers is hard. Well, what do they know – this article presents a program which takes an integer (at compile time) and prints its factors in O(1) time. If the number has multiple factors then just one pair will be printed. If the number is prime, then the number itself, times one, will be printed.

Naturally it is impossible to compute factors of an integer in constant time. The trick used here is called Template Metaprogramming. Template metaprogramming is essentially creating a set of C++ templates which encode a program. Algorithms can be represented by a handful of template metaprogramming idioms – there are idioms for conditionals, recursion, expression evaluation, data passing, and more – and if the template is instantiated anywhere in the code, the metaprogram is executed by the compiler at compile time. At this point it is worth noting that template metaprograms cannot contain mutable values; therefore it is impossible to metaprogram regular index-based loops, but recursion must be used instead. This means that trees can be more economical data structures than linear arrays or lists, because the latter needs much more “stack space” (=simultaneously instantiated template objects) than e.g. tree. Anyway, in order to create a program which apparently factors integers in constant time, a vastly greater compilation time must have passed to compute the actual result, but the result is eventually stored into the program code as a plain old constant value.

The most canonical factoring algorithm is trial division. However, in this article I’ve decided to use the Unusual Recursive Factoring Algorithm instead because it uses more economical tree traversal, as opposed to indexed loop needed in trial division. Alas, my fear was unfounded: it seems that the modern compilers (I used MS Visual C++ Express 2010) no longer have limitations to the number and/or depth of template instantiations which they had when I first tried this code for real.

Anyway, here’s the code.

Solution To Friday Puzzle #4

26 09 2011

Reader yrpe was the first to post the correct answer to Friday Puzzle #4.  This is their answer, slightly paraphrased:

Given any two cards there is exactly one card that competes the set, so the answer is 1/79 .