IMO Shortlist 1999 problem C1
Kvaliteta:
Avg: 0,0Težina:
Avg: 6,0 Let
be an integer. A path from
to
in the
plane is a chain of consecutive unit moves either to the right (move denoted by
) or upwards (move denoted by
), all the moves being made inside the half-plane
. A step in a path is the occurence of two consecutive moves of the form
. Show that the number of paths from
to
that contain exactly
steps
is
![n \geq 1](/media/m/a/9/8/a982fcac3e2c9e0d94e965d6efb5a582.png)
![(0,0)](/media/m/3/e/4/3e48f4571311d9b0074aa083e1ebe311.png)
![(n,n)](/media/m/6/2/3/6233cbd5bea84837cb8cad96dc65ff05.png)
![xy](/media/m/5/9/6/596af52a0894be7f886bc10ba63d140f.png)
![E](/media/m/8/b/0/8b01e755d2253cb9a52f9e451d89ec11.png)
![N](/media/m/f/1/9/f19700f291b1f2255b011c11d686a4cd.png)
![x \geq y](/media/m/4/c/f/4cf15742197dfe4cb55aac6dfcd77ba2.png)
![EN](/media/m/8/a/7/8a738873fd9bb9b92a40601aa803337f.png)
![(0,0)](/media/m/3/e/4/3e48f4571311d9b0074aa083e1ebe311.png)
![(n,n)](/media/m/6/2/3/6233cbd5bea84837cb8cad96dc65ff05.png)
![s](/media/m/9/0/8/908014cbadb69e42261a56b450a375b9.png)
![(n \geq s \geq 1)](/media/m/f/0/a/f0a45ce55f9310382e67fe5569133649.png)
![\frac{1}{s} \binom{n-1}{s-1} \binom{n}{s-1}.](/media/m/e/8/a/e8aaef8007f7688c0b9a6f79fab6144b.png)
Izvor: Međunarodna matematička olimpijada, shortlist 1999