Olimpiade Matematica Polacca 1984 — Round 3

Count functions on an n-element set whose (n-1)-th iterate is constant but (n-2)-th iterate is not.

Find the number of all real functions $f$ which map the sum of $n$ elements into the sum of their images, such that $f^{n-1}$ is a constant function and $f^{n-2}$ is not. Here $f^0(x)=x$ and $f^k=f\circ f^{k-1}$ for $k\ge 1$.

Topic: Algebra, Insiemi e funzioni, Combinatoria Metodo: Conteggio, Ricorsione Abilita: Astrazione, Conteggio sistematico, Lettura attenta Area: Algebra e Analisi, Combinatoria, Logica e Probabilita Fonte: apri PDF

Contare le funzioni su un insieme di n elementi la cui (n-1) -th iterate è costante ma (n-2) -th iterate non è.

Trova il numero di tutte le funzioni reali $f$ che mappano la somma degli elementi $n$ nella somma delle loro immagini, in modo che $f^{n-1}$ sia una funzione costante e $f^{n-2}$ non lo sia. Qui $f^0(x)=x$ e $f^k=f\circ f^{k-1}$ per $k\ge 1$.

src_pol_1984_r3__Q01

Prove a lower bound of n/2 for a sum of absolute partial-sums under any permutation of a special matrix.

Let $n$ be a positive integer. For all $i,j\in \{1,2,\dots ,n\}$ define $a_{j,i}=1$ if $j=i$ and $a_{j,i}=0$ otherwise. Also, for $i=n+1,\dots ,2n$ define $a_{j,i}=-\frac{1}{n}$. Prove that for any permutation $p$ of the set $\{1,2,\dots ,2n\}$ the following inequality holds: ${\sum }_{j=1}^n\left|{\sum }_{k=1}^n{a}_{j,p(k)}\right|\ge \frac{n}{2}.$

Topic: Algebra, Disuguaglianze, Combinatoria Metodo: Disuguaglianze, Casework, Estremalità Abilita: Manipolazione algebrica, Casework accurato, Astrazione Area: Algebra e Analisi, Combinatoria, Logica e Probabilita Fonte: apri PDF

Prove un limite inferiore di n/2 per una somma di somme parziali assolute sotto qualsiasi permutazione di una matrice speciale.

$n$ sia un numero intero positivo. Per tutti i $i,j\in \{1,2,\dots ,n\}$ definire $a_{j,i}=1$ se $j=i$ e $a_{j,i}=0$ altrimenti. Inoltre, per $i=n+1,\dots ,2n$ definire $a_{j,i}=-\frac{1}{n}$. Prove che per qualsiasi permutazione $p$ del set $\{1,2,\dots ,2n\}$ si verifica la seguente disuguaglianza: ${\sum }_{j=1}^n\left|{\sum }_{k=1}^n{a}_{j,p(k)}\right|\ge \frac{n}{2}.$

src_pol_1984_r3__Q02

Two concentric circles inscribed in and circumscribed about the section of a regular octahedron by a plane through its center; prove a ratio bound.

Let $W$ be a regular octahedron and $O$ be its center. In a plane $P$ containing $O$ circles $k_1(O,r_1)$ and $k_2(O,r_2)$ are chosen so that $k_1\subset P\cap W\subset k_2$. Prove that $\frac{r_1}{r_2}\le \frac{\sqrt{3}}{2}$.

Topic: Geometria solida, Geometria piana, Disuguaglianze Metodo: Estremalità, Casework, Coordinate Abilita: Ragionamento geometrico, Stima, Astrazione Area: Geometria, Algebra e Analisi Fonte: apri PDF

Due cerchi concentrici inseriti e circoscritti intorno alla sezione di un ottaedro regolare da un piano attraverso il suo centro; dimostrare un rapporto legato.

Che il $W$ sia un ottaedro regolare e il $O$ sia il suo centro. In un piano $P$ contenente $O$ si scelgono i cerchi $k_1(O,r_1)$ e $k_2(O,r_2)$ in modo tale che $k_1\subset P\cap W\subset k_2$. Dimostra che $\frac{r_1}{r_2}\le \frac{\sqrt{3}}{2}$.

src_pol_1984_r3__Q03

A coin tossed n times; partial sums with toss values 1 or 2; express the probability that the partial sums hit n recursively.

A coin is tossed $n$ times, and the outcome is written in the form $(a_1,a_2,\dots ,a_n)$, where $a_i=1$ or $2$ depending on whether the result of the $i$-th toss is the head or the tail, respectively. Set $b_j=a_1+a_2+\cdots +a_j$ for $j=1,2,\dots ,n$, and let $p(n)$ be the probability that the sequence $b_1,b_2,\dots ,b_n$ contains the number $n$. Express $p(n)$ in terms of $p(n-1)$ and $p(n-2)$.

Topic: Probabilità, Combinatoria Metodo: Ricorsione, Casework, Conteggio Abilita: Modellizzazione, Conteggio sistematico, Astrazione Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Una moneta lanciata n volte; somme parziali con valori di lancio 1 o 2; esprimere la probabilità che le somme parziali colpiscano n in modo ricorrente.

Una moneta viene lanciata $n$ volte, e il risultato è scritto nella forma $(a_1,a_2,\dots ,a_n)$, dove $a_i=1$ o $2$ a seconda che il risultato del tiro $i$-th sia la testa o la coda, rispettivamente. Impostare $b_j=a_1+a_2+\cdots +a_j$ per $j=1,2,\dots ,n$, e lasciare $p(n)$ la probabilità che la sequenza $b_1,b_2,\dots ,b_n$ contiene il numero $n$. Esprimere $p(n)$ in termini di $p(n-1)$ e $p(n-2)$.

src_pol_1984_r3__Q04

A regular hexagon of side 1 is covered by six unit disks; prove no vertex is covered by two or more disks.

A regular hexagon of side $1$ is covered by six unit disks. Prove that none of the vertices of the hexagon is covered by two (or more) disks.

Topic: Geometria piana, Combinatoria Metodo: Estremalità, Casework, Principio dei cassetti Abilita: Ragionamento geometrico, Stima, Casework accurato Area: Geometria, Combinatoria, Logica e Probabilita Fonte: apri PDF

Un esagono regolare del lato 1 è coperto da sei dischi unitari; dimostrare che nessun vertice è coperto da due o più dischi.

Un esagono regolare di lato $1$ è coperto da sei dischi unitari. Prova che nessuno dei vertici dell’esagono è coperto da due (o più) dischi.

src_pol_1984_r3__Q05

1025 cities pairwise connected by 10 airlines; prove some airline has a round trip of odd length.

Cities $P_1,\dots ,P_{1025}$ are connected to each other by airlines $A_1,\dots ,A_{10}$ so that for any two distinct cities $P_k$ and $P_m$ there is an airline offering a direct flight between them. Prove that one of the airlines can offer a round trip with an odd number of flights.

Topic: Combinatoria, Logica Metodo: Grafi, Colorazione, Estremalità, Principio dei cassetti Abilita: Astrazione, Modellizzazione, Conteggio sistematico Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

1025 città collegate in coppia da 10 compagnie aeree; dimostrare che alcune compagnie aeree hanno un viaggio di andata e ritorno di lunghezza strana.

Le città $P_1,\dots ,P_{1025}$ sono collegate tra loro da compagnie aeree $A_1,\dots ,A_{10}$ in modo che per due città distinte $P_k$ e $P_m$ esiste una compagnia aerea che offre un volo diretto tra di esse. Prova che una delle compagnie aeree può offrire un viaggio di andata e ritorno con un numero imparato di voli.

src_pol_1984_r3__Q06