This problem seems very hard!! I hear the solution is quite tricky and involved.

Muriatic wrote: This problem seems very hard!! I hear the solution is quite tricky and involved. It appears not to be so Color the rows alternately white and black. Move all the vertically faced cars in black rows into white rows. Now clear all the horizontal cars in black rows by moving them very far to the right or left. Now, the black rows are empty. Move the vertically faced cars into black rows. Now clear the horizontal cars in white rows by moving them very far out. At this point, we have essentially moved all horizontal cars very far out, which means that we can freely clear the vertically faced cars, and we're done. Remark To formalize this, consider a very large square containing all the cars. To "clear" a set of cars is to move them outside of the box, and then have them keep moving in the direction they are going in at every step. This solution was found by numbersandnumbers

WHAT Call a car horizontal if it is left-facing or right-facing, and \emph{vertical} otherwise. Color the columns black and white in an alternating manner. Surround all the cars in a box. It is sufficient to show that the cars can all leave the box. Perform the following procedure: Move all horizontal cars in a black column to a white column. This is possible because the cell immediately in front of each car is empty. Clear the black columns of vertical cars. This is possible because all cars in a black column must face the same direction. Move all the horizontal cars into black columns. This is possible because all vertical cars in black columns have left. Clear the white columns of vertical cars, which is possible for similar reasons as above. Clear the box of horizontal cars, which must all face the same direction With the box sufficiently big, all cars can move infinitely many times, as desired. $\square$

It's problems like this that make me wish the downvote button was still around

