City of Mar del Plata is a square shaped $WSEN$ land with $2(n + 1)$ streets that divides it into $n \times n$ blocks, where $n$ is an even number (the leading streets form the perimeter of the square). Each block has a dimension of $100 \times 100$ meters. All streets in Mar del Plata are one-way. The streets which are parallel and adjacent to each other are directed in opposite direction. Street $WS$ is driven in the direction from $W$ to $S$ and the street $WN$ travels from $W$ to $N$. A street cleaning car starts from point $W$. The driver wants to go to the point $E$ and in doing so, he must cross as much as possible roads. What is the length of the longest route he can go, if any $100$-meter stretch cannot be crossed more than once? (The figure shows a plan of the city for $n=6$ and one of the possible - but not the longest - routes of the street cleaning car. See http://goo.gl/maps/JAzD too.)
Problem
Source: Czech-Polish-Slovak 2012, P5
Tags: geometry, perimeter, combinatorics unsolved, combinatorics
22.04.2013 08:48
I have a solution to this problem but i amnot sure whether it is right or wrong.Please corrcet me if there is any mistake. The main thing here is that we should cover all the roads as much as possible without violating the conditions. I am considering $WN$ as y axis and $WS$ as x axis and the areas as unit squares. So to ensure all the roads to cover the man goes to $(0,1)$ then to then to $(1,n)$ then to$(2,n)$ then to$(2,0)$ but in this process he will reach $(n,n)$ in short time leaving all the horizontal roads uncovered. So this is not the path.. Now the person first goes to $(0,2)$ then to$(2,n)$ as proceeding in the same way as the previous..here he will reach$(n,0)$This is because here $n$ is even.the he goes to $(n,1)$ then to $(0,1)$ then to $(0,2)$ then to $(n,2)$ So like this he continues....But here one thing is there here will reach$(0,n)$ and then from there he has to reach$(n,n)$. But he cannot move across $y=n$. So the thing here to do is that that when he reaches$(n-2,0)$. Then he directly goes to $(n,n)$. So our path is completed and thus we have left the roads $y=n-1$ and$x=1$ untouched. This is the maximal length of the road. Before calculating the length i am still in doubt is there any other possiblity or is my proof incomplete?
03.02.2015 11:36
I claim that the maximal route leaves $4(n-1)$ unit streets uncrossed. The arrows in the picture depict one example of a possible route of the car. I am going to show now that indeed at least $4(n-1)$ unit streets remain uncrossed. Consider a random route of the car. Let me make use of some notations: $\bullet\ a$ denotes the number of unit streets of the route oriented to $SE$; $\bullet\ b$ denotes the number of unit streets of the route oriented to $NW$; $\bullet\ c$ denotes the number of unit streets of the route oriented to $SW$; $\bullet\ d$ denotes the number of unit streets of the route oriented to $NE$; $\bullet\ A$ denotes the total number of unit streets in the city oriented to $SE$; $\bullet\ B$ denotes the total number of unit streets in the city oriented to $NW$; $\bullet\ C$ denotes the total number of unit streets in the city oriented to $SW$; $\bullet\ D$ denotes the total number of unit streets in the city oriented to $NE$; It is obvious that $A=n+B$ and $C=n+D$. Moreover, $a=n+b$ and $c=n+d$, since the car starts from $N$ and it has to arrive in $S$. $(*)$ Suppose there is also an imaginary arrow from $S$ to $N$. Now look at the colored points: $\bullet$ the outdegree of each blue point is 1 greater than its indegree, therefore for any blue point there is an unit street leaving the point that can't be used in the route. $\bullet$ the indegree of each red point is 1 greater than its outdegree, therefore for any red point there is an unit street arriving in the point that can't be used in the route. Notice that all these not used streets are all oriented to $SE$ or $SW$. It follows that $a+c\le A+C - (2n-2)$ (because there are $2n-2$ colored points) and using $(*)$ we also get that $b+d\le B+D-(2n-2)$. Finally, $a+b+c+d\le A+B+C+D-4(n-1)$ and the conclusion follows.
Attachments:
