OCD dog

Treat the $46 \times 46$ intersections as lattice points bounded by the square with diagonally opposite corners $(1,1), (46,46)$ (including points on the boundary). It is obvious that the points on the sides are reachable, the dog just runs to one of the corners and go to the top right corner. All $(x,y)$ in the range any $x,13 \leq y \leq 34$ is reachable, the dog runs to $(1,y)$ , and then $(46,y)$ and then the top right corner. A similar argument for all $(x,y)$ in the range any $y,5 \leq x \leq 42$ is reachable, the dog runs to $(x,1)$ , and then $(x,46)$ and then the top right corner. There are 4 more $3 \times 11$ rectangles that we have not considered. Let them be rectangle $1,2,3,4$ starting from the top left rectangle in clockwise order. If rectangle 1 or 2 reached from the horizontal direction, there are not enough blocks for the dog to run to the top row. If rectangle 2 or 3 reached from the vertical direction, there are not enough blocks for the dog to run to the rightmost column. It is clear that rectangle 1 or 4 cannot be reached vertically, as the dog must change direction from one of the columns where $x=2$ to $4$ , which the dog cannot stop there. It is clear that rectangle 3 or 4 cannot be reached horizontally, as the dog must change direction from one of the rows where $y=2$ to $12$ , which the dog cannot stop there. So now it is shown that these points are unreachable. So we covered all points and only these 4 rectangles are unreachable, which gives us the answer $4 \times 33=132$ .

say that the horizontal direction as $x$ and the vertical direction as $y$ and the dog stand at origin $(0,0)$

Note that Any time the dog runs to the right, it runs at least 4 consecutive blocks to the right, and any time it runs up, it runs at least 12 consecutive blocks up.

from this information we know that the dog can not stop (change the direction) when $x=1, 2, 3$ or $x=46-1, 46-2, 46-3$ or $y=1,2,...,11$ or $y=46-1, 46-2, ...,46-11$ , if the dog want to go to the food. There is 6*22=132 intersection of $x$ and $y$ of at this condition. claim this is total of unreachable point.

now, we show that 132 point above is unreachable

1. Its clear that the point at $x=1,2,3$ and $y=1,2,3,...,11$ is unreachable, since the dog runs at least 4 consecutive blocks to the right, and at least 12 consecutive blocks up.

2. For (x,y) with $0<x<4$ or $0<y<12$ or $42<x<46$ or $34<x<46$ except for the first case. for this case

a. if $y<12$ , then the dog is run with vertical direction and $42<x<46$ so the dog can not turn the direction, it'not posibble to reach $x=46$

b. if $46>y>34$ and $0<x<4$ then the dog at horizontal direction so the dog can not reach $y=46$

c. if $46>y>34$ and $42<x<46$ then if the dog at horizontal direction so the dog can not reach $y=46$ and if the dog at vertical direction the dog can not reach $x=46$

Now we show that the rest point is reachable

for $(x,y)$ with at least one of $x$ or $y$ satisfy $4\leq x\leq 42$ or $12\leq y\leq 34$ .

if $x$ and $y$ both satisfy condition its easy to past the point by $(0,0)\rightarrow (x,0)\rightarrow (x,y)\rightarrow (46,y)\rightarrow(46,46)$

if one of $x$ or $y$ satisfy condition WLOG say $x$ satisfy the condition so $4\leq x\leq42$ , the dog can choose the direction $(0,0)\rightarrow(x,0)\rightarrow$ past $y$ $\rightarrow(x,46)\rightarrow(46,46)$

The claim satisfy so there is 132 unrechable point.

The dog will start runing either right or up. So he will be unable to reach the first 4 vertical streets or the first 12 horizontal streets with his first turn. This means that there will be 3x11 unreachable intersections here. But as the last stretch must also satisfy the rules, there will be another 3x11 unreachable intersections. If we see at the top left corner we see the situation is the same, and at the down right corner too, because there is no way that the dog enter at the intersection and be able to reach de exit. The rest of the intersections are easily reachable just running directly to the selected row, or column, whatever it applies to become factible to reach the place.

Consider the four 4x12 chunks of blocks in the corners of the grid. The intersections within the chunks touching the start and end points are obviously unreachable. The other two chunks also have unreachable points inside. Consider an intersection within the leftmost, uppermost chunk. The dog must first travel up to the intersection's y-coordinate, then turn right. Now there is no way to get to y=46, and no way to complete the journey. We can apply similar logic to the rightmost, bottommost chunk. These four chunks have 4x3x11=132 intersections. We must show that all other points are attainable. Consider the "+" formed by the grid without the corner chunks. We can reach any point within or on the border of the portion spanning 46 vertical blocks simply by moving right to the appropriate x-coordinate, moving all the way up, and moving the rest of the way right. Similar logic shows that any point within or on the border of the portion spanning 46 horizontal blocks is reachable. This covers all the remaining points. Q.E.D.

