Problem 015

[misterikkit]

I'm not sure what is meant by "backtracking" in this problem. To me, it could mean a few things:
1) you cannot use the same edge twice
2) you cannot visit the same intersection twice
3) you are not allowed to move up or to the left

I guess #3 implies the first two, but I just want to make sure I understand this problem because my initial answers were incorrect.

I'd also like to check that this isn't a trick question. When asked "How many routes are there through a 20x20 grid?" Does it mean routes from the top left corner to the bottom right corner without backtracking?

Thanks,
Jonathan

[daniel.is.fischer]

It's interpretation 3), and routes from top left to bottom right without ever moving left or up.

[misterikkit]

thanks!

[fish613]

Hi,
I have a program I wrote to solve problem 15 (how many paths are there through a square grid 20x20?). For smaller numbers than 20 (up to about 10), it is definitely giving the right answer, confirmed by other methods. However, the answer I get for 20, xxxxxx, is being marked wrong. Is the fault in my program or somewhere else?
Thanks,
fish613

[hk]

I think there is some fault in your program.
The answer is quite near, though, so I edited your post.

[fish613]

Thanks for the reply,
When you say my answer was near, do you mean it was nearly right or it was the right answer for another value of n rather than 20?

[hk]

I checked that the answer you were entering was wrong. So the fault is yours.

[fish613]

I've checked my program over a few times. As far as I can see, everything is going ok. So can someone possibly check my reasoning?
I reasoned as follows:

Expand

Correct reasoning removed

As far as I can tell, this is correct. But I'm not 100% sure. Can anyone offer advice?
Thanks.

Edit by hk

[hk]

Your reasoning is correct but unnecessary complex.
The only thing is that you are losing accuracy somehow.
The last four digits of your answer were incorrect. Are you using the right datatype?
BTW why are you calculating 21 of those coefficients while one is enough?

[fish613]

As to the first, data types have already been giving me problems, so I'll recheck that and see if I can use other types. Thanks for the reassurance!
As to the second, why I am calculating 21 coefficients, if you're referring to some clever simplification it's because I don't know of any. I'm only a high school student

(P.S. Sorry I've been leaving in too much detail - I'll be more careful to leave it out in future.)


Edit: I just changer the data type from "float" to "double" (in C++) and got the solution right! Thanks for all your help!

[hk]

As to the second, why I am calculating 21 coefficients, if you're referring to some clever simplification it's because I don't know of any. I'm only a high school student

But a clever one!
If you know how to calculate the number of paths to any point you mentioned, why not use that same technique for the point in question? just extend in your thoughts the square enough to find the point in question to lie also on the kind of line you described.
But perhaps better still: read the forum for this question.

Edit: I just changed the data type from "float" to "double" (in C++) and got the solution right! Thanks for all your help!

Congrats
Up to the next problem!

[fish613]

But a clever one!

I wouldn't say that - according to the site I am a poor 2% genius. But I've done a lot of maths outside school. That helps.

If you know how to calculate the number of paths to any point you mentioned, why not use that same technique for the point in question? just extend in your thoughts the square enough to find the point in question to lie also on the kind of line you described.

I thought about that for a minute and I see what you're saying. Thanks for that!
My next challenge will be to find a way to do the same for a rectangle. You can find a line in almost the same way, but it seems to me the numbers of paths at the points will be only some of the coefficients, if you see what I mean...

[fatcat1111]

#Problem 15 (View Problem) is ambiguous. It reads:

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

The problem is that "backtracking" is not used in the normal sense here, at least not as it is used in graph theory. For example, with this problem's example, if the verticies are numbered starting with 1 in the upper left corner, ending with 9 in the bottom right, as in:

123
456
789

then the following path is legal:

1, 2, 3, 6, 5, 4, 7, 8, 9

However, this isn't listed as one of the possible answers to the example.

If backtracking is to mean "never moving away from the end", rather than "all edges in the walk are distinct" that should be made clear in the problem statement.

Thank you for this wonderful site!

[rayfil]

That is why an example was given in an attempt to avoid any ambiguity in the terminology.

Every effort is made to provide a clear description of the problems without guessing what the author intended. It is known that the meaning of words may differ from one person to another for numerous reasons, and examples are thus often used whenever this could happen. This is probably one of the main features why this site has become so popular.

[stijn263]

I think the addictivity of seeing a green tick is the reason why this site has become so popular

[quilan]

I think the addictivity of seeing a green tick is the reason why this site has become so popular

I think the inherent delay in refreshing the page once you submit an answer is probably the most stressful moment for me here. It's like, spend hours crafting a crazy algorithm that finally works and then submit your answer...

"it's... wait for it.......... wait for it.......... I see the header now..... it's GOOD! Phew!"

[daniel.is.fischer]

But on the other hand, if it's bad, you still have a nice problem to keep you amused for the rest of the weekend

[sanya]

It's interpretation 3), and routes from top left to bottom right without ever moving left or up.

The problem seems to be defined inaccurately.

I actually did a "brute force" and found all possible routes.
Here is the Python script i used http://dumpz.org/15994/
I checked its output for the 3x3 and 4x4 grids manually and i am pretty sure it's correct.

For the 20x20 grid there are 1370 routes.

Being very confused about declaring this answer incorrect i have watched for the answer on the spoiler site just to estimate how far i am from the right way.

(I do not copy answers from that site if i can't solve the problem in case you might think so;-) You actually can see that from statistics:D)

The number of routes given there is quite huge.
I think it's simply impossible to get so many routes without moving up and left.

So i suggest to define the term "backtracking" more accurately.

Thanks.

[stijn263]

I think it's simply impossible to get so many routes without moving up and left.

It is possible, think about it some more. This will help you debugging perhaps, I get for n x n:
n --> #
2 --> 6
3 --> 20
4 --> 70
5 --> 252

[sanya]

I think it's simply impossible to get so many routes without moving up and left.

It is possible, think about it some more. This will help you debugging perhaps, I get for n x n:
n --> #
2 --> 6
3 --> 20
4 --> 70
5 --> 252

You are right - i am missing some routes