Montana, where are you?

This blog gave me two nice surprises for Christmas: the first visitor from Algeria and the first visitor from North Dakota.

Now, I am only missing visitors from one of the United States: Montana.

If any of you knows somebody who lives in Montana or happens to make a trip to the headwaters state and connects to the Internet, it would be nice to have the remaining US-state flag...

DNA

Some days ago, I started reading the book "The Making of the Fittest" by Sean B. Carroll and I cannot put it down.  Finally, a book that explains how the study of DNA proves beyond any doubt that Darwin was right with his theory of evolution.  A clear and uncluttered explanation of how DNA works.  In fact, I like it so much that I will try to summarise it (!) here.

DNA consists of a double chain (or "strand") of compounds called "Nucleotides" (although, to be precise, not all compounds called nucleotides are to be found in DNA).  A nucleotide (also called "Base") is a simple molecule with one or two dozen atoms.  Four bases exist: Adenosine (A), Cytidine (C), Guanosine (G), and Thymidine (T).

Each base in a strand is linked via a Hydrogen bond to a base in the other strand: the As are linked with Ts and the Gs are linked with Cs.  That's how the two strands of DNA are kept together.  This means that for every A in one strand, there is a corresponding T in the other strand, for each C a G, for each G a C, and for each T an A.  Therefore, each strand contains the same information.  In other words, a DNA molecule contains the same information twice, once in each strand.  That's why you will find in the literature the description of DNA as consisting of "base pairs".  The Human DNA consists of about three billion base pairs.

A "gene" is a sequence of about 1200 base pairs that contain the information to build a protein, and humans have something between 20,000 and 25,000 genes.

A chromosome is only the name given to a portion of DNA.  That is, the fact that we have twenty-three chromosomes only tells you that our Genome (collective name for all our genes) is not contained in a single molecule of DNA but in a series of separate double-strands.  Chromosomes are important but, somehow, I don't find them very interesting, although, I might change my mind.  You can find a list of the number of genes and base pairs in each human chromosome here: http://en.wikipedia.org/wiki/Chromosome.

When a cell wants to generate a protein (don't ask me when and why that happens), it "transcribes" the sequence of one of the DNA strands of the corresponding gene into a single strand of what is called "messenger RNA", or mRNA.  mRNA is a sequence of nucleotides similar to a DNA strand, and repeats the DNA sequence of the gene but with an A for each T, a C for each G, a G for each C, and a U (Uracil, another nucleotide) for each A.

Proteins are chains of simpler compounds called "Amino Acids", which are quite simple molecules containing nitrogen.

The cell "translates" the strand of mRNA into the corresponding protein, one amino acid at a time.  To do so, it scans the nucleotide sequence of the mRNA in groups of three, and each triplet (which is called a "codon") of nucleotides identifies a particular amino acid.

Let's see: there are four different nucleotides in mRNA (A, C, G, and U).  Therefore, a group of three nucleotides can identify 4 x 4 x 4 = 64 amino acids.  In fact, there are only 20 amino acids (which is very convenient, because they can be identified by a single letter of the alphabet, as shown in http://en.wikipedia.org/wiki/Aminoacid).  This means that several triplets of nucleotides identify the same amino acid.  Note that pairs of nucleotides (instead of triplets) would have not been enough, because they could have only identified 4 x 4 = 16 amino acids.  In any case, there are also some codons that are used to "stop" a sequence.  When the molecule encounters a stop codon, it stops building up the protein.

Obviously, as each gene has on average some 1200 bases and three bases are needed to identify an amino acid, the average protein contains 1200 / 3 = 400 amino acids.

It turns out that about half of our DNA is "junk", left behind by genes that were no longer needed and have decayed due to natural mutation or resulting from the random duplications that often occur.

As you might have heard, evolution is due to variations (i.e., DNA mutations), selection, and time.  DNA frequently mutates for various reasons (for example, when a nucleotide is replaced by a different one), but it can also happen that entire sequences of base pairs are either duplicated or lost.  If the "new" gene is viable, the corresponding protein sometimes turn out to be advantageous for the carriers of the mutated gene.  In those cases, if the gene is passed on to enough new members of the species, even a little advantage can, after enough time, cause a complete replacement of the "old" gene.

Even minute advantages due to the presence (or absence) of a gene have, on the long run, significant effects.  Einstein (I believe) compared them to compound interest: even a small percentage, over many years, can result in substantial figures.  And evolutionary periods are measured in centuries and millennia, when not in millions of years.

If the mutation is damaging, the same mechanism of natural selection "purges" the DNA.  That's how some genes have remained unchanged for, literally, billions of years and can be found in almost all species.

It can also happen that, due to mutated environmental conditions, a particular gene ceases to be advantageous.  In those cases, natural selection no longer operates.  With time, as the gene mutates, there is no longer a mechanism to purge the DNA of those mutations that make the gene unviable.  As a result, eventually, all genes that cease to be advantageous decay and become irrelevant.  These fossil genes contribute to the junk base pairs in our DNA.

The fact that genes disappear is a big blow to the proponents of "Intelligent Design".  Isn't it?

There are genes that provide the material needed for our organs, and genes that regulate how those proteins are organised.  How these regulating genes do their job depends on a series of base-pair sequences in our DNA (called "Switches"), like a computer program depends on its parameters.  Changes in those switches can result in dramatic differences at the macroscopic level, because they also set things like the number of limbs.

Fascinating!

Lacing Shoes

Almost one and a half years ago, I posted an article about how to fold toilet paper (Toilet paper woes).  Today, I would like to write about another simple task that often doesn't receive much attention (except by me, that is): how to lace shoes.

After deciding to write about this neglected subject, I discovered a great website entirely dedicated to the different techniques for lacing up shoes: Ian's Shoelace Site.  Very thorough a professional.

Perhaps not surprisingly, the discovery of Ian's site didn't deter me from writing here my reflections on the subject.  Ian shows diagrams for 36 different ways to lace shoes, but I will concentrate on the three methods that, as far as I can see, are used by the vast majority of people.

Here is the first method, in which one side of the lace spirals through all eyelets and the other side goes through to one of the two top holes:

The advantage of this method is that, if the two sides can come close together, the loops are parallel to each other.  This appeals to many, and I have often found that this method is applied by salespeople.  Perhaps they do it because, with this method, you don't need to count holes.

I hate this method.  After a while, it tends to skew the holes, as one of the bottom ones is strongly pulled towards the top.  It is also somewhat more difficult to open up the shoe, and the side of the lace that loops through tends to remain loose in the middle.  Besides, I like symmetry.

One variation of this method is as follows:

As you can see, both sides loop through each second pair of holes.  The loops remain parallel in front, while the skewing effect is significantly reduced.  But I still don't like it, because it remains asymmetrical and (don't ask me why) somewhat unnatural.

