"Taxi distance" with three axes of movement -- a 7 by 7 by 7 situation
Image a building with stairways at the intersections at every one of seven corridors and every one of seven hallways on each floor and with seven floors. The corridors are vertically placed with respect to the other corridors and the same for the hallways. Corridors and hallways are perpendicular to each other.
The problem's question: In particular, in such a building as described above, how non-backtracking routes between opposite corners of the building?
Assume that you start on the first floor in the south west corner bottom floor of the building and are traveling to the north east corner top floor of the building via the corridors, hallways and stairways, how many distinct routes without backtracking (i. e., never traveling to the west, south or down) are there?
I verified that I could work this problem on a US$1 scientific calculator without writing down any intermediate results in just a few minutes. I could. This particular calculator can do 10 digit arithmetic.
The answer is 17153136.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The changes in corridor, hallway and floor are each six for a total change of eighteen. This question is how many combinations of eighteen things can be selected into three bins (changes of corridor, hallway or floor) containing six changes each. This is 6 ! 6 ! 6 ! 1 8 ! = ( 1 8 ; 6 , 6 , 6 ) ⇒ 1 7 1 5 3 1 3 6 .
This can get out of hand quickly: a ten-dimensional version with a delta of ten for each dimension gives this small answer: two hundred thirty-five novemvigintillion, seven hundred seven octovigintillion, four hundred fifty-eight septenvigintillion, nine hundred thirty-nine sexvigintillion, three hundred four quinvigintillion, three hundred eighty-nine quattuorvigintillion, six hundred forty trevigintillion, nine hundred thirty-one duovigintillion, nine hundred sixty-eight unvigintillion, three hundred sixteen vigintillion, one hundred thirty novemdecillion, two hundred nine octodecillion, one hundred twenty-eight septendecillion, nine hundred seventy-nine sexdecillion, six hundred twenty-four quindecillion, one hundred ninety-six quattuordecillion, six hundred fifty-eight tredecillion, five hundred seventy-eight duodecillion, five hundred seventy-four undecillion, one hundred forty-one decillion, forty-six nonillion, four hundred ninety-seven octillion, three hundred forty-nine septillion, seven hundred fourteen sextillion, five quintillion, three hundred forty-nine quadrillion, seven hundred six trillion, six hundred eighty-nine billion, one hundred sixty-seven million, three hundred sixty thousand, using American style billions.