PS - Combinatory

[Xbond]

Hi there,

Could you help me to understand and resolve this problem.
You can get the image in OG 11th (PS N°195 - page 178)

Pat will walk from intersection X to intersection Y along a route that is confined to the square grid of four streets and three avenues shown in the map above. How many routes from X to Y can Pat take that have the minimum possible length ?

a) 6

b) 8

c) 10

d) 14

e) 16


A prompt reply should be very appreciated

regards

[mike22629]

Not sure if I am interpretting question correctly, but this is what I think.

In order to make it in the minimum distance there are 4 different spots where a decision can be made.

Hence 2^4

Is answer 16?

[lilu]

This is a problem with permutations with repetition.
https://regentsprep.org/regents/math/permut/LpermRep.htm

Basically, the directions U-up and L-left --> UULLL can be arranged in 5!/2!*3! ways--> 10 ways because U is repeated twice and L is repeated three times.
It's similar to letter combinatorics in words with repeating letters (please see the link I've attached)

[lunarpower]

Basically, the directions U-up and L-left --> UULLL can be arranged in 5!/2!*3! ways--> 10 ways because U is repeated twice and L is repeated three times.

yes.

well done.

--

since ALL OF THE ANSWER CHOICES ARE SMALL NUMBERS, we can also attack this problem by just making a list of the possibilities. as with other solutions involving making lists, the only catch is that you have to ORGANIZE YOUR LIST according to some easily understood principle.

here's one such principle:
figure out the paths that go left, early. then move to the paths that go left at later times.

here are the paths that you'll find according to this principle:

l l l u u
l l u l u
l l u u l

l u l l u
l u l u l
l u u l l

u l l l u
u l l u l

u l u l l

u u l l l

... and then there were ten.

you could also trace out these paths visually, on the diagram, but of course i don't have the means to do that here.

it should be noted that this is the same list that you'd get by organizing a bunch of abstract U's and L's in alphabetical order.

[ghacker]

Assume This is 4X3 grid

so in order to go from X to Y one must go 4 blocks in the X direction and 3 blocks in the Y direction .All X blocks are similar and all Y blocks are similar

XXXXYYY

so total no of ways = 7!/4!*3!

So for a 3X2 block we have XXXYY = 5!/3!*2! =10