After returning this morning from a sleep-over/locking event with Max and his scouting troop at a local museum, I am rather tired. Not because it was loud, late, and full of energy — that is to be expected. I am tired this morning because I was up all night thinking about, of all things… sleeping arrangements.
You see, the 32 scouts in attendance slept on a standard 8×8 chessboard. Each scout could take up 2 horizontally or vertically adjacent spots, and all of the spots were taken. To make sure that the chaperoning parents could quickly get to any child if needed, at least every other row’s horizontal edge must be unobstructed. Finally, the row closest to the dinosaur skeleton exhibit had to be made up out of the four oldest scouts, all laying horizontally. (I guess that there was a movie where people spent the night at a museum that involved a T-Rex skeleton?)
It doesn’t matter who sleeps where necessarily, just the pattern of horizontal and vertical scouts. Each solution can have at most two contiguous rows, so that any scout can be accessed. Here is an example where that is observed, and where it isn’t observed:
No more than two rows are blocked with scouts
More than two rows are blocked with scouts
This week’s puzzle, and the conundrum that kept me up most of last night: how many unique patterns of horizontal and vertical scouts could be laid out respecting the “access” rule, and having the “border row” of horizontal scouts at one end?
This puzzle is all about combinatorics: How many different 1 or 2 row sets of scouts are possible, and how can these 1 or 2 row sets fill the eight rows of the chess board?
With the row closest to the dinosaur exhibit “fixed” (4 horizontal scouts), we only need to think about the other seven. Each of these seven can match the fixed top row (just one way to do that) or be two rows tall (allowing for direct chaperone access.)
If a pair of rows holds scouts, you need to have the vertical pairs in pairs; having an odd number of vertical pairs won’t completely fill a row, as the non-vertical scouts are horizontal, and are by definition 2 squares wide. You can have either 2 vertical scouts, 4 vertical scouts, 6 vertical scouts or a completely vertical two row set of 8 vertical scouts.
Addressing each in turn: 2 vertical scouts / 3 horizontal pairs of scouts:
Here we have 5 “units,” two of which are vertical. 5C2 = 10, there are 10 different options for this arrangement. 4 vertical scouts / 2 horizontal pairs of scouts:
With 6 units in play, 6C2 = 15, there are 15 different options for this arrangement. 6 vertical scouts / 1 horizontal pair of scouts:
Seven units, 1 of which is horizonal, 7C1 = 7 different options. 8 vertical scouts / no horizontal scouts:
Just one distinct way to make this arrangement.
The count of distinct positionings of scouts to make two contiguous rows is 10 + 15 + 7 + 1 = 33.
Now let’s turn to the other orientation. Having the top row fixed, the other seven rows are combinations of one-row and two-row sets. As they need to add up to seven, we have the following options for sets of rows: 1 one-row set and 3 two-row sets:
Once again, simple combinatorics… 4 units, 3 of which are two-rows. 4C3 = 4. There is just one way to represent the one-row set, and 33 for each two-row set, so this option yields 4 x 11 x 333 = 4 x 1 x 33,597 = 143,748. 3 one-row sets and 2 two-row sets:
There are 5 units, 2 of which are two-row sets, and 5C2 = 10. As there are 2 two-row sets that have 33 different permutations, this option yields 10 x 13 x 332 = 10 x 1 x 1,089 = 10,890. 5 one-row sets and 1 two-row sets:
Here, there are 6 units, 1 of which is a two-row set, and 6C1 = 6. As there is just 1 two-row set, this option yields 6 x 15 x 331 = 6 x 1 x 33 = 198.
7 one-row sets and no two-row sets:
This one is simple: 7C0 = 1, and 1 x 17 x 330 = 1 x 1 x 1 = 1. This makes sense, as there is just one way to have 7 one-row sets: all 28 scouts are horizontal.
Summing up, there are a total of 143,748 + 1,089 + 198 + 1 = 154,837 different sets of sleeping arrangements that meet the criteria above.
Congratulations to Blaine for submitting a correct solution and being selected at random from among the correct (or at least reasonably well-reasoned) solutions submitted. A $50 Gift Certificate from ThinkGeek will be on its way shortly!
Thanks to everyone that entered, and to ThinkGeek for sponsoring our puzzles in 2015.
Happy puzzling!
Liked it? Take a second to support GeekDad and GeekMom on Patreon!
You see, the 32 scouts in attendance slept on a standard 8×8 chessboard. Each scout could take up 2 horizontally or vertically adjacent spots, and all of the spots were taken. To make sure that the chaperoning parents could quickly get to any child if needed, at least every other row’s horizontal edge must be unobstructed. Finally, the row closest to the dinosaur skeleton exhibit had to be made up out of the four oldest scouts, all laying horizontally. (I guess that there was a movie where people spent the night at a museum that involved a T-Rex skeleton?)