The third method I would like to show you is completely symmetrical.  Here it is:

In the example shown, the lace always go through the eyelets from the outside to the inside.  This is in fact a variation of the most common technique, in which the lace starts from the inside and always go through from the inside to the outside.  The result is a zip-like pattern that is quite pleasing.  Like in the previous cases, it doesn't require you to count the holes.  But it has two disadvantages.  The first one is that you cannot bring the two sides of the shoe completely together.  It is not a problem in the example, but I had sometimes shoes in which the two sides even overlapped.  The second disadvantage is that the two sides of the lace rub against each other, thereby making it somewhat more difficult to open and close the shoe.

The final method is the one that I consistently use.  Although, for the best effect, it requires you to count the holes (in, out, in, ...), it represents in my opinion the most pleasing solution in terms of symmetry, low friction, and applicability.

It is also nice to see the Xs formed by the laces inside.  Or not?

A Puzzling year indeed

In yesterday's article, I forgot to say that in 2011 I also developed a CalcuDoku-solving game for the iPad (search iTunes for CalcuDokus and you'll find it in your local iTunes store).

I first made a $0.99 version with 100 puzzles, and then a free version with 17 puzzles and advertisements.

Despite my attempts at getting some review sites to look at it, the results were quite disappointing.  Apple's AppStore is saturated with applications, and it has become very difficult to get noted.  Big games-developing companies systematically hit jackpots, but nanodevelopers like me have close to no chance.

Far from me the idea that my application is exceptionally good and overlooked.  But I am pretty sure that a couple of years ago, it would have sold reasonably well.  So, why did I wait for 2011 and a saturated market before developing for the iPhone/iPad?  Because I am stupid.  That's why.  I did the same with the Web: in the early nineties, instead of being one of the first web developers on the market, I developed an application for the Mac (MacDOS) that went nowhere.

Another missed opportunity...

A Puzzling Year

This has been a year during which I have concentrated on developing puzzles and writing about it.  I had always been interested more in developing programs to generate and solved numeric puzzles than to solve the puzzles themselves.  Towards the end of 2010, I finally dedicated myself to it.

The first thing I did was to write two programs to generate and solve Sudoku Classic puzzles.  I also added to the Generator the code necessary to create pattern Sudokus (i.e., puzzles in which the initial clues are arranged in a pre-determined way).  Once I was done with Sudoku Classics, I wrote a program to combine five pattern Sudokus into a Samurai Sudoku puzzle.

This work on Sudoku resulted in my first puzzle book, Sudoku Programming, which I self published at the beginning of April.  365 pages of strategy explanations, walk-throughs of "C" code, and examples.

Shortly after that, I thought that a book describing in detail the strategies to solve Sudoku Classic puzzles could be useful, and wrote Sudoku Explained, a booklet of 94 pages that I published at the end of May.  I offered it to the game shop Mind Games, that has since sold some copies.  Forget what they say about eBooks.  In terms of satisfaction, nothing compares with seeing your printed books on the shelves of a physical, old fashion, shop.

I had designed the head with the "Sudoku Brain" for my first book, and had the idea of placing small heads on the two sides of my name.  But, after flipping the small head to place on the right-hand side of the cover, given my perfectionism, I flipped each digit inside the brain back to its original direction, so that they could be read.  The devil is indeed in the details...

At that point, I decided that "C", after all, was less popular than Java, and decided to rewrite all my Sudoku programs in Java. This took a few months during the middle of the year.  After that, it seemed natural to rewrite "Sudoku Programming" for Java.  This time, I chose the more catchy title How to Create Your Own Sudokus with Java.  I contacted some publishers and also some agents, but nobody was interested in publishing it.  They all claimed that it was a very difficult book to place.  As a result, once more, I decided to publish it myself.

But while I was looking for a publisher for my Java book, I started working on another puzzle: CalcuDoku (see several recent articles in this blog).
I developed a program to generate and solve CalcuDokus, but this time I decided not to write books that explain how the programs work.  Similarly to what I had done with Sudokus, I wrote a program to compose CalcuDokus into larger puzzles.