Here's the official solution write-up, complete with pretty diagram and some historical comments. Let $S$ be any rectangle containing all the cars. Partition $S$ into horizontal strips of height $1$, and color them red and green in an alternating fashion. It is enough to prove all the cars may exit $S$. [asy][asy] size(10cm); defaultpen(fontsize(12pt)); usepackage("amssymb"); picture base; draw(base, box((0,0), (7,5)), black+1); fill(base, box((0,0), (7,1)), rgb(1,0.9,0.9)); fill(base, box((0,2), (7,3)), rgb(1,0.9,0.9)); fill(base, box((0,4), (7,5)), rgb(1,0.9,0.9)); fill(base, box((0,1), (7,2)), rgb(0.9,1,0.9)); fill(base, box((0,3), (7,4)), rgb(0.9,1,0.9)); for (int i=1; i<7; ++i) { draw(base, (i,0)--(i,5), grey); } for (int i=1; i<5; ++i) { draw(base, (0,i)--(7,i), grey); } picture phase0; add(phase0, base); draw(phase0, (1.5,1.5)--(1.5,2.5), dashed+orange, EndArrow(TeXHead)); draw(phase0, (4.5,3.5)--(4.5,2.5), dashed+orange, EndArrow(TeXHead)); draw(phase0, (5.5,3.5)--(5.5,2.5), dashed+orange, EndArrow(TeXHead)); draw(phase0, (6.5,3.5)--(6.5,4.5), dashed+orange, EndArrow(TeXHead)); label(phase0, "$\blacktriangleright$", (1.5, 4.5)); label(phase0, "$\bigtriangledown$", (3.5, 4.5)); label(phase0, "$\blacktriangleright$", (1.5, 3.5)); label(phase0, "$\bigtriangledown$", (4.5, 3.5)); label(phase0, "$\bigtriangledown$", (5.5, 3.5)); label(phase0, "$\bigtriangleup$", (6.5, 3.5)); label(phase0, "$\blacktriangleright$", (0.5, 2.5)); label(phase0, "$\blacktriangleright$", (3.5, 2.5)); label(phase0, "$\bigtriangleup$", (2.5, 2.5)); label(phase0, "$\bigtriangleup$", (1.5, 1.5)); label(phase0, "$\blacktriangleleft$", (3.5, 1.5)); label(phase0, "$\blacktriangleleft$", (5.5, 1.5)); label(phase0, "$\blacktriangleright$", (6.5, 1.5)); label(phase0, "$\blacktriangleleft$", (4.5, 0.5)); label(phase0, "Step 1", (3.5,0), dir(-90)); picture phase1; add(phase1, base); draw(phase1, (5.5,1.5)--(0,1.5), dashed+orange, EndArrow(TeXHead)); draw(phase1, (6.5,1.5)--(7,1.5), dashed+orange, EndArrow(TeXHead)); draw(phase1, (1.5,3.5)--(7,3.5), dashed+orange, EndArrow(TeXHead)); label(phase1, "$\blacktriangleright$", (1.5, 4.5)); label(phase1, "$\bigtriangledown$", (3.5, 4.5)); label(phase1, "$\blacktriangleright$", (1.5, 3.5)); label(phase1, "$\bigtriangledown$", (4.5, 2.5), blue); // moved down label(phase1, "$\bigtriangledown$", (5.5, 2.5), blue); // moved down label(phase1, "$\bigtriangleup$", (6.5, 4.5), blue); // moved up label(phase1, "$\blacktriangleright$", (0.5, 2.5)); label(phase1, "$\blacktriangleright$", (3.5, 2.5)); label(phase1, "$\bigtriangleup$", (2.5, 2.5)); label(phase1, "$\bigtriangleup$", (1.5, 2.5), blue); // moved up label(phase1, "$\blacktriangleleft$", (3.5, 1.5)); label(phase1, "$\blacktriangleleft$", (5.5, 1.5)); label(phase1, "$\blacktriangleright$", (6.5, 1.5)); label(phase1, "$\blacktriangleleft$", (4.5, 0.5)); label(phase1, "Step 2", (3.5,0), dir(-90)); picture phase2; add(phase2, base); draw(phase2, (1.5,2.5)--(1.5,3.5), dashed+orange, EndArrow(TeXHead)); draw(phase2, (2.5,2.5)--(2.5,3.5), dashed+orange, EndArrow(TeXHead)); draw(phase2, (3.5,4.5)--(3.5,3.5), dashed+orange, EndArrow(TeXHead)); draw(phase2, (4.5,2.5)--(4.5,1.5), dashed+orange, EndArrow(TeXHead)); draw(phase2, (5.5,2.5)--(5.5,1.5), dashed+orange, EndArrow(TeXHead)); draw(phase2, (6.5,4.5)--(6.5,5), dashed+orange, EndArrow(TeXHead)); label(phase2, "$\blacktriangleright$", (1.5, 4.5)); label(phase2, "$\bigtriangledown$", (3.5, 4.5)); label(phase2, "$\bigtriangleup$", (6.5, 4.5)); label(phase2, "$\bigtriangledown$", (4.5, 2.5)); label(phase2, "$\bigtriangledown$", (5.5, 2.5)); label(phase2, "$\blacktriangleright$", (0.5, 2.5)); label(phase2, "$\blacktriangleright$", (3.5, 2.5)); label(phase2, "$\bigtriangleup$", (2.5, 2.5)); label(phase2, "$\bigtriangleup$", (1.5, 2.5)); label(phase2, "$\blacktriangleleft$", (4.5, 0.5)); label(phase2, "Step 3", (3.5,0), dir(-90)); picture phase3; add(phase3, base); draw(phase3, (1.5,4.5)--(7,4.5), dashed+orange, EndArrow(TeXHead)); draw(phase3, (0.5,2.5)--(7,2.5), dashed+orange, EndArrow(TeXHead)); draw(phase3, (4.5,0.5)--(0,0.5), dashed+orange, EndArrow(TeXHead)); label(phase3, "$\blacktriangleright$", (1.5, 4.5)); label(phase3, "$\bigtriangledown$", (3.5, 3.5), blue); label(phase3, "$\bigtriangledown$", (4.5, 1.5), blue); label(phase3, "$\bigtriangledown$", (5.5, 1.5), blue); label(phase3, "$\blacktriangleright$", (0.5, 2.5)); label(phase3, "$\blacktriangleright$", (3.5, 2.5)); label(phase3, "$\bigtriangleup$", (2.5, 3.5), blue); label(phase3, "$\bigtriangleup$", (1.5, 3.5), blue); label(phase3, "$\blacktriangleleft$", (4.5, 0.5)); label(phase3, "Step 4", (3.5,0), dir(-90)); add(phase0); add(shift(8,0)*phase1); add(shift(0,-7)*phase2); add(shift(8,-7)*phase3); [/asy][/asy] To do so, we outline a five-stage plan for the cars. All vertical cars in a green cell may advance one cell into a red cell (or exit $S$ altogether), by the given condition. (This is the only place where the hypothesis about empty space is used!) All horizontal cars on green cells may exit $S$, as no vertical cars occupy green cells. All vertical cars in a red cell may advance one cell into a green cell (or exit $S$ altogether), as all green cells are empty. All horizontal cars within red cells may exit $S$, as no vertical car occupy red cells. The remaining cars exit $S$, as they are all vertical. The solution is complete. Remark: [Author's comments] The solution I've given for this problem is so short and simple that it might appear at first to be about IMO 1 difficulty. I don't believe that's true! There are very many approaches that look perfectly plausible at first, and then fall apart in this or that twisted special case. Remark: [Higher-dimensional generalization by author] The natural higher-dimensional generalization is true, and can be proved in largely the same fashion. For example, in three dimensions, one may let $S$ be a rectangular prism and partition $S$ into horizontal slabs and color them red and green in an alternating fashion. Stages 1, 3, and 5 generalize immediately, and stages 2 and 4 reduce to an application of the two-dimensional problem. In the same way, the general problem is handled by induction on the dimension. Remark: [Historical comments] For $k > 1$, we could consider a variant of the problem where cars are $1 \times k$ rectangles (moving parallel to the longer edge) instead of occupying single cells. In that case, if there are $2k-1$ empty spaces in front of each car, the above proof works (with the red and green strips having height $k$ instead). On the other hand, at least $k$ empty spaces are necessary. We don't know the best constant in this case.

