There are 9 cities numbered 1 to 9. From how many cities a flight
can start so as to reach the city 8 either directly or indirectly
such the path formed is divisible by 3
eg. 1368-Flights goes from 1 through 1-3-6-8 to 8.
May 15, 2009
Flight path puzzle
There are 9 cities numbered 1 to 9. From how many cities a flight
can start so as to reach the city 8 either directly or indirectly
such the path formed is divisible by 3
eg. 1368-Flights goes from 1 through 1-3-6-8 to 8.
Subscribe to:
Post Comments (Atom)
4 comments:
Assuming that you can't visit any city more than once and that I haven't missed any journeys the answer is 7673.
This consists of the journeys listed below. Only pathways where successive cities having a higher number are listed but these cities can obviously be visited in any order as long as City 8 is the last; eg from the four-city group the path 1-2-4-8 represents these trips also: 1-4-2-8, 2-1-4-8, 2-4-1-8, 4-1-2-8, and 4-2-1-8 meaning that, for the four-city group, the number of paths listed must be multiplied by 6 to give the actual total.
3 two-city trips (total=3)
1-8
4-8
7-8
7 three-city trips, each of which can be travelled 2*1=2 ways (total=7*2=14)
1-3-8
1-6-8
2-5-8
3-4-8
3-7-8
4-6-8
6-7-8
8 four-city trips, each of which can be travelled 3*2*1=6 ways (total=8*6=48)
1-2-4-8
1-2-7-8
1-3-6-8
1-4-5-8
2-3-5-8
2-4-7-8
3-4-6-8
4-5-7-8
12 five-city trips, each of which can be travelled 4*3*2*1=24 ways (total=12*24=288)
1-2-3-4-8
1-2-3-7-8
1-2-4-6-8
1-3-4-5-8
1-3-5-7-8
1-4-5-6-8
1-5-6-7-8
2-3-4-7-8
2-3-5-6-8
2-4-6-7-8
3-4-5-7-8
4-5-6-7-8
7 six-city trips, each of which can be travelled 5*4*3*2*1=120 ways (total=7*120=840)
1-2-3-4-6-8
1-2-3-6-7-8
1-2-4-5-7-8
1-3-4-5-6-8
1-3-5-6-7-8
2-3-4-6-7-8
3-4-5-6-7-8
2 seven-city trips, each of which can be travelled 6*5*4*3*2*1=720 ways (total=2*720=1440)
1-2-3-4-5-7-8
1-2-4-5-6-7-8
1 eight-city trip, each of which can be travelled 7*6*5*4*3*2*1=5040 ways (total=1*5040=5040)
1-2-3-4-5-6-7-8
The question is: "From how many cities a flight can start"
I mean the answer is: 8 cities (1, 2, 3, 4, 5, 6, 7 and 9... you can easily discover a route starting on all of them)
About how many routes, in the answer above all routes with city "9" are missing, and another three ones.
two-cities: (3)
1-8
4-8
7-8
three-cities: (10 * 2! = 20)
1-3-8
1-6-8
1-9-8*
2-5-8
3-4-8
3-7-8
4-6-8
4-9-8*
6-7-8
7-9-8*
four-cities: (15 * 3! = 90)
1-2-4-8
1-2-7-8
1-3-6-8
1-3-9-8*
1-4-5-8
1-5-7-8**
1-6-9-8*
2-3-5-8
2-4-7-8
2-5-6-8**
2-5-9-8*
3-4-6-8
3-4-9-8*
4-5-7-8
4-6-9-8*
five-cities: (22 * 4! = 528)
1-2-3-4-8
1-2-3-7-8
1-2-4-6-8
1-2-4-9-8*
1-2-6-7-8**
1-2-7-9-8*
1-3-4-5-8
1-3-5-7-8
1-3-6-9-8*
1-4-5-6-8
1-4-5-9-8*
1-5-6-7-8
1-5-7-9-8*
2-3-4-7-8
2-3-5-6-8
2-3-5-9-8*
2-4-6-7-8
2-4-7-9-8*
3-4-5-7-8
3-4-6-9-8*
4-5-6-7-8
4-5-7-9-8*
six-cities: (20 * 5! = 2400)
1-2-3-4-6-8
1-2-3-4-9-8*
1-2-3-6-7-8
1-2-3-7-9-8*
1-2-4-5-7-8
1-2-4-6-9-8*
1-2-6-7-9-8*
1-3-4-5-6-8
1-3-4-5-9-8*
1-3-5-6-7-8
1-3-5-7-9-8*
1-4-5-6-9-8*
1-5-6-7-9-8*
2-3-4-6-7-8
2-3-4-7-9-8*
2-3-5-6-9-8*
2-4-6-7-9-8*
3-4-5-6-7-8
3-4-5-7-9-8*
4-5-6-7-9-8*
seven-cities: (9 * 6! = 6480)
1-2-3-4-5-7-8
1-2-3-4-6-9-8*
1-2-3-6-7-9-8*
1-2-4-5-6-7-8
1-2-4-5-7-9-8*
1-3-4-5-6-9-8*
1-3-5-6-7-9-8*
2-3-4-6-7-9-8*
3-4-5-6-7-9-8*
eight-cities: (3 * 7! = 15120)
1-2-3-4-5-6-7-8
1-2-3-4-5-7-9-8*
1-2-4-5-6-7-9-8*
nine-cities: (1 * 8! = 40320)
1-2-3-4-5-6-7-9-8*
TOTAL = 64961
@danvdias
Yup, you're right. Ending on City 8 caused me to forget that there was a City 9.
Nice one.
yep ... its brill
Post a Comment