Over the past couple of months, I have published three books of puzzles: 200 Puzzling Hearts, with 200 heart-patterned easy Sudokus, 200 Puzzling Shamrocks, with 200 difficult Sudokus patterned like four-leafed clover, and 100 Double CalcuDokus.

     

I am currently publishing what is going to be my last puzzle book (at least, that's what I am thinking now): 50 Samurai CalcuDokus.  This book has a larger format because the samurai puzzles are LARGE!

Next year, I will have to work on something else.  I confess that I feel a bit saturated with puzzle programming.  Perhaps, I will resume writing my historical novel Ciao Biondina.  But also a crime novel or an alternate history might inspire me.  We shall see...

Double CalcuDoku #2

I can now generate Double CalcuDokus with any overlapping, although, at least for the time being, the overlapping region can only be a square.  Here is an example of a 6x6 overlap:

I find puzzles with large overlaps more interesting. It makes it easier to exploit the fact that the cells of each row and columns that are not share must coincide.  For example, in the above example, the three bottom cells of the middle column of the right puzzle include two singles: a 4 and a 2.  This means that also the top three cells of the same column must include a 4 and a 2.  As the 2-cell cage "9x" cannot possibly contain an even digit, it means that the they must be in the other two cells.

And here is an example of a 7x7 overlap:

The "edge effect" is particularly strong when the overlapping is 7x7, and makes the solution of the overall puzzle easier.  To keep the difficulty at a challenging level, I have therefore tweaked the configuration parameters and made the individual puzzles a bit more difficult.  Notice that in the above example there are three 5-cell cages and seven 4-cell cages.

I have just published a book with one hundred puzzles:

You can buy it in print from Lulu for US$9.99 or in several eBook formats from Smashwords for US$0.99.

Double CalcuDoku

I imagine that you are familiar with the double Sudokus like the following one:

I though: wouldn't it be nice to make overlapping CalcuDokus? Well, here is the first one I generated:

As you can see, I overlapped a 3x3 area. To explain how this works, I have coloured the puzzle, which is normally in B&W. The two squares are two normal CalcuDokus, but the green area belongs to both the yellow and the blue puzzles.

Notice that cages can cross the boundary. For example, the right-side cell of the 2-cell cage "2:" belongs to both puzzles, while its left-side cell only belongs to the yellow puzzle.

As I don't like puzzles that admit multiple solutions, I ensured that the program delivers a unique solution. The interesting thing with overlapping CalcuDokus is that they can overlap by any amount of rows and/or columns, while Sudokus, to maintain the integrity of the boxes, can only overlap by 3 or 6 rows and/or columns.

For the time being, my program only supports an overlapping of 3 rows and 3 column, but I am going to parameterise it. Then problem is not in generating and solving the puzzle, but in displaying it.

Concerning the name to give to these puzzles, I thought that Niken would be a nice possibility. This is because "Ni" means "two" in Japanese and KenKen (which is a registered trademark of Nextoy LLC) is much more widely known than CalcuDoku. In any case, "CalcuDoku", as a name, is quite long on its own. As "Ken" is a normal Japanese word (which, as you probably know, means "wisdom"), I don't believe that Nextoy could accuse me of infringing their trademark. I could also call it KenTwo or TwoKen but, somehow, it doesn't seem right. Also Kenni is not good. What do you think?

KenKen and CalcuDoku

I found three websites that let you play daily KenKen (® Nextoy LLC) /CalcuDoku puzzles: kenken.com, calcudoku.org, and my website zambon.com.au.

While the other two websites include puzzles of different sizes, and calcudoku.org also includes variants, my website only includes 9x9 puzzles. KenKen and CalcuDoku are the same puzzle, but their implementation is done by different people. Each implementation has a different feel and, on average, different levels of difficulty.

I know how my puzzles are developed, but, obviously, I have no idea what algorithms the other developers use. I thought it would be interesting to identify some of the differences from a statistical point of view.

For this purpose, I analysed 10 puzzles taken from each website. I know that 10 is too small a sample to make good statistics, but it was a lot of counting...

Anyhow, what follows is a summary of what I came up with. To avoid repeating the domain names, I will use K to identify kenken.com, Z for zambon.com.au, and C for calcudoku.org. ‘A’ indicates values obtained by averaging all. The triplets of numbers indicate minimum, average, and maximum values.

Number of cages: K=[31, 33.2, 38]; Z=[32, 34.3, 37]; C=[33, 34.2, 35]; A=[32.0, 33.9, 36.7].

The average number of cages is for everyone around 34. But it is interesting to note that K's spread is 7, Z's is 5, and C's only 2. This might indicate that, while K and Z do not set any limits to the number of cages, C determines the cages not completely as a result of random choices. This might be consistent with the fact that C sometimes presents puzzles that have the cages arranged in particular patterns (although none of the puzzles I randomly picked belonged to that group). It would be interesting to know what Patrick (C's developer) would have to say about this.

With larger samples, I expect that Z's (i.e., my) number of cages would turn out to be normally (i.e., randomly) distributed. Actually, as I generate the puzzles, I don't need to do the counting, because the computer automatically lists for the number of cages. I can check it out right now.

...

It turns out that the number of cages calculated for 100 Z's puzzles is [32, 34.83, 38].