I can't find mistake in my solution. Please help me to find it. We use the following process. Suppose Right facing cars are R , left facing are L, and similarly U & D. 1)At first, Choose a R. 2) Then we move it rightward. By condition, no L is there in that row. 3) While moving it rightward, if we get an U. Then we we move U forward by one step and then again keep moving R. 4) If we get a L, we move it forward by one step then again keep moving. 5) If we get a R, then we stop moving the previous car and contrate in this new R and keep moving it. We can do this process infinite many times. Hence we are done. I can't find any mistake. Please judge it..

Please reply so that I can know whether my solution is okay.

Never mind.

@2below Thanks for pointing it out.

I guess intuition is key here.

@ayan_mathematics_king @brainiacmaniac31 Each car needs to be moved infinitely many times, not only one car. In your solutions, you only showed that at least one car can be moved infinitely many times.

NikoIsLife wrote: @ayan_mathematics_king @brainiacmaniac31 Each car needs to be moved infinitely many times, not only one car. Ohhhhh thank you for pointing that out.

Edit: below solution is false. The solution I found seems to be completely different from the intended solution (and possibly far more natural to think of) We will call a car to be a 'east car' if it faces east. Define 'west car', 'north car' and 'south car' similarly. At every stage, we'll just ignore an east car if it is further east than any non-east car. We'll even pretend it doesn't exist. Similar holds true for other directions. Call the score of a car configuration as the sum over cars of the number of moves the car needs to make such that we may pretend it doesn't exist. Call a car configuration valid if it conforms to the problem statement. (i.e. Space between cars, no 2 cars destined to collide) Observe that we are done if we can reach a valid config from any valid config as the score plays the role of a decreasing monovariant. Assume ftsoc that we have a valid car config such that we can't reach any other valid config. 2 in front of every car must be another car. Join these cars by a directed edge. In the formed graph, every car has outdegree 1, so there is cycle. Move every car part of this cycle one forward.

p_square wrote: Move every car part of this cycle one forward. I think the following counterexample shows that your operation does not preserve validity. ..v.<... ........ ..>....v >...^... ........ ^......< In this example, the cycle that you construct involves all eight cars. But in the third row you will get end up with one car directly blocked. EDIT: I misunderstood the previous post, but here's another example >.v. .>.v ^.<. .^.<

Ah, I didn't explain it very well. So, (like as in the above example), if there is a car such that 2 ahead of it is empty, we just move the car. For instance if >..^... was part of the grid, we wouldn't even make the graph. Instead we'd move the left car to get .>.^... The point is that validity is preserved because all of the cars we moved where on the same colour in a chessboard colouring. Each edge can only separate cars that only have 1 square in between. Edit: nvm, I just realized, this solution is indeed a fakesolve.

Didn't expect to be trolled Call the car facing upwards, downwards, left, and right as $A,B,C,D$ type. Notice that once a car leaves the board, then we could just "ignore" it as it could move freely along the infinite grid. Notice that we have finitely many cars, therefore we could border all the cars with a giant rectangle $m \times n$ such that all cars are inside this rectangle. Now, color the rows alternately with black and white. Now, move all the $A$ and $B$ type cars which are in the black row. This can be done since by the initial hypothesis, there must be a space available in front of every car. Therefore, there are no more $A$ and $B$ type cars in the black row. This results all $C$ and $D$ type cars in the black row could leave the board. Therefore, all the $A$ and $B$ type cars Therefore, we have all the $C$ and $D$ cars are in the white row. Now, the initial hypothesis of "there must be a space in front of every car" is still satisfied. Do the same to all the $A$ and $B$ type cars and we can remove all the $C$ and $D$ type cars in the white row. Now, since there are only $A$ and $B$ type cars in the grid, and there mustn't be any two of the same type facing to each other in a particular column, then they all could manage to leave the $m \times n$ grid.

