login
Number of ways to quarter a 2n X 2n chessboard.
(Formerly M3987)
4

%I M3987 #83 Sep 28 2023 04:15:58

%S 1,1,5,37,782,44240

%N Number of ways to quarter a 2n X 2n chessboard.

%C Warning: it now seems very likely that this is an incorrect version of A257952. - _N. J. A. Sloane_, Apr 17 2016

%C Number of ways to dissect a 2n X 2n chessboard into 4 congruent pieces.

%C One can ask the same question for a 2n+1 X 2n+1 board if one omits the center square: this gives A006067.

%C a(0)=1, since there is one way to do nothing.

%C Comment from _Andrew Howroyd_, Apr 18 2016: (Start)

%C This sequence is wrong because of a bug in Mr. Parkin's code, and amazingly I can pinpoint exactly what the bug is! (I can reproduce his results.)

%C Firstly the description of the problem and its solution in Mr. Parkin's letter is very clear -- he doesn't leave a lot of room for misinterpretation (this is hugely to his credit). He also includes a very clear description of his algorithm, so I decided I would just code it up. I obtained _Giovanni Resta_'s results as given in A257952 -- there is nothing wrong with Mr Parkin's algorithm.

%C A detailed breakdown of Parkin's results is also provided in the letter. All the results match with the exception of the final line. (This would be highly improbable if there was a completely different interpretation.) In any case, one sentence stood out as a possible red flag: "Further, there are potential mirror image paths in both cases when starting on the centre lines and these are prevented by requiring a turn in one direction on the path prior to allowing a turn in the other direction" (bottom of page 6). The discrepancy in results does indeed relate to the center line and if I modify my code to lose the flag on recursion, then I get Mr. Parkin's results (so turn in one direction is only prohibited for one step). (End)

%D M. Gardner, The Unexpected Hanging and Other Mathematical Diversions. Simon and Schuster, NY, 1969, p. 189.

%D Popular Computing (Calabasas, CA), Vol. 1 (No. 7, 1973), Problem 15, front cover and page 2.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. R. Parkin, <a href="/A003213/a003213_5.png">Letter to N. J. A. Sloane, Feb 01, 1974</a>. This letter contained as an attachment the following 11-page letter to Fred Gruenberger.

%H T. R. Parkin, <a href="/A003213/a003213_6.png">Letter to Fred Gruenberger, Jan 29, 1974</a>, Page 1.

%H T. R. Parkin, <a href="/A003213/a003213_7.png">Letter to Fred Gruenberger, Jan 29, 1974</a>, Page 2.

%H T. R. Parkin, <a href="/A003213/a003213_8.png">Letter to Fred Gruenberger, Jan 29, 1974</a>, Page 3.

%H T. R. Parkin, <a href="/A003213/a003213_9.png">Letter to Fred Gruenberger, Jan 29, 1974</a>, Page 4.

%H T. R. Parkin, <a href="/A003213/a003213_10.png">Letter to Fred Gruenberger, Jan 29, 1974</a>, Page 5.

%H T. R. Parkin, <a href="/A003213/a003213_11.png">Letter to Fred Gruenberger, Jan 29, 1974</a>, Page 6.

%H T. R. Parkin, <a href="/A003213/a003213_12.png">Letter to Fred Gruenberger, Jan 29, 1974</a>, Page 7.

%H T. R. Parkin, <a href="/A003213/a003213_13.png">Letter to Fred Gruenberger, Jan 29, 1974</a>, Page 8.

%H T. R. Parkin, <a href="/A003213/a003213_14.png">Letter to Fred Gruenberger, Jan 29, 1974</a>, Page 9.

%H T. R. Parkin, <a href="/A003213/a003213_15.png">Letter to Fred Gruenberger, Jan 29, 1974</a>, Page 10.

%H T. R. Parkin, <a href="/A003213/a003213_16.png">Letter to Fred Gruenberger, Jan 29, 1974</a>, Page 11.

%H T. R. Parkin, <a href="/A003213/a003213.png">Discussion of Problem 15</a>, Popular Computing (Calabasas, CA), Vol. 2, Number 15 (June 1974), page PC15-4.

%H T. R. Parkin, <a href="/A003213/a003213_1.png">Discussion of Problem 15</a>, Popular Computing (Calabasas, CA), Vol. 2, Number 15 (June 1974), page PC15-5.

%H T. R. Parkin, <a href="/A003213/a003213_2.png">Discussion of Problem 15</a>, Popular Computing (Calabasas, CA), Vol. 2, Number 15 (June 1974), page PC15-6.

%H T. R. Parkin, <a href="/A003213/a003213_3.png">Discussion of Problem 15</a>, Popular Computing (Calabasas, CA), Vol. 2, Number 15 (June 1974), page PC15-7.

%H T. R. Parkin, <a href="/A003213/a003213_4.png">Discussion of Problem 15</a>, Popular Computing (Calabasas, CA), Vol. 2, Number 15 (June 1974), page PC15-8.

%H Popular Computing (Calabasas, CA), <a href="/A003213/a003213.jpg">Illustration showing that a(3) = 37</a>, Vol. 1 (No. 7, 1973), front cover. (One of the 37 is simply the square divided into four quadrants.)

%Y Bisection of A006067. Cf. A064941.

%Y See A257952 for another version.

%K nonn,more

%O 0,3

%A _N. J. A. Sloane_