[seqfan] Re: Parking lot for bad drivers

[Veikko Pohjola]

Dear seqfans,

I am considering to submit my version of this parking lot problem (if it has not been done yet). The version is what I did call misinterpreted, because it refers to an idealized model of the whole: cars which can move horizontally to any direction and a parking lot which is an open square with permeable borders. It is thus just a mathematical excercise. The task is to find for an nxn square the maximum coverage by the occupied 1x1-spaces under the constraint that no rows of three occupied spaces can appear vertically, horizontally and diagonally.

Actually we have a tiling problem here. The maximum coverage of an nxn square can be obtained with a 3x3-size macrotile, but some extra challenge is offered by the evidence that a macrotile of one types can solve only 2/3 of the cases while another, symmetrical, is necessary to solve the rest.

The sequence of the maximum numbers of occupied spaces in an nxn square starts as follows: 1, 4, 6, 9, 16, 20, 25, 36, 40, 49, 64, 68, 81, ... (not in OEIS).

The original parking lot problem was launched elsewhere and then discussed by many other people. Thus, I will proceed to submission of this version only if nobody objects.

Regards,
Veikko


Vladimir Shevelev kirjoitti 19.7.2015 kello 12.47:

> On the other hand, if to mean the initial problem on drivers, in case n=15
> we have 102 cars:
> 
> XX_XX_XX_XX_XX_
> ______________X
> XX_XX_XX_XX_X_X
> XX_XX_XX_XX_XX_
> 
> XX_XX_XX_XX_X_X
> XX_XX_XX_XX_XX_
> 
> XX_XX_XX_XX_X_X
> XX_XX_XX_XX_X_X
> 
> XX_XX_XX_XX__XX
> XX_XX_XX_XX_XX_
> ______________X
> XX_XX_XX_XX_X_X
> 
> I get 1,2,4,8,12,17,24,30,38,48,56,66,80,90,102,...
> (not in OEIS).
> Conjecture: 1) if n==1 (mod 3), then a(1)=1, 
> a(n) = 4*(n-1)*(n+2)/9, n>=4;
> 2) if n==2 (mod 3), then a(n) = 2*(n+1)*(2*n-1)/9, n>=2.
> 3) if n==0 (mod 3), then a(n) = 4*(n/3)^2+x_n, n>=6. where x_n
> are small additives which till now I do not know: x_3=0, x_6=1, x_9=2, x_12=2, x_15=2.
> 
> Note that up to n=8, earlier Rob had 1, 2, 4, 8, 12, 16, 21, 26.
> However, for n=6 we have 17 cars
> 
> XX_XX_
> _____X
> XX_X_X
> XX_XX
> ______
> XX_XX
> 
> while for n=7 we have 24 cars:
> 
> XX_XX_X
> _______
> XX_XX_X
> XX_XX_X
> _______
> XX_XX_X
> _X_XX_X
> 
> and for n=8, as I have already written, we have 30 cars
> (Veikko's result which was confirmed by me in a simpler variant).
> 
> Best regards,
> Vladimir