# 9 Cities Numbered 1 to 9

There are 9 cities numbered 1 to 9. From how many cities the flight can start so as to reach the city 8 either directly or indirectly such the path formed is divisible by 3.

#### anand3186 Profile Answers by anand3186

• Jul 17th, 2009

9 cities.
1 - 8 (1+8 = 9)
2-5-8(2+5+8=15)
3-4-8
4-(3 or 6)-8
5-2-8
6-(4 or 1)-8
7-8
8-2-8
9-1-8

#### m_manic Profile Answers by m_manic Questions by m_manic

• Dec 9th, 2009

It can strart from 8 cities. 1,2,3,4,5,6,7,9

#### rajkumar03939 Profile Answers by rajkumar03939

• Dec 19th, 2009

8+1

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

These are the ways that find to reach the 8 city in direct and indirect ways.

#### praveen_isu23 Profile Answers by praveen_isu23

• Mar 14th, 2010

7(7+1)/2+8,
(7*8)/2+8,
56/2+8,
28+8,
36

#### tibuhari Profile Answers by tibuhari

• Nov 24th, 2010

Assuming that you can't visit any city more than once and that I haven't missed any journeys the answer is 64961.

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.
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

#### SAIKIRAN

• Sep 17th, 2011

3 and 6 are the cities divisible by 3

#### Dipronil Dey

• Aug 16th, 2017

8*((7C1*1!)+(7C2*2!)+(7C3*3!)+(7C4*4!)+(7C5*5!)+(7C6*6!)+(7C7*7!))