We assume a truck as a $1 \times (k + 1)$ tile. Our parking is a $(2k + 1) \times (2k + 1)$ table and there are $t$ trucks parked in it. Some trucks are parked horizontally and some trucks are parked vertically in the parking. The vertical trucks can only move vertically (in their column) and the horizontal trucks can only move horizontally (in their row). Another truck is willing to enter the parking lot (it can only enter from somewhere on the boundary). For $3k + 1 < t < 4k$, prove that we can move other trucks forward or backward in such a way that the new truck would be able to enter the lot. Prove that the statement is not necessarily true for $t = 3k + 1$.
Problem
Source:
Tags: combinatorics, Tiling
sami1618
30.09.2024 19:29
The most intuitive way to place the trucks into the gird is as follows (shown for $k=5$). It consists of $3k+1$ trucks. Notice that the middle truck in the bottom row will always end up covering the center cell. We now have a important claim. Claim: If the center cell is covered by a truck, then there are at most $3k+1$ trucks in the table WLOG assume that the truck is vertical. Notice that at most one truck can be placed in each row and column. There can be at most $k$ vertical trucks to the left and right of it and at most $k$ trucks in total in the columns above and below it, finishing the claim. [asy][asy] size(5cm); import graph; // Define the size of the grid int gridSize = 11; // Draw the grid for (int i = 0; i <= gridSize; ++i) { draw((i, 0)--(i, gridSize), gray); // Vertical lines draw((0, i)--(gridSize, i), gray); // Horizontal lines } // Highlight the central square filldraw((5, 5)--(6, 5)--(6, 6)--(5, 6)--cycle, lightgray); // Function to draw a 1x6 or 6x1 rectangle with a specific color void drawRectangle(pair start, bool horizontal, pen color) { if (horizontal) { filldraw(start--(start.x+6, start.y)--(start.x+6, start.y+1)--(start.x, start.y+1)--cycle, color); } else { filldraw(start--(start.x+1, start.y)--(start.x+1, start.y+6)--(start.x, start.y+6)--cycle, color); } } // Define colors for different regions pen color1 = lightblue; // Top-left region (5x6 rectangle) pen color2 = lightgreen; // Bottom region (6x11 rectangle) // Divide the 5x6 rectangle in the top-left corner into 1x6 rectangles for (int i = 0; i < 5; ++i) { drawRectangle((i, 5), false, color1); // Vertical 6x1 rectangles (top-left) } // Divide the 6x11 rectangle at the bottom into 1x6 or 6x1 rectangles for (int i = 0; i < 11; ++i) { drawRectangle((i, 0), false, color2); // Vertical 6x1 rectangles (bottom-left) } for (int j = 6; j < 11; ++j) { drawRectangle((0, j), true, color2); // Horizontal 1x6 rectangles (bottom-right) } [/asy][/asy] Thus there will always be at most $3k+1$ trucks in the table, so no new truck can enter. This finishes the second part of the problem. Now it helps to consider the following packing of $4k$ trucks into the rectangle. [asy][asy] size(5cm); import graph; // Define the size of the grid int gridSize = 11; // Draw the grid for (int i = 0; i <= gridSize; ++i) { draw((i, 0)--(i, gridSize), gray); // Vertical lines draw((0, i)--(gridSize, i), gray); // Horizontal lines } // Highlight the central square filldraw((5, 5)--(6, 5)--(6, 6)--(5, 6)--cycle, lightgray); // Function to draw a 1x6 or 6x1 rectangle with a specific color void drawRectangle(pair start, bool horizontal, pen color) { if (horizontal) { filldraw(start--(start.x+6, start.y)--(start.x+6, start.y+1)--(start.x, start.y+1)--cycle, color); } else { filldraw(start--(start.x+1, start.y)--(start.x+1, start.y+6)--(start.x, start.y+6)--cycle, color); } } // Define colors for different regions pen color1 = lightblue; // Top-left region pen color2 = lightgreen; // Bottom-right region pen color3 = lightred; // Top-right region pen color4 = lightyellow; // Bottom-left region // Divide and draw 1x6 or 6x1 rectangles within the original 5x6 and 6x5 rectangles // First 5x6 rectangle (at (0, 5)) -> vertical 6x1 rectangles, color1 for (int i = 0; i < 5; ++i) { drawRectangle((i, 5), false, color1); // Vertical 6x1 rectangles } // Second 5x6 rectangle (at (6, 0)) -> vertical 6x1 rectangles, color2 for (int i = 6; i < 11; ++i) { drawRectangle((i, 0), false, color2); // Vertical 6x1 rectangles } // First 6x5 rectangle (at (5, 6)) -> horizontal 1x6 rectangles, color3 for (int j = 6; j < 11; ++j) { drawRectangle((5, j), true, color3); // Horizontal 1x6 rectangles } // Second 6x5 rectangle (at (0, 0)) -> horizontal 1x6 rectangles, color4 for (int j = 0; j < 5; ++j) { drawRectangle((0, j), true, color4); // Horizontal 1x6 rectangles } [/asy][/asy] Notice that the center square must be uncovered as $3k+1<t$. Let $R$, $G$, $Y$, and $B$ denote the respective sets of trucks that lie to the four directions of the center cell, respectively. Let $R'$, $G'$, $Y'$, and $B'$ be the four trucks from each set that are the closest to the center. Now we can move all the trucks in $R$ directly behind $R'$ and similarly for other groups. Now we will clearly be able to move these four blocks until they all touch the wall and will either lie in the above configuration or its reflection. Now the remaining truck can easily enter, finishing the problem.