Reading the above solutions, I am inclined to think that the following is probably wrong, but I am unable to find any mistake myself. Hopefully someone will be able to point out where I went wrong. EDIT: The two posts below point out why this is wrong. We draw arrows from one to car to the one in front of it(if any). Thus what we have is a directed graph, with indegree at most 2 and outdegree at most 1. Call a configuration of cars "stable" if every car has no car right in front of it. First, we define the move "Shifting" of a cycle for stable configurations: Suppose we have a directed cycle $C_1,C_2,\cdots,C_n$. Move $C_2$ to the cell right in front of it.Bring $C_1$ to the cell initially occupied by $C_2$. Next, move $C_3$ to the cell right in front of it. Bring $C_2$ to the cell which $C_3$ initially occupied, and keep going. Finally, we bring $C_n$ to the $C_1$'s initial cell. It is important to note that at the end of these moves, we have a stable configuration again. We show that for any given car we can eventually always move it. Pick a given car, $A_0$. Follow the arrows from it. What is formed is either a path, a cycle or a branch that leads into a cycle. At every stage, we Shift the cycle that is encountered on this branch. Assume FTSOC that $A_0$ is never moved and furthermore, there is a car, $A_1$ in the branch emanating from $A_0$ (the case with only cycles and paths is easy to deal with using the move of "Shifting " and its obvious analogue for a path) which is never moved in this process of Shifting cycles. (Note that this $A_1$ actually exists due to $A_0$ itself). Look at the car right in front of it, $A_2$(this car may be variable), say. It is eventually always in the same direction, due to obvious reasons. However, the row/column of $A_2$ can contain only finitely many cars in its ( i.e. that of $A_2$) direction. Thus, at one stage we see that $A_2$ is never moved again. Continuing in this way, we see that the branch can be made arbitrarily long, which is obviously a contradiction. This shows that we eventually end up with a cycle containing $A_0$ or we have a path containing $A_0$ with no car in front of the leading car. In the first case, we may just apply another "Shift". For the latter, we move the car in front of the path beyond the horizon so that we may no longer care about it. Next, we move the car behind it to its initial position and so on, until we reach $A_0$, at which point we are done.

You made the exact same mistake I did As Evan pointed out, stable configurations, needn't be preserved. v_Enhance wrote: >.v. .>.v ^.<. .^.< If you don't preserve the niceness of the configuration, you run into issues where shifting cars of a cycle is impossible. >v ^<

Thanks. Although v_Enhance's example does not directly cause problems: v_Enhance wrote: >.v. .>.v ^.<. .^.< I think we are allowed to start with: >...... >.v ... ^.< And this causes problems. I had misinterpreted the problem as " all the 4 cells directly surrounding a car are empty".

As there are finitely many cars, there is a rectangle that contains them all. Looking at each car, and move cars with no obstructions out of the rectangle$\textbf {(one by one)}. $ Keep doing this until all the cars have left the rectangle, or there's a configuration of obstructed cars. Since every car is obstructed, and can only obstruct one other car at a time. If we move one car, and release the freed cars. Another idea We give each car a weight as the following If it is unobstructed: infinite If it is obstructed and unmoveable $0. $ If obstructed and movable $:1$ for each car it blocks itself, a fraction for each car it is coblocking. Move cars with the highest weights till they leave the starting rectangle. Reevaluate the weights after every move. If the cars have the same weight pick at random, unless one of them moved the previous turn. Then move that one again.

tastymath75025 wrote: On an infinite square grid we place finitely many cars, which each occupy a single cell and face in one of the four cardinal directions. Cars may never occupy the same cell. It is given that the cell immediately in front of each car is empty, and moreover no two cars face towards each other (no right-facing car is to the left of a left-facing car within a row, etc.). In a move, one chooses a car and shifts it one cell forward to a vacant cell. Prove that there exists an infinite sequence of valid moves using each car infinitely many times. Nikolai Beluhov For our convenience, we call a car as 'vertical car' if it moves vertically or we call a car as 'horizontal car' if it moves horizontally. We first color the grid into white and rows alternatively. Here is an algorithm - First, move a vertical car one step forward if it is on a black row, and do not move the car if it is on a white row This means that the black colored rows are full of horizontal cars. We clear the horizontal cars on black rows and send them to a sufficiently faraway distance, much safer than the hindrance of vertical cars. Now the vertical facing cars will have an empty spot in front of them. Move each vertical facing car one step forward, so that all vertical facing cars are on a black row. Now the white colored rows are full of horizontal cars, therefore send each horizontal facing cars to a sufficiently faraway distance, much safer than the hindrance of vertical cars. This finally means that, the vertical cars do not have the hindrance of horizontal cars either. This means that, we can move each vertical car into a sufficiently far away distance, such that all north facing cars are sufficiently distant from their original position in the northern direction and the south facing cars are sufficiently distance from their original position in the southern direction. This means that now, given any car $C$ on the grid, $C$'s path is obstructed by a car which is moving in the same direction as $C$, which means that we can move each car indefintitely, as desired.

