IBM Research | Ponder This | June 2006 solutions
Skip to main content

June 2006

<<May June July>>


Consider a 2*n rectangle tiled with n dominoes.  Horizontally oriented dominoes come in pairs one on top of the other (else it will not be possible to successfully complete a tiling of the rectangle). So we may assume there are 2*a horizontally oriented dominoes and n-2*a vertically oriented dominoes.  The tiling is determined by the bottom row which will consist of a horizontally oriented dominoes and the bottom part of (n-2*a) vertically oriented dominoes.  Clearly there are C(n-a,a) (where C(n-a,a) denotes the binomial coefficient n-a chose a) ways of arranging the bottom row.  C(n-a,a) is a monotonic function of a rising to a maximum as a increases then falling off. Assume n is large and let a=r*n.  Then by equating C(n-a,a) and C(n-(a+1),(a+1)) it is easy to see that at the peak r will satisfy the equation r*(1-r)=(1-2*r)**2 or 5*r*r-5*r+1.  This has solution r=(5-sqrt(5))/10 (since clearly r<.5).  For large n the peak will be narrow so that almost all of the configurations will correspond to this value of r.  So the typical fraction of horizontally oriented dominoes is the same as the fraction at the peak or 2*a/n = 2*r = 1-sqrt(5)/5 = .5528 (and the fraction of vertically oriented dominoes is sqrt(5)/5 = .4472).

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: