From a 99x99 checkerboard, the middle square of one side is removed.

In article <1994Mar4.000442.1@carleton.edu>, costellj@carleton.edu
writes:
> Puzzle straight from the St Olaf Math Mess -- heh.
>
> Answer:  NO.
>
> Suppose you have a chessboard of dimensions (4k+3) x (4k+3), one
> white square removed.  Suppose it is colored after the pattern of a
> normal chessboard, with black corner squares.
> (x = black, o = white)
>
> xoxoxo ... xox ... oxoxox
> ox ...                   ... xo
> :                       :
> xoxoxo ... xox ... oxoxox
>
> Then you have         (4k+2)(4k+3)/2 + (4k+2)/2 + 1 black squares and
>                 (4k+2)(4k+3)/2 + (4k+2)/2 - 1 white squares.

No, this is mistaken.

[munch]
> Observe that 99 = 4(24) + 3.  Observe also that any middle square is
> white, since it's the 50th square in its row.  As a special case of
> the above result, it too cannot be tiled.

The middle square is black, not white.  The diagonal is black.  The
number of White squares is 4900, so is the number of black squares.
ALL boards of the form (2n+1)x(2n+1) with the middle square removed
have equal numbers of white and black squares, and that number is
divisible by 4.

Coloring the board is a good idea.  I wonder if a four color pattern
could be developed . . . I'll have to think about it.

-- Scott Nelson <snelson@asd.sgi.com>

[ Editor: Nelson's objection applies to the centre square of the board
(row 50, column 50), which is black.  The square removed in this
puzzle is the middle square of a side (row 1, column 50), which is
white, and for it the quoted counts are right: with k = 24 they give
4851 + 49 + 1 = 4901 black and 4851 + 49 - 1 = 4899 white squares,
which add up to 99^2 - 1 = 9800.  The rest of costellj's argument was
cut by Nelson ("[munch]") and is not in the collected postings. ]

[ Editor: further material on this puzzle, edited separately from other collected postings (batch 13); it may repeat some of the above. ]

[ Editor: problem as stated there: ]
From a 99x99 checkerboard, the middle square of one side is removed.
Is it possible to completely tile the remaining board using 2450
T-shaped tetrominoes?  A T-tetromino consists of four squares and looks
like

      XXX
       X


Puzzle straight from the St Olaf Math Mess -- heh.

Answer:  NO.

Suppose you have a chessboard of dimensions (4k+3) x (4k+3), one white
square removed.  Suppose it is colored after the pattern of a normal
chessboard, with black corner squares.  (x = black, o = white)

xoxoxo ... xox ... oxoxox
ox ...             ... xo
:                       :
xoxoxo ... xox ... oxoxox

Then you have   (4k+2)(4k+3)/2 + (4k+2)/2 + 1 black squares and
                (4k+2)(4k+3)/2 + (4k+2)/2 - 1 white squares.

Call a t-tetramino "Evil" if it covers 3 black squares and "Good" if it
covers 3 white squares.  Let E be the number of Evil t-tiles and G be
the number of Good tiles.

The following equations must be satisfied:

3E +  G = (4k+2)(4k+3)/2 + (4k+2)/2 + 1  (a)
 E + 3G = (4k+2)(4k+3)/2 + (4k+2)/2 - 1  (b)

Multiplying (a) by 3 and subtracting (b) we get:

8E      = (4k+2)(4k+3)   + (4k+2)   + 4
4E      = (2k+1)(4k+3)   + (2k+1)   + 2
4E      = 8k^2 + 12k + 6
2E      = 4k^2 +  6k + 3
^-- even         ^-- odd.

this implies we have a fractional number of Evil tiles, a
contradiction.  So a board of dimension (4k+3)x(4k+3) missing a white
square can't be tiled with t-tetraminoes.

Observe that 99 = 4(24) + 3.  Observe also that any middle square is
white, since it's the 50th square in its row.  As a special case of the
above result, it too cannot be tiled.

(4k+1)x(4k+1) boards are still an open question...

-- John S Costello <costellj@carleton.edu>

[ Editor: John Costello's reply to Scott Nelson's objection that the
middle square is black. ]

In article <2l7u42$l9r@fido.asd.sgi.com>, snelson@victor.asd.sgi.com
(Scott Nelson) writes:
>> Then you have         (4k+2)(4k+3)/2 + (4k+2)/2 + 1 black squares and
>>                 (4k+2)(4k+3)/2 + (4k+2)/2 - 1 white squares.
>
> No, this is mistaken.

Actually in the proof above I'd assumed that we'd removed one
white square from an unspecified place on the board.  So the
equations above are OK.

>> Observe that 99 = 4(24) + 3.  Observe also that any middle square is
>> white, since it's the 50th square in its row.  As a special case of
>> the above result, it too cannot be tiled.
>
> The middle square is black, not white.  The diagonal is black.  The number
> of White squares is 4900, so is the number of black squares.

Let's number the squares across a side.  We'll start in the corner
with "1" and end in the corner with "99".

01 02 03 ... 48 49   50   51 52 ... 97 98 99
49 squares here.     ^^             49 squares here.
                     ||
          one square in the middle

Color all the odd squares black and all the even squares white.
This is the standard chessboard coloring.  Notice that square
number 50 is even.  It's also in the middle.

For chessboards 4k+3 by 4k+3, there will be (4k+2)/2 = 2k+1
squares on the left and right of the middle square, so the
middle square will always be the 2k+2th square, i.e., it will
be white.  For chessboards 4k+1 by 4k+1 the middle square will
always be the 2k+1th square, i.e., it will be black.

> ALL boards of the form (2n+1)x(2n+1) with the middle square removed
> have equal numbers of white and black squares, and that number is
> divisible by 4.

Until I realized the distinction between 4k+3 and 4k+1 chess-
boards, I thought I'd proven it for all odd chessboards.  The
problem is actually a generalization of a generalization -- I
had to prove the 7 x 7 board untilable for a competition I was
in, so *I* thought that all the middle squares were going to be
white.  Then I looked at the 5 x 5 board and the 7 x 7 board and
realized my mistake.

  v--------------v
xoxox  versus xoxoxox

 (oops)

By the way:  "2k+1th" might be another one of those dubious rhymes
for "month"...

-- John S Costello <costellj@carleton.edu>

[ Editor: the two men mean different squares: Nelson the centre of the
board (row 50, column 50, on the black diagonal), Costello the middle
square of one side (row 1, column 50, white), which is the square the
puzzle removes. ]