Ponder This Challenge - June 2006 - Fraction of vertical dominoes

Ponder This Challenge:

Puzzle for June 2006.

Suppose we use dominoes to tile an infinite strip of height 2. In a typical tiling what fraction of the dominoes will be oriented vertically?  Typical can be defined rigorously by considering all possible tilings of a 2*n rectangle and then letting n go to infinity.

The first 100 people who answer all parts correctly will be listed. The answer will be posted a week after the 100th is received, or at the end of the month.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

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

Solution

• Click here to view the solution

  Answer:

  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: ponder@il.ibm.com

Solvers

• Kevin Costello (06.01.2006 @11:40:03 AM EDT)
• Balakrishnan V (06.01.2006 @12:04:59 PM EDT)
• Dan Dima (06.01.2006 @12:49:47 PM EDT)
• Frank Yang (06.01.2006 @04:06:23 PM EDT)
• Dinesh Krithivasan (06.01.2006 @04:58:04 PM EDT)
• Jan Rubak (06.01.2006 @05:01:44 PM EDT)
• Hagen von Eitzen (06.01.2006 @06:18:01 PM EDT)
• David Vaccaro (06.01.2006 @08:20:58 PM EDT)
• Steven Noble (06.01.2006 @08:21:41 PM EDT)
• Luke Pebody (06.01.2006 @09:42:18 PM EDT)
• lalafa1003 (06.01.2006 @09:48:13 PM EDT)
• Graeme McRae (06.02.2006 @03:04:14 AM EDT)
• Roberto Tauraso (06.02.2006 @07:35:08 AM EDT)
• Kennan Shelton (06.02.2006 @09:25:17 AM EDT)
• Harold Gutch (06.02.2006 @10:53:48 AM EDT)
• Michael Brand (06.02.2006 @11:18:47 AM EDT)
• Miroslava Sotakova (06.02.2006 @11:28:31 AM EDT)
• Joël Bleuse (06.02.2006 @01:04:32 PM EDT)
• Andrew McRae (06.02.2006 @03:20:14 PM EDT)
• Eugene Vasilchenko (06.02.2006 @04:33:29 PM EDT)
• Douglas Zare (06.02.2006 @05:43:16 PM EDT)
• Alap Karapurkar (06.02.2006 @07:14:58 PM EDT)
• Dion K Harmon (06.02.2006 @07:58:36 PM EDT)
• James Dow Allen (06.03.2006 @01:35:46 AM EDT)
• Manuel Gräf (06.03.2006 @12:13:43 PM EDT)
• Chris Hills (06.03.2006 @01:32:01 PM EDT)
• Vitaly Stakhovsky (06.03.2006 @02:22:14 PM EDT)
• John Dalbec (06.03.2006 @03:59:18 PM EDT)
• Gareth McCaughan (06.03.2006 @07:06:48 PM EDT)
• John Hubenschmidt (06.04.2006 @12:43:31 AM EDT)
• Andrey Goder (06.04.2006 @02:36:19 AM EDT)
• Alexey Vorobyov (06.04.2006 @03:43:51 AM EDT)
• Dan Pryor (06.04.2006 @08:45:01 AM EDT)
• Joseph DeVincentis (06.04.2006 @12:11:49 PM EDT)
• Ping-Che Chen (06.04.2006 @02:21:08 PM EDT)
• Ed Sheppard (06.04.2006 @09:07:01 PM EDT)
• Guangzhong Sun (06.04.2006 @11:36:41 PM EDT)
• Alan Murray (06.05.2006 @01:16:05 AM EDT)
• Roger Thompson (06.05.2006 @03:59:13 AM EDT)
• Tristrom Cooke (06.05.2006 @05:29:23 AM EDT)
• John Tromp (06.05.2006 @08:07:28 AM EDT)
• Matthew Paterson (06.05.2006 @08:35:22 AM EDT)
• Chris Lomont (06.05.2006 @01:57:15 PM EDT)
• Se Kwon Kim (06.06.2006 @03:23:39 AM EDT)
• Ben North (06.06.2006 @05:17:21 AM EDT)
• Ashish Mishra (06.06.2006 @05:46:26 AM EDT)
• David McQuillan (06.06.2006 @07:33:06 AM EDT)
• Frank Schmidt (06.06.2006 @09:20:09 AM EDT)
• Phil Muhm (06.06.2006 @01:29:00 PM EDT)
• Kerry M Soileau (06.06.2006 @05:15:04 PM EDT)
• William C Hasenplaugh (06.06.2006 @05:58:42 PM EDT)
• Kirk Bresniker (06.06.2006 @07:34:38 PM EDT)
• Wolf Mosle (06.06.2006 @08:10:26 PM EDT)
• Biantaishabi (06.06.2006 @09:46:40 PM EDT)
• Austin Shapiro (06.06.2006 @11:17:42 PM EDT)
• Bart De Vylder (06.07.2006 @08:55:35 AM EDT)
• Thijs Veugen (06.07.2006 @09:36:02 AM EDT)
• Chuck Carroll (06.07.2006 @09:39:04 AM EDT)
• Andrew Buchanan (06.07.2006 @09:56:00 AM EDT)
• Christian Blatter (06.07.2006 @10:51:24 AM EDT)
• Alex Izvalov (06.08.2006 @02:38:01 PM EDT)
• David Friedman (06.08.2006 @02:43:15 PM EDT)
• Ramkumar Balaraman (06.08.2006 @08:07:58 PM EDT)
• Eric R. Farmer (06.09.2006 @09:46:26 AM EDT)
• Emilio Schiavi (06.09.2006 @01:52:32 PM EDT)
• Du Yang (06.09.2006 @02:30:08 PM EDT)
• Brendan Owen (06.10.2006 @02:18:19 AM EDT)
• Chuck Nelson (06.10.2006 @12:20:58 PM EDT)
• Edna Mantsour (06.11.2006 @09:27:50 AM EDT)
• Jan Van Delden (06.11.2006 @02:15:11 PM EDT)
• Narayanan Rajamani (06.11.2006 @06:18:06 PM EDT)
• Mohammed Ajmal (06.11.2006 @07:24:15 PM EDT)
• Pushkar S. Joglekar (06.12.2006 @06:28:37 AM EDT)
• Zhou Guang (06.12.2006 @09:05:42 PM EDT)
• Firat Solgun (06.13.2006 @04:45:11 PM EDT)
• Richard A Bauer (06.14.2006 @12:56:34 AM EDT)
• Jack Kennedy (06.14.2006 @01:30:56 PM EDT)
• Robin Ryder (06.15.2006 @10:23:31 AM EDT)
• John G. Fletcher (06.15.2006 @04:27:32 PM EDT)
• Clive Tong (06.16.2006 @07:04:11 AM EDT)
• John Roy (06.16.2006 @11:37:59 AM EDT)
• Federico Felizzi (06.19.2006 @02:40:39 AM EDT)
• Ariel Flat (06.19.2006 @02:47:39 AM EDT)
• Vince Lynch (06.19.2006 @07:07:43 PM EDT)
• Jiri Hrdina (06.21.2006 @08:02:34 AM EDT)
• Van Steirteghem Anneke (06.21.2006 @09:42:26 AM EDT)
• Greg Bubnis (06.21.2006 @09:57:19 AM EDT)
• Ervan Darnell (06.21.2006 @06:58:06 PM EDT)
• Leo Broukhis (06.21.2006 @10:34:44 PM EDT)
• Yoav Raz (06.22.2006 @10:18:50 PM EDT)
• Greg Janée (06.23.2006 @03:26:16 AM EDT)
• Jonathan Mizrahi (06.27.2006 @08:25:21 AM EDT)
• Christopher Reed (06.29.2006 @08:04:02 AM EDT)