The following image shows how the normal distribution (the magenta squares) fits to the measured values (the blue diamonds; these are the default of Excel and I didn't bother to change them). The vertical bars represent a standard deviation from the normally distributed values. In other words, if the distribution reflects reality, there is a 68.2% probability for each measurement to fall within the bars. At the very least, the plot confirms that the number of cages in my puzzles is not in disagreement with a normal distribution. I confess I would have been shocked if it had not been so, because the distribution is the result of several [pseudo]random choices...

The following table summarises the counts of operation codes and cage sizes.

C has about 6 times the number of 1-cell cages that K and Z have, and half the number of 2-cell cages.  I will go out on a limb and say I believe that such differences are not due to statistical fluctuations within the samples. C also seems to have fewer divisions (1.3 vs. 3.5 and 5.5) and more cages with more than 3 cells (6.4 vs. 3.1 and 3.9). It seems reasonable to assume that the lower number of divisions (and perhaps subtractions) is due to the lower numbers of 2-cell cages.

In general, I have the impression that C's puzzles are more difficult than those of K and Z, and it seems reasonably safe to assume that the higher number of large cages is a contributing factor.

To deduce more from such a small sample would be inappropriate.

Catholic Church? No Thanks!

I just published with Smashwords a short book titled Catholic Church? No Thanks!.

It collects a series of short pieces about the Catholic Church that I wrote over a period of time. They describe some events that occurred to me and some of my reflections on how the Church operates. I was never a fervent Catholic, but this booklet explains some of the events that contributed to my Atheism.

You can buy CalcuDoku for the iPad

My application to play CalcuDoku on the iPad is finally available in the iTunes App Store:

You can also check it out on itunes.apple.com

What are you waiting for? 

Same-sex Marriage

Yesterday I talked about boat people.  Today, I feel compelled to write a short note about another issue that is being hotly debated in Australia.

Boat People

Every year, some thousand people are desperate enough to attempt the dangerous crossing from Indonesia to Australia on rickety boats.  They pay thousands of dollars to the unscrupulous operators who own the boats, in the hope that they will be allowed to remain in Australia as refugees.

The CalcuDoku application for the iPad is ready

I have just uploaded the CalcuDoku application for the iPad to Apple’s application store.  They could still find something I didn’t do right and reject it, but I think (and hope) that everything will go smoothly.  I don’t know how long it will take before it will appear in the AppStore, though...

Unfortunately, I am also not sure that it will be available in the Australian Apple store.  The problem is that I am not registered for GST (for the non-Australians: GST stands for Goods and Services Tax and is Australia’s 10% value-added tax).  It is only compulsory to register for GST if your Australian business revenue exceeds 75 kAUD, and it is such a bureaucracy that you don’t really want to get into it unless you do have such an income and/or incur significant GST-deductible expenses.

It is not clear to me whether Apple will simply not pay me when they sell my application in Australia or (more likely) the Australian residents will be unable to buy the application locally.  In any case, they should still be able to buy it from the US store for USD 0.99 instead AUD 0.99 (actually a cent or two cheaper).  We shall see.

Now that this application is done, I will go back writing fiction.  I confess I am a bit fed up with programming.  As I said in a previous article, Apple’s development environment is great, but not bug-free.  In a couple of occasions, I had to find some workarounds to get done what I needed.

Why a bladder?

I have always had some of my most interesting ideas during the periods of drowsiness that precede and follow sleep.

The CalcuDoku application for the iPad is almost done!

Hopefully, in the next week or two, you will see the application in the Apple Store.  There will be a version with ten puzzles for free and a version with one hundred puzzles for a few dollars.  This is obviously to allow people to try out the game for free, and then, if they like what they see, buy the version with many puzzles to play.

Since the last article on this blog, I added a tool bar and a menu to select the puzzles, as shown in the following snapshot.

Progress on the CalcuDoku application for the iPad

This is to report on my progress on the development of the application I announced in my previous article. Here a snapshot that gives you an idea on some of the functionality:

A CalcuDoku application for the iPad

Perhaps you have visited my DailyCalcuDoku page. There, I provide interactivity with JavaScript, but all the work is done offline by a C application that runs on my server. Every day, a few minutes after midnight AEST (Australian Eastern Standard Time), the system launches the application, which uses the current date as a pseudorandom seed, and generates an HTML file with the daily CalcuDoku.

Actually, I have just realised that if you attempt to play immediately after my midnight, the program will fail. I have to fix it. It’s not nice when a program fails with no explanation. It might not seem a serious problem, but midnight here is 10 AM in Boston and 6 PM in Moscow...

Anyhow, after developing the Daily CalcuDoku software, I thought: wouldn’t it be nice to create an application for the iPad that does a similar thing? I started on 1 September, and the following snapshot gives you a taste of it:

How to identify some email scams

Some days ago, I received the following email (with my email address removed and the links disabled):

Subject: Your package has arrived!

From: UPS Shipments

Date: Wed, 7 Sep 2011 21:42:50 +0900 (KST)

To:

Dear client

Your package has arrived.

The tracking # is : 16B9159622A040A2 and can be used at :

http://www.ups.com/tracking/tracking.html

The shipping invoice can be downloaded from :

http://www.ups.com/tracking/invoices/download.aspx?invoice_id=16B9159622A040A2

Thank you,

United Parcel Service

*** This is an automatically generated email, please do not reply ***

Giza-IQ Test - Solution 20

This is the last posting concerning my Giza-IQ test.

Giza-IQ Test - Solution 19

Giza-IQ Test - Solution 18

Giza-IQ Test - Solution 17

Giza-IQ Test - Solution 16

Giza-IQ Test - Solution 15

Daily CalcuDoku

On July 10th, I missed the first anniversary of this blog, but I have just discovered that with the previous article I passed the 100-article mark.  Not too bad, even if the visitors are thousands instead of millions.

Anyhow, I invite you to solve my daily CalcuDoku by clicking on the following picture of a partially solved puzzle

A word of warning: these puzzles are very hard!

Then, you can tell me whether you like my implementation better than the Flash application you find in the original KenKen website kenken.com.

Checks on Senior Law-Enforcement Agents

Yesterday, I watched Four Corners (http://www.abc.net.au/4corners/stories/2011/08/15/3291474.htm), one of Australia’s leading current affairs programs (without advertising), and feel compelled to reflect on it.

Giza-IQ Test - Questions 15 to 20

Here are the last six numeric questions.  As usual, I will post the answers one by one in the near future.

2.05    ? W R O F ? V I N E ?

2.06    John has two girlfriends, Linda and Iris. Just in front of John’s place, there is a bus stop for the lines 23 and 37. Line 23 takes him to Linda, while line 37 takes him to Iris. The buses come equally often. Every day, John visits one of his girlfriends. Without looking at his watch, he takes the first bus that comes. After a few weeks though, Linda calls him crying and tells him that she doesn’t want to see him anymore. If he cared about her, she says between sobs, he would visit her more often than once a week. How can it be?

2.07    1011, 1001, 1011, 1010, ?, ?, ?, ?

2.08    Minesweeper is a computer game included in all versions of Microsoft Windows. If 10 mines are placed at random within a field of 5 x 4 positions and you start a round of the game by clicking on a position at random, what is the probability that all the positions adjacent to the one you have clicked on are occupied by mines? Provide the answer as a percentage with three digits after the decimal period.

2.09    628318530717??

2.10    In a game of Bingo with 90 numbers, what is the probability that the first five numbers drawn are in increasing order? (e.g., 2 6 25 72 83 or 50 53 77 82 89)

Giza-IQ Test - Solution 14

Giza-IQ Test - Solution 13

I cannot get over it

This story of Patrizio Galli (see the posting of the 6th) is affecting me more than I would have thought.

Giza IQ-Test - Solution 12

Giza IQ-Test - Solution 11

Patrizio Galli

Giza-IQ Test - Questions 13 and 14

2.03    In a contest, three problems, A, B, and C are posed.  25 of the participants solve at least one problem each. Of all those who don’t solve problem A, the number of those who solve B is twice the number of those who solve C.  The number of participants who only solve problem A is one more than the number of those who solve A and at least one other problem.  Of all participants who solve just one problem, half do not solve problem A.  How many participants solve only problem B?

2.04    How many four-digit integers (i.e., between 1000 and 9999) cannot be changed to multiples of 1892 by replacing up to three of their digits?

Giza-IQ Test - Questions 11 and 12

New month, new questions.  I have already posted all my geometrical questions.  This month, I have numerical and combinatorial questions for you.

2.01    In a sport contest lasting n days (with n > 1), m medals are awarded.  On the first day, one medal and 1/5 of the remaining m-1 medals are awarded; on the second day, two medals and 1/5 of the then remaining medals are awarded; and so on.  On the last day, the remaining n medals are awarded.  How many days does the contest last and how many medals are awarded altogether?

2.02    Five students, A,B,C,D, and E take part in a contest.  One prediction was that the contestants would finish in the order ABCDE.  In fact no contestant finishes in the position predicted, and no two contestants predicted to finish consecutively actually do so.  A second prediction had the contestants finishing in the order DAECB.  This prediction was better:  Exactly two of the contestants finish in the places predicted, and two disjoint pairs of students predicted to finish consecutively actually do so.  Determine the order in which the contestants finish.

Giza-IQ Test - Solution 10

Each of the two ants has 4 edges to choose. This gives a total of 4² = 16 possible choices. Of those choices, we have to discard the four cases in which the ants choose the same edge, because then they would meet between their starting vertices after walking 1/2 edge each.

We are left with 12 possible choices. This result can also be obtained by noting that if we let one of the ants choose the edge it likes, then the second ant is only left with three possible choices: 4*3 = 12.

After walking their first edge, in 4 of the 12 possible cases, the ants find themselves still on opposite vertices, while in the other 8 cases, they are at two ends of the same edge.

Now, if they are at the two ends of an edge, it is for them impossible to meet after walking exactly a further edge without one of them having to walk back to its vertex of origin. As the question states that the ants never double back, these possibilities have to be discarded.

As a result of the considerations above, the only cases that satisfy all the conditions are those in which the ants move from a pair of opposite edges to a different pair of opposite edges. The probability is 4/16 = 1/4.

In its new position, each ant can choose one of 3 possible edges (not 4, because ants never double back). Therefore, there are 3² = 9 possibilities. Of these, only 2 lead to a meeting satisfying the required conditions: those in which both ants walk to one of the two vertices that were so far unoccupied by either one of them. The probability is therefore 2/9.

The total probability is given by the product of the probabilities calculated for the two edges: P = 1/4 * 2/9 = 1/18 = 0.0555 .

Giza-IQ Test - Solution 9

 

 It is a regular Octahedron.

Giza-IQ Test - Solution 8

If you lie the octahedron on its ADE face, its top view is as follows:

The area of the smallest enclosing rectangle is given by BC, which is 1, multiplied by the projection of DF onto the horizontal plane, which is twice the distance between the centre of a face and one of its vertices = 2 * 2/3 * sqrt(3)/ 2 = 2/3 * sqrt(3)

The height of our box coincides with the distance between the faces ADE and BCF, which is twice the radius of the inscribed sphere.

Using the coordinate axes shown in the figure below, I write the equation of the sphere centred in the origin that has on its surface the centre of one of the faces. If you find a better method for calculating the radius, I’d be happy to hear from you. I just use the first method that comes to mind.

Considering that CDEF is a square of side 1, the distance of each vertex from the centre of the octahedron is sqrt(2)/2. Therefore, the coordinates of the vertices B, C, and F are:

B: (0, 0, sqrt(2)/2)

C: (0, sqrt(2)/2, 0)

F: (sqrt(2)/2, 0, 0)

To calculate the coordinates of the centre of the BCF face, I just average the coordinates of its vertices:

centre of BCF: (sqrt(2)/6, sqrt(2)/6, sqrt(2)/6)

The equation of a sphere centred in the origin is simply x² + y² + z² = r², and r turns out to be sqrt(6)/6.

We can finally calculate the volume of our box as:

V = area of base * height = [2/3 * sqrt(3)] * [sqrt(6) / 3] = 2/3 * sqrt(2)

Giza-IQ Test - Solution 7

The cubic root of 2 is 1.259921049894873 = ~1.26

The following table shows how many 2-cubes (i.e., cubes of volume 2) fit side-by-side into the length occupied by a given number of 1-cubes:

1-cubes 2-cubes

   1      0

   2      1   1.26

   3      2   2.52

   4      3   3.78

   5      3   3.78

   6      4   5.04

   7      5   6.30

   8      6   7.56

   9      7   8.82

  10      7   8.82

  11      8  10.08

For example, six 2-cubes need just a bit less space than eight 1-cubes.

To solve the problem, we only need try possible box dimensions starting from the smallest one that can contain a 2-cube. We can afford to do so, because we expect to find a solution pretty soon.

1-cubes   1-vol   2-cubes   2-vol   ratio

2x2x2       8     1x1x1       2      1/4

2x2x3      12     1x1x2       4      1/3

2x3x3      18     1x2x2       8      4/9

3x3x3      27     2x2x2      16     16/27

2x2x4      16     1x1x3       6      3/8

2x3x4      24     1x2x3      12      1/2

3x3x4      36     2x2x3      24      2/3

3x4x4      48     2x3x3      36      3/4

4x4x4      64     3x3x3      54     27/32

2x2x5      20     1x1x3       6      3/10

2x3x5      30     1x2x3      12      2/5   ***

Giza-IQ Test - Solution 6

If you open the icosahedron, you can easily see that the shortest line between the geometrical centres of two opposite faces is the straight line. This is the geodesic line, which you would obtain in absence of friction if you stretched between the two points an elastic band. If you establish the Cartesian axes as shown in the figure, the coordinates of the two points are (0, 1/3) and (5/2, 2/3).

Therefore, the solution is given by:

d = sqrt((5/2) ² + (1/3)²) = sqrt(226) / 6 = 2.505549396395485.

Giza-IQ Test - Solution 5

The volume of a tetrahedron is baseArea * height / 3. If we extend exactly two edges, they can only be adjacent. If you choose two that are not part of the base, the maximum height is obtained when the rotating edge is perpendicular to the base.

Then, the height coincides with the length of the edge.

The area of the base is sqrt(3)/4. Therefore, the maximum volume of the tetrahedron is:

Vmax = sqrt(3) / 4 * 1/3 = sqrt(3) / 12 = 0.144337567297406.

Giza-IQ Test - Solution 4

The volume of a tetrahedron is baseArea * height / 3. If we only extend one of the edges that don’t form the base, as shown in the figure, the maximum height is obtained when the rotating face is perpendicular to the base.

Then, the height coincides with that of an equilateral triangle of side 1: sqrt(3)/2.

The area of the base is sqrt(3)/4. Therefore, the maximum volume of the tetrahedron is:

   Vmax = sqrt(3)/4 * sqrt(3)/2 / 3 = 1/8 = 0.1250.

Just for fun, we can compare this volume with that of a regular tetrahedron. Its height can be calculated as follows:

   h = sqrt( 1² - (2/3)²) = sqrt(5)/3

Therefore, the volume of the regular tetrahedron of unitary edge is

   sqrt(3)/4 * sqrt(5)/3 / 3 = 1/12 * sqrt(5/3) = 0.1076...

Giza-IQ Test - Solution 3

Cut the cone along the line formed by the vertical segment of the string, and open it onto a flat surface.  You obtain a triangle with a rounded base.  The string slips off the cone when the angle at the top of the opened surface of the cone reaches 180 degrees.  That is, when the opened cone looks like a semicircle.

If we take the radius R of the semicircle to be 1, the circumference of the cone base is given by:
  C = 2*pi*R / 2 = pi

The radius of the cone base is then given by
  r = C/(2*pi) = 1/2

The aperture α of the cone is easily calsulated as follows:
  α = 2*arcsin(r/R) = 2*arcsin(1/2) = 60 degrees.

Giza-IQ Test - Questions 9 and 10

Three more geometrical puzzles.  Don’t you like polyhedra?  These are the last two geometrical questions.  Then, I will have for you numerical ones.

1.09    Four regular tetrahedrons are placed inside a regular tetrahedron that has edges of double length.  This is done in such a way that each vertex of the large tetrahedron coincides with one of the vertices of the small tetrahedrons, so that an empty space is left in the middle of the large tetrahedron.  Please describe in words the shape of the empty space.

1.10    Two ants are on the opposite vertices of a regular octahedron.  They choose at random one of the edges and walk on it at the same uniform speed.  Every time each of the ants encounters a vertex, it immediately chooses at random a new edge (that is, it never doubles back onto the edge it has just come from) and walks on it.  What is the probability that the two ants meet after each ant has walked on exactly two edges?

Giza-IQ Test - Solution 2

This is the solution to the second of the two problems I posted on July 11.

Giza-IQ Test - Solution 1

Today, instead of proposing more puzzles, I have decided to begin giving you solutions.

This is the solution to the first of the two problems I posted on July 11.

Giza-IQ Test - Questions 7 and 8

Today’s puzzles are about fitting regular polihedra into boxes.

1.07    A rectangular box can be filled completely with cubes of dimensions 1 x 1 x 1.  When the unit cubes are removed and larger cubes, each having a volume of 2, are placed in the box with their edges parallel to the edges of the box, it turns out that they can only fill 40% of the box. What is a possible set of dimensions for such a box?

1.08    What are the dimensions of the smallest rectangular box that can contain a regular octahedron with unitary edge length?

Giza-IQ Test - Questions 5 and 6

To all French visitors: Happy Bastille Day!  For those who don’t know, on July 14th of 222 years ago, the French Revolution exploded.  That’s why today is the French equivalent of U.S.A’s  July 4th.  I wonder what fraction of such momentous events occurred during summer.  The Russian national day is (was?) October 25th, and the Chinese one is October 1st, but Italy’s is June 2nd, and the Australian one January 26th (which is during the southern summer)...

Anyhow, today I am going to propose two more of my mathematical puzzles.  These two are about Platonic solids: a Tetrahedron and an Icosahedron.  Wikipedia says that many viruses, including the herpes virus, have icosahedral shells. Fascinating  (as an old friend with pointy ears would say)!

1.05    In a regular tetrahedron with unitary edge length, two (and exactly two) edges are increased in length, thereby increasing the volume of the solid.  What is the maximum volume that can be obtained in this way?

1.06    An ant walks on a regular icosahedron with unitary edge length.  It goes from the geometric centre of one face to the geometric centre of the opposite face (the geometric centre of a triangle is the centre of the circumscribed circle).  What is the minimum distance that the ant needs to cover?

Java - Formatting a Sudoku for the Web

I just wrote a small method in Java that somebody might find useful. It converts a Sudoku string into HTML.

Giza-IQ Test - Questions 3 and 4

Here are two more questions to test your intelligence with mathematical and geometrical problems.  The first problem I propose to you today was one of the problems I encountered when in 1967 I attended in Rome the selections for the Italian National Math championship.  I qualified for the national championship and there I reached the fifth place, thanks to which I became part of the Italian team sent to the IX International Mathematics Olympiad.

Giza-IQ Test - Questions 1 and 2

As you might know, in 2010 I joined several High-IQ societies. half a year later, I started working on an Intelligence Test. After developing twenty-three questions, as it often happens to me, I lost interest and left it unfinished. As I don’t think I will ever complete it, I will publish the questions in this blog. To see the correct answers, you will have to send me an email or comment online.

Testing for Rare Medical Conditions

I am not a Medical Doctor, but I know enough about statistics to talk about the validity of [some of] the tests currently used to screen for prostate cancer.

Equinoxes in Canberra

I noticed a discrepancy in Canberra equinoxes that I cannot explain.  Perhaps one of you will be able to shed some light on this puzzle.

Arrays of Functions in Java

A couple of months ago, shortly after publishing the book Sudoku Programming (also see the post in this blog), I asked myself whether I should have written the programs in Java instead of classic C.

I had chosen C because I thought it would be easier for non-programmers to deal with a procedural language rather than with Object Oriented programming, with its class inheritance and operator overloading. But, looking at the number of functions I needed for the C implementation, I began thinking that in Jva the implementation would probably have been simpler. I simply had to re-develop Solver and Generator in Java. I simply had to do it.

One of the first problems I encountered was how to implement in Java an array of function pointers.

Sudoku Explained

I have just released the book “Sudoku Explained”.

Casualties

Another Australian soldier has died in Afghanistan.  It saddens me to think that a hail of nails and ball bearings on a dusty road killed a young, strong, and courageous man.  Like most people, I know what it means to lose somebody you care about, and my thoughts go to Sergeant Wood’s wife.

Refugees

The members of Mensa Australia exchange ideas via a mailing list.

On May 1^st, one of the members posted the following message, under the heading “cost-benefit of refugees”:

To an Economist, cost and benefit is everything.

Sudoku Programming

I have finally completed my book “Sudoku Programming”.

The purpose of this book is to teach you how to write computer programs to solve and generate Sudoku puzzles. If you love Sudoku and have some knowledge of computer programming, you will have no problem in understanding the code of my Sudoku Solver and Sudoku Generator.

Code Red

I haven’t been posting anything for a while.  I thought, perhaps I can entertain you with a micro-story I wrote last year.  It is a slightly modified version of a story that was shortlisted in the “Positive Words” mini-competition of February 2010, open to stories not longer than 100 words.  I tell you, it wasn't easy to write a story with a character and a plot in 100 words...

I clench my teeth.  The cockpit is a cacophony of beeping sounds.  The instrument panel a kaleidoscope of flashing red lights.

“Captain...”

I nod, without taking my eyes off the angry sea of grey before me.  With all the checklists exhausted, there is nothing more to say.

Few seconds later, the plane hammers onto the tarmac, its frame jarred by the impact.  The engines scream in reverse.

A lineup of fire trucks emerges from the fog on the right side of the runway.  This time they will not be needed.

In the back, the passengers erupt into applause.

KenKen - One more case

Here is one more interesting strategy I discovered when solving one of my CleverClever puzzles.

The four-cell cage on the right shows all possible candidates of each cell. We can discard the 1 of (5,8) because the sum must be even and the three other cells only have even candidates. Then, as the 1 of row 5 can only be in (5,1), we can remove all other candidates from that cell and the corresponding candidates in the other cell of the cage.

KenKen - A non-trivial case

Solving one of my CleverClever puzzles, I encountered the following configuration:

Suppose that the 112x cage is solved by the combination [8 7 2 1]. Then, the 8 must be in (7,5), because there is already an 8 in either (3,6) or (4,6). But if that is the case, then the remaining three cells of the cage, all in column 6, must contain 7, 2, and 1. This leads to a contradiction, because it would force us to remove the 1s in (2,6) and (8,6), thereby leaving both cells with a 9 as the only possible candidate. Therefore, the 112x cage must be solved with [7 4 2 2] (which, incidentally, means that (7,5) must contain a 2).

I don’t have a name for this strategy, but it is a nice example of a technique that does not (and cannot) occur in Sudoku.

KenKen Strategies

Most of the strategies used to solve Sudoku rely on the interplay of boxes and lines. Therefore, it is not surprising that they are not transferable to KenKen^® (registered trademark of Nextoy LLC).

KenKen

Some weeks ago, I discovered the Sudoku-like puzzle KenKen^® (registered trademark of Nextoy LLC). In Japanese, Ken means ‘clever’. I say ‘Sudoku-like’ because it consists of a grid to be filled with digits. Like with Sudoku, every digit can only appear once within its row and once within its column. But, instead of square boxes, KenKen^® contains cages, which can hold between one and seven (the largest cage I have encountered) contiguous cells. There are no initial clues, but for every cage, the puzzle provides a number and an operation with which the number is to be achieved.

Watch Your Language!

Intelligent Design is an affirmation of a belief, not a scientific theory.  To maintain that Nature is too complex to have evolved on its own and then deduce from such an arbitrary concept that a Creator/Designer must exist is an affirmation of faith, not a scientific statement.

It is important that magazines focussed on popularising Science maintain the highest standards of objectivity, not just in what they say but also in how they say it.  Statements that purport to be scientific but are formulated with elements of superstition can have deleterious effects on the minds of the younger readers.

What prompted this tirade is the article by Lauren Monaghan titled “Grand Delusions” that appeared in Cosmos (self proclaimed “Australia’s #1 Science Magazine”)  Issue 28 of Aug/Sep 2009. On page 46, it contained the following sentence:

“...we always have — and always will — want to believe in the fantastic. In fact, many scientists believe we are even programmed to do so.”  (my italics)

In the same article was also the following statement made by an experimental psychologist:

“Humans are born with brains designed to make sense of the world, and that sometimes leads to beliefs that go beyond natural explanations.”  (again, my italics)

Do you see what I mean?  The words “programmed” and “designed” imply the existence of a Programmer and a Designer.  They should have never appeared in a Science magazine.

Bah...

GLUT in C with Eclipse on the Mac

For the past couple of months, for my book on Sudoku, I have been writing C programs with Eclipse running under Mac OS.

Multiculturalism

In 1970, the German film director and producer Rosa von Praunheim made the film Die Bettwurst. The word Bettwurst, invented by Rosa, means bed sausage, and refers to somebody who never gets out of bed.

Anyhow, I saw the film decades ago, but I still remember the words of the following little song:

Die ganze Welt ist nur ein Arsch

und wir sind seine Fürze.

Ein Jeder stinkt nach seiner Art.

Das gibt dem Leben Würze.

Here is my best translation of it:

The whole world is just an arse

and we are its farts.

Each one stinks in its own way.

This gives spices to our lives.

Sudoku - A Handsome Samurai

I have almost completed my book Sudoku Programming (if I have ever seen a plug...) about how to write C applications that can solve and generate Sudokus. As part of it, I have decided to explain how to generate Samurai Sudokus. I had noticed that they often have the shared boxes completely empty and wanted to do better than that. I am very happy with the result, and would like to share it with you. Here it is:

I can generate as many as I like and not necessarily fully symmetrical, even if I think that they are just beautiful. Each one of the five puzzles I used to ‘assemble’ the Samurai requires some non-trivial strategies like Y-wing, XY-chain, and X-wing. The presence of the intersections might/should reduce the overall difficulty of the puzzle, but I still expect it to be reasonably (whatever that means) difficult.

Obviously, I have got the solution, but you don’t expect me to give it to you, do you?

Fortran and Eclipse on the Mac - Addendum

This is about updating Eclipse, PTP, and the Fortran compiler to their latest versions. Beth Tibbitts of the Eclipse Parallel Tools Platform (http://eclipse.org/ptp) told me how to do it via the Photran Information mailing list (photran[a t]eclipse.org).

Fortran and Eclipse on the Mac

In this post, I describe how I installed a Fortran compiler within Eclipse on my 64-bit Macintosh running the Snow Leopard system (OS X 10.6.5).

A New Year's Tale

As soon as the starship enters the solar system, the board AI begins the process of thawing the crew. Despite the powerful zero-point energy propulsion, the trip from Tau Ceti 4 has lasted almost three decades.