[IMO13 - P6] La grande bellezza

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
EvaristeG
Site Admin
Messaggi: 4617
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

[IMO13 - P6] La grande bellezza

Messaggio da EvaristeG » 02 ago 2013, 12:30

Sia $n\geq 3$ un intero e consideriamo una circonferenza con $n+1$ punti segnati su di essa, nei vertici di un poligono regolare. Ad ogni punto associamo un numero tra $0,1,\ldots, n$, usando ogni numero una volta sola; due tali poligoni numerati sono da considerarsi equivalenti se si possono ottenere l'uno dall'altro per rotazione.

Un poligono numerato si dice bello se per ogni quattro numeri $0\leq a<b<c<d\leq n$ tali che $a+d=b+c$ la corda che congiunge i vertici numerati con $a$ e $d$ non interseca la corda che congiunge i vertici numerati con $b$ e $c$.

Sia $M$ il numero dei poligoni numerati belli (a meno di rotazioni, ovviamente) e sia $N$ il numero di coppie ordinate $(x,y)$ di numeri interi positivi tali che $x+y\leq n$ e $\textrm{MCD}(x,y)=1$. Dimostrare che
$$M=N+1\;.$$

Rispondi