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.

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!

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 .

Solution To Friday Puzzle #3

19 09 2011

John: “Hi, Mary, how’s it going?”

Mary: “Fine, thanks. Have you been thinking of that spinner problem someone blogged about on Friday?”

John: “Tell you what, I was just going to ask you the same. You wanna try solving it using the Monte Carlo method?”

Mary: “Monte who?

John: “Heehee…  Monte Carlo method is an experimental way to get approximate solutions to problems about probabilities. You repeat an experiment over and over and over, and make notes about the outcomes. When you have repeated the experiment a great many times you will have a pretty good idea of the probability you are trying to figure out. For instance, if you toss a coin ten times you may get 7 heads and 3 tails, but if you toss the same coin 10,000 times you may get 5,014 heads and 4,986 tails. The ratio will converge to 1/2 just like it should if the coin is good.”

Mary: “All right, let’s try it out. Hey, wait a minute, we don’t have any axles or blades to make spinners out of. How you gonna experiment with a device with… no device?”

John: “Mind you, I’ve thought of that, too! See, here are three pencils. Two of them are green and one is red. If the axles are called A and B, and the point at which the blades are pointing to is X, then the distance |AB| =1 must be greater than both of the distances |AX| and |BX| or else the blades can’t overlap.  In other words, the simulated blades will overlap if and only if the length |AB| is the longest side of the triangle ABX.”

Mary: “A-ha, I see now: I’ll toss the pencils on the floor, the pencils will define three straight lines, and those three lines together will define a random triangle.”

John: “Exactly! And next consider the red pen as the base between the axles and the green pens as the blades, then the experiment is successful every time when the red pen defines the longest side of the resultant random triangle. Count successes and divide by total numer of experimentations and voila, Monte Carlo method in action! Let’s start, toss the pencils, Mary.”

Mary: “But…”

John: “Yes I know we have a long task ahead of us so lets just start.”

Mary: “But…”

John: “Please, Mary, the longer we argue the longer it takes to find out the approximate solution. You do want to find it out, don’t you?”

Mary sighs and tosses the pencils.

John: “Well?”

Mary: “Well…”

John: “Well?”

Mary: “Well… ummm… errr… I am sorry. I was trying to tell you that I am color blind. I can’t tell apart red and green, but I can say that because there are three pencils, the red pencil defines the longest side of the triangle with probability 1/3.”

John is at loss of words in face of Mary’s spontaneous insight.

So the answer to Friday Puzzle #3 is that the blades overlap with probability P=1/3. Also, my apologies for failing to supply the solution by Sunday like promised.

Solution To Friday Puzzle #2

11 09 2011

Kudos to Al Nikolov, who was the first to correctly answer the Friday Puzzle #2.  The answer is indeed P=1/2, meaning that there is fifty-fifty chance that the Grumpy Old Man will get their seat without fuss.

Here’s the intuitive reasoning: When a businessman finds that their seat is already occupied by someone else and randomly takes another seat, he becomes the virtual Silly Old Lady and the real Silly Old Lady becomes a virtual Energetic Businessman. This adjustment does not affect the outcome but it helps to see that only one person (the real or virtual Silly Old Lady) will ever occupy a wrong seat. For as long as the real or virtual Silly Old Lady takes a seat that belongs to a businessman they will eventually have to move again. But as soon as the real or virtual Silly Old Lady takes either their own seat or the seat that is assigned to the Grumpy Old Man, then all remaining businessmen will be able to board the plane without fuss. Therefore, when Grumpy Old Man enters the plane there are two equiprobable statuses:

  1. All businessmen sit on a seat assigned to some businessman, and the Silly Old Lady sits on the seat assigned to herself
  2. All businessmen sit on a seat assigned to some businessman, and the Silly Old Lady sits on Grumpy Old Man’s seat

Because these two statuses are equiprobable, the answer is 1/2.


Solution To Friday Puzzle #1

4 09 2011

Not too many attempts to answer the puzzle were posted, but I hope you have pondered it anyway. Nevertheless, here’s my solution (hosted in What I consider particularly elegant in the solution of the Hard Part is the unusual opportunity to reuse the entire solution of the Easy Part:

ReverseString( pString + n );

ReverseString( pString );

ReverseString( pString + strlen(pString) – n );

For example, rotating the string “Hello, World!” by 3 steps generates the following intermediate strings:

  • “Hello, World!” >> reverse 3..n
  • “Hel!dlroW ,ol” >> reverse 0..n
  • “lo, World!leH” >> reverse n-3..n
  • “lo, World!Hel”

Isn’t that neat!