If the dog initially starts moving upwards, it will not be able to start moving right until it has moved $12$ blocks, and if it initially starts moving to the right, it cannot move upwards until it has moved $4$ blocks. Because of this, there is a $3 \times 11$ group of intersections near the bottom-left corner that the dog cannot travel through. To help understand this, imagine the dog trying to get to the intersection that is one block up and one block to the right from the starting intersection. In order to get there, the dog would have to go one block to the right and then change direction and go one block up, or vice versa. But it cannot do this because it must travel at least $4$ consecutive blocks to the right or $12$ consecutive blocks upwards, so it cannot reach this intersection. Similar reasoning shows that the dog cannot reach any of the intersections in a $3 \times 11$ group of intersections near the bottom-left corner because it would have to change direction before moving the required number of blocks in a certain direction. The dimensions of the group are $3$ and $11$ because the dog cannot change direction after moving $1, 2,$ or $3$ blocks to the right or $1, 2, \cdots , 11$ blocks upwards.

For a similar reason there is another $3 \times 11$ group of unreachable intersections near the top-right corner of the grid. Imagine if the dog were to reach the intersection one block below and one block to the left of the top-right corner. If he were currently moving in the upward direction, he could move one unit upward and then one unit to the right. But his last stretch must also satisfy the conditions of consecutive blocks so this would be invalid, and if he moved to the right, he would have to move up only one block, so that would be invalid too. There is a $3 \times 11$ group of intersections near the top-right corner where the dog would have to move fewer than $4$ consecutive blocks to the right or $12$ consecutive blocks upward to reach its destination, so these are unreachable.

There are also two $3 \times 11$ groups of unreachable intersections near the top-left and bottom-right corners of the grid for reasons similar to the others. Imagine of the dog had reached the intersection one block up and one block to the left of the bottom-right corner. He could only have reached this by first moving $44$ blocks to the right and then $1$ block upward. But in order to reach his destination, he would still have to move one more block to the right at some point, which would violate the condition of having to move at least $4$ blocks to the right consecutively. Each intersection in this $3 \times 11$ group can only be reached by first moving to the right and then upwards, and each is less than $4$ blocks away from the right side of the grid, so each of these intersections is unreachable. The same applies for a $3 \times 11$ group near the top-left corner: Each intersection in that group can only be reached by first moving upwards and then to the right, and each is less than $12$ blocks from the top of the grid.

There is no reason why the dog could not reach any other intersection in the grid, so there $4 \times (3 \times 11)=132$ total intersections that it cannot reach because there are $4$ groups of unreachable intersections with dimensions $3 \times 11$ .

Since the dog can move more than $12$ blocks up and more than 4 blocks right, the border of the area can be traversed easily $(46 > 12$ and $46 > 4)$ . This leaves us with a $44 * 44$ area.

However, there is a $3 * 11$ area the dog cannot reach in the bottom left hand corner since it is less than $4$ blocks right and $12$ blocks up. This gives us $33$ intersections the dog cannot reach.

Similarly, the top right hand corner also has a $3 * 11$ area the dog cannot reach as he is unable to more up or right in this area. This gives us another $33$ intersections.

The remaining two corners also have a $3 * 11$ are the dog cannot go through as any motion right or up will lead it to the $33$ intersections in the top right hand corner.

This gives us a grand total of $3*11*4 = 132$ intersections that cannot be reached.

Other than this, any other intersection can be reached by moving right $4$ or more blocks and traversing up to the top part of the border, where it can reach the end point easily or running up $12$ or more units and then running to the rightmost part of the border where it can likewise reach the endpoint very easily.

If there are 46 x 46 streets, then let's number them 0 to 45 in each direction. We can consider the two directions independently.

We want solutions to x1 + x2 + ... + xn = 45 (all xi >= 4) y1 + y2 + ....+ yn = 45 (all yi >= 12)

Let's start with the y's. He cannot do more than 3 stages, since 4 x 12 = 48, which is too far. and he is limited to these choices: 15,15,15 16,15,14 16,16,13 17,14,14 17,15,13 17,16,12 18,14,13 18,15,12 19,13,13 19,14,12 20,13,12 21,12,12 33,12 45 So the y-coordinates which can be stopped at are those numbers plus the sums of any two of them on a single line, which is: all numbers from 12 through 33 and 45. That is, a total of 24 different y-coordinates which can be stopped at.

For the x-coordinates it is similar but more encompassing: you cannot reach 1, 2, 3, or 42, 43, or 44, so there are 40 different x-coordinates. The ones where he cannot even pass through are the ones where both the x and y coordinates are on the "black list".

x = 1, 2, 3 or 42, 43, 44 y = 1 - 11 or 34 - 44 The number of those is 6 * 22 = 132.

Let the position of the dog be $(1,1)$ , and let each intersection be on a lattice point such that if the dog travels one block up from his starting point, then he will be at $(1,2)$ , and at $(2,1)$ if he traveled one block to the right.

Notice that the dog cannot turn where he either a) will cut his required run short, or b) will be unable to reach his food. So, he cannot turn

• before the line $x = 5$
• before the line $y = 13$
• after the line $x = 43$ (with the exception of $x = 47$ )
• after the line $y = 35$ (with the exception of $y = 47$ )

