(First things first - I don't know a solution to this, but the puzzle occurred to me a few hours ago, and I thought people might be interested in it)
Imagine a rectangular (or square) grid of any size, every square white. If the grid is "x" squares across and "y" squares high, what is the minimum number of squares ("n") that must be shaded so that no white square is adjacent to more than 2 other white squares?
(For this puzzle, diagonally adjacent squares are not considered to be adjacent)
So, for example, if the grid is simply a 3x3 then the only square that needs shading is the centre one, then all others squares only touch two others - i.e. for x=3 y=3, n=1
a) Is there an formula to calculate "n" that will work for all paired-values of "x" and "y"?
b) If not, what is "n" for a chessboard-sized x=8 y=8 (post your suggested minimum using a standard chess-like "A7" type of description for a list of all your shaded squares)?
I suggest minimum density.
Confirm Lucky - Less than 21
Formula for Sqaures
A grid with black and white shadings has an adjacency property such that black cells are
placed so that white cells may not have more than two adjacent neighbours, being either
horizontally or vertically respectively.
Question: For any given square/rectangle, what formula gives the minimum number of black
squares?
Within an infinite grid of black and white columns, the minimum color ratio is 1:1. By adding
white columns and advancing successive rows one column so as to preserve the adjacency
property, only one scenario exists. With every third column black and every successive row
advanced by one column, the color density is 1:2. Adjacency is preserved and a white
'stairway' pattern is produced.
Now every finite square/rectangle will be a 'template' within this environment but the
expected color ratio can only expect to be an approximation of 1:2.
Towards a formula:
Here are the product of my thoughts.
From observing squares, and using the pattern of the infinite grid (as described) and one main
diagonal is black, except for the corners, I have derived this interesting set of values.
Considered in symmetry, this arrangement further guarantees the minimum.
My Table:
Side 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Black 1 . . 10 . . 25 . . 46 . . 73 .
Sq's . 4 . . 15 . . 32 . . 55 . . 84
. . 7 . . 20 . . 39 . . 64 . . Gap 3 3 3 5 5 5 7 7 7 9 9 9 11 11
1. For "Side", the Black values for the Multiples of 3, I have defined as "Base No."
These are the first row of Black values (1, 10, 25, ….)
2. The interval between Base Nos. formed a triple series of consecutive Odd numbers (Gap)
3. These intervals are a function of the Side value and is defined as: i = 1 + int(Side/3)*2.
4. Sum of Consecutive Numbers = Nos in Series/2 * [first no. + last no.]
5. A Base No is the sum of Gap intervals, less 2 and is given by the formula:
Base No = 3 * Sum of Consecutive Odd Nos –2.
The first Odd no. is 1 and the last one is i, or 1 + int(Side/3)*2.
Note however that the previous interval in the series of a Base No is 2 below the value
corresponding to that value in the 'Gap' row.
ie; Base No = 3 * int(Side/3)/2 * (1 + [1+ int(Side/3)*2 –2]) - 2
= 3* int(Side/3)/2 * (int(Side/3)*2) –2
= 3 * [int(Side/3)]^2 - 2
Other values are obtained from the product of the Mod(3) value of Side and the next
interval ; ie, Interval = mod(Side,3)*(1 + int(Side/3)*2).
The Whole number of Black for any square of Side = n is:
Black= 3*(int(n/3))^2 -2 + mod(n,3) * (1+ int(n/3)*2)
This may be tested in MSExcel by copying and pasting the above formula (except for
the word 'Black'.
For example, change the n to A1 and paste the formula into B3. Record a side value in A1 and get the Black value in B3.
Other Observations and thoughts which may help to a general solution:
1 Within the infinite grid it will be noted that black squares are 3 columns apart
horizontally and 3 rows apart vertically. Oddities begin to occur when comparing rectangular groups. Imposing a "template" of the considered square/rectangle within the infinite grid results in the "3" factor having some columns or rows having 1 more black than others. This may be noted in some way within the squares table above.
2 In drawing and coloring grids, if a black diagonal line starts or ends in a corner, it can
be removed as adjacency is preserved. This is a consideration of the table above.
3 May be the Int and Mod functions have a continuing role.
Eureka!! - Squares Anyway
