In the figure we see the paths connecting the square of a city (point P) with the school (point S). In the square there are k pupils starting to go to the school. They have the ability to move only to the right and up. If the pupils are free to choose any allowed path (in order to get to school), determine the minimum value of k so that in any case at least two pupils follow the same path.
https://cdn.artofproblemsolving.com/attachments/e/2/b5d6c6db5942cb706428cb63af3ca15590727f.png combinatoricsgridsquare gridpaths