[seqfan] Re: Parking lot for bad drivers
Veikko Pohjola
veikko at nordem.fi
Sat Jul 25 10:23:28 CEST 2015
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
More information about the SeqFan
mailing list