Define a vertical car to be a car facing up or down, and define a horizontal car to be a car facing left or right. It suffices to show every car can escape the bounding box. Color the rows black and white in an alternating fashion, then perform the following steps: 1. Move all vertical cars in white rows one space to a black row. We can do this because there is a space in front of every car, and no two cars face each other. 2. Move all horizontal cars in white rows out of the box. 3. Move all vertical cars to a white row. 4. Move all horizontal cars in black rows out of the box. 5. Move all vertical cars out of the box.

Step 1: Surround all the cars in a box. It suffices to show that all cars can leave the box. Step 2: Color all the rows alternately white and black. Step 3: Move all the vertically faced cars from a white row to a black row. Step 4: Clear all the horizontally faced cars that are in a white row. Step 5: Move all our vertically faced cars to a white row. Step 6: Clear all the horizontally faced cars on a black row. Step 7: We have cleared all horizontal faced cars, so we can now clear all the vertically faced cars. Step 8: All cars have left the box, so we are done.

Can someone please tell me if there is anything wrong with this solution? 1. Colour the grid in chessboard pattern. 2. Move all cars on black squares simultaneously (possible because all cars have empty square in front of them). Note: By "simutaneously", if we have cars $c_1,\ldots, c_k$ on black squares then we choose an arbitrary order to move them each by one square. 3. Now all cars are on white squares, so we can move them simultaneously because no cars are adjacent since no white squares are adjacent by edge, and now they are all on black squares. 4. Inductively, all cars are on the same coloured squares after moving all of them "simultaneously", so no car will be blocking another after this. Repeat indefinitely. Edit: This is a fakesolve

NoctNight wrote: Can someone please tell me if there is anything wrong with this solution? 1. Colour the grid in chessboard pattern. 2. Move all cars on black squares simultaneously (possible because all cars have empty square in front of them). Note: By "simutaneously", if we have cars $c_1,\ldots, c_k$ on black squares then we choose an arbitrary order to move them each by one square. 3. Now all cars are on white squares, so we can move them simultaneously because no cars are adjacent since no white squares are adjacent by edge, and now they are all on black squares. 4. Inductively, all cars are on the same coloured squares after moving all of them "simultaneously", so no car will be blocking another after this. Repeat indefinitely. It might happen that two cars are facing the same square so you cant do that.

I see, thanks

Hello, the math club at my school has been working on a generalization of this problem which involves k * 1 cars, (not the same as the generalization given in the historical note - the cars here are wide instead of tall, ie the move in a direction perpendicular to their long axis). Is anybody aware of a name or an attempted solution to this problem? It seems significantly harder than the original - we were not able to prove that the problem is solvable no matter how much empty space we put in front of each car

guys I do not think donald trump is a very good guy. anyway this problem was too easy for me, solved it in 12 minutes in my head while my wife jill biden yelled at me for not eating my leafy greens. Solution: Take the minimal rectangle $R$ containing all the cars. First, we claim that if at some point all the cars are no in $R$ then the task can be completed. Indeed, note that all north facing cars must have exited $R$ from it's north side. This also holds for west, south, and east. From here it is fairly obvious to see that no pair of cars facing different directions can ever occupy the same square regardless. Thus, cycliclally moving each car one space moves each car an infinite number of times. Thus, it is sufficient to show that there is some algorithm to move all the cars out of $R$ in finite time. We provide such a strategy below. Alternate coloring the rows of $R$ red and blue. First, move all verticle facing cars on red rows exactly one times. Note that, now, all verticle facing cars are on blue rows. Thus, all horizontal facing cars on red rows can trivially move arbitrarily far and thus, off the rectangle. Now, all red rows are entirely empty, so all verticle facing cars move exactly once on to the emppty red rows. Now, all blue rows only have horizontal facing cars, and can trivially move off $R$ in finite time. Now, $R$ only contains horizontal facing cars, which can all trivially move of off $R$. Thus, $R$ is empty as desired. $\blacksquare$ jill is now throwing furniture so i have to go now.