Judging by the restraints, there exist $4$ rectangular grids of lattice points that the dog cannot enter. One is at the bottom left and is bounded by the points $(2,2)$ , $(4, 2)$ , $(2, 12)$ , and $(4, 12)$ . This area bounds $(4 - 2 + 1) \cdot (12 - 2 + 1) = 33$ lattice points.

Another is at the top left and is bounded by the points $(2, 36)$ , $(2, 46)$ , $(4, 36)$ , and $(4, 46)$ . It is congruent to the one bounded in the bottom right corner, and both contain $(4 - 2 + 1) \cdot (46 - 36 + 1) = 33$ lattice points.

The final area is at the top right, and it is bounded by the points $(44, 36)$ , $(46, 36)$ , $(44, 46)$ , and $(46, 46)$ , and it cointains $(46 - 44 + 1) \cdot (46 - 36 + 1) = 33$ lattice points (surprise, surprise!).

Thus, the total number of intersections that the dog cannot run through is $33 \cdot 4 = \boxed{132}$ .

For an intersection to be unreachable, it is required that there be:-

1. No paths leading from the origin up to that point, AND,
2. No paths leading from that point up to the destination.

Since our fellow canine has a constraint on the minimum and not maximum number of steps, it can easily get to virtually any intersection, EXCEPT to some intersections near each of the corners of the grid.

To illustrate:-

Consider a 46x46 grid where x = street index to the right, and y = street index upwards. Clearly the indices run from 0->45

.............................................. FOOD (45,45)
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
.***......................................***.
..............................................
START (0,0)

Where ' . ' is a reachable intersection and ' * ' is unreachable. Just near the corners there are 3x11 blocks of intersections of streets that the dog cannot pass through. These are the points which satisfy one of the following:-

1. (x,y) : 0<x<4 AND 0<y<12
2. (x,y) : 0<x<4 AND 0<(45-y)<12
3. (x,y) : 0<(45-x)<4 AND 0<y<12
4. (x,y) : 0<(45-x)<4 AND 0<(45-y)<12

These constraints arise from the two requirements mentioned above. That is to say, to reach any intersection:-

1. From the starting position (1,1), the dog must have used a path that required at least 12 steps upwards or none, AND, at least 4 steps rightwards or none.
2. To the destination, there are at least 12 steps upwards or none, AND, there are at least 4 steps rightwards or none.

The 3x11 grids marked in ' * ' violate these requirements and are hence "unreachable".

Therefore in total, there are 4x(3x11) = 132 intersections the dog will never run through.

Let's t

Let's look at the quadrant formed by: $(0,0), (12,0), (0,4), (12,4)$

Any point strictly inside this quadrant is not accessible. The no. of points inside this quadrant $= 3*11 = 33$

There are similar quadrants on each corner of the grid:

1. Top-Left
2. Top-Right
3. Bottom-Left
4. Bottom-Right

The inner points of each of these quadrants are inaccessible.

Thus total inaccessible points $= 33*4 = \boxed{132}$

I represented each intersection as a dot, and a block is represented as the space between two consecutive dots. We can see the grid of 46 x46 streets on a Cartesian plane forming a square (starting from the bottom leftest point - (0,0) - to the top rightest point - (45,45)).

The first thing that I asked when I saw this question was 'How can the dog reach a certain point?" After much thought, it was actually obvious but many of us I am sure would have missed it out at first glance. Since the dog only moves to the right or upwards, to reach a particular point, it can move

1. $\uparrow \rightarrow$
2. or $\rightarrow \uparrow$

Ok, how does that help? Notice that the dog needs to travel at least $4$ blocks to the right and $12$ upwards each time. [Before proceeding, note that $4$ blocks means $5$ intersections, which is in turn represented as $5$ dots.] Hence, any point that is within the $1$ to $3$ blocks to the right and $1$ to $11$ blocks upwards from the start point $(0,0)$ cannot be reached by the dog. This is shown in the diagram below which is a representation of the bottom leftest $13$ x $5$ streets: (The red dots represent intersections that can be run through and blue dots just means those that cannot.) Image of bottom left 13x5 streets

As you can see, in the bottom left corner, $3*11 = 33$ intersections are not reachable.

Next, notice that the requirement of the question states that the last stretch that the dog runs must also satisfy the conditions. Hence, any intersection run through by the dog must at least be $4$ blocks away the line $x=45$ ( Condition 1 )- which represents the last whole column of streets - and $13$ blocks away from the line $y=45$ ( Condition 2 ) - the last whole row of streets. Refer to the next diagram and you will observe 4 $3$ x $11$ blue squares, labelled A to D. The $4$ dots on the edge of the diagram represents the $4$ corner intersection, with the green dot representing where the food is.

OCD 2

These blue squares each represents $3$ x $11$ intersections which are unreachable by the dog. Square A fails to satisfy Condition 2 , Square B fails to satisfy Conditions 1 and 2 and Square C fails to satisfy Condition 2 . Square D has been shown to be unreachable by the first diagram above.

As such, the number of different intersections unreachable by the dog equals to $3*11*4 = 33*4 = \boxed {132}$ .