City Block Shuffle

Probability Level pending

A man is lost in a big city at a location 8 blocks north and 8 blocks west of his destination point. He must navigate around a city block which is under construction. The construction activity is located 4 blocks east and 5 blocks south of his current location. How many possible paths are there around the construction that will get him to his destination point (8 blocks south and 8 blocks east)?

2032 1716 2172 2207

1 solution

A Former Brilliant Member
Jan 4, 2021

very nice challenge. i saw the pattern, but solved it by hand.
maybe you can add the info that he moves like a knight on a chess board (or jumps from roof to roof like spiderman :). i assumed first that he was moving on the street.

num IC - 4 months, 3 weeks ago

Thanks, I did add that he walked along streets only south and east. Thought I had that in there but it escaped me.

A Former Brilliant Member - 4 months, 3 weeks ago

ty for the add but that's not what i meant.
my first impression was the the man has to walk along the edges and not jump from block to block.
i hope the pic explains my assumption.
my numbers became too big, so i became aware that it's more like a kings (or rook) move.
(so it's like a chessboard and he starts at A8)

but more important: i tried to redo the formula that u use, but i couldn't.
can you explain it? or propose a link?

num IC - 4 months, 3 weeks ago

@Num Ic – http://www.dartmouth.edu/~chance/teaching aids/books articles/probability_book/Chapter12.pdf

See if this helps. If you can't follow using combination formula, then just add the number of paths with 1 in 1st row and 1st column. Fill out all squares, i.e. row 5, col 4 = 35 (15+20). Then from your total without construction, subtract the product of ways up to construction (35) and ways from construction to destination (35).

A Former Brilliant Member - 4 months, 3 weeks ago

@A Former Brilliant Member – great ty.
yeah i solved it by just adding them up but i want to find/understand a more elegant solution.
i see the binomial coefficients but i struggle to get the final formula.

num IC - 4 months, 3 weeks ago

@Num Ic – Added a post above to clear up confusion with the way combination formula is presented. You can use this formula for any case including when N=M or not.

A Former Brilliant Member - 4 months, 3 weeks ago

@A Former Brilliant Member – ty. the formula is very good. i still have to read the document to understand the creation of the formula.
i can just prove it by induction, but that does not satisfy me.

btw: i propose to remove the added sentence: "The man only walks south or east along a street."
it might cause even more confusion.

num IC - 4 months, 3 weeks ago

@Num Ic – Ok. Will remove. Just came across this wiki in Brilliant that might help with analysis:

https://brilliant.org/wiki/rectangular-grid-walk-no-restriction/

A Former Brilliant Member - 4 months, 3 weeks ago

@A Former Brilliant Member – that's a good link ty.
i saw the binomial coefficients, but could find no reasoning for them.
the wiki is helpul thank you.

num IC - 4 months, 3 weeks ago