Attachment 27457

count the number of paths from A to B ? which you can just gorightorup? (with inclusion and exclusion principle)

* plz write the solution for a foolish person : )

Printable View

- March 9th 2013, 10:24 AMmshouinclusion and exclusion principle
Attachment 27457

count the number of paths from A to B ? which you can just go**right**or**up**? (with inclusion and exclusion principle)

* plz write the solution for a foolish person : ) - March 9th 2013, 02:27 PMemakarovRe: inclusion and exclusion principle
This is not a question? It is a command? Therefore, no question mark is necessary? :)

Let's introduce a coordinate system with origin at A and the unit length equal to the grid size. Then A has coordinates (0, 0) and B has coordinates (8, 7).

There are two holes in the grid. A path goes through the first hole iff it goes through (3, 3). Let X be the set of such paths. A path goes through the second hole iff it goes through (5, 5) and (5, 6). Let Y be the set of such paths. You need to find |X ∪ Y| and subtract it from the number of paths from A to B in the grid without holes. By inclusion-exclusion principle, it is sufficient to find |X|, |Y| and |X ∩ Y|.