Concours Général des Lycées 2019 — Matematica

Remarkable families of functions on [0,+inf): show the set of polynomial functions is contained in / characterized by sets closed under sum, composition, difference and product (properties P1-P6).

We denote by $\mathcal{P}$ the set of functions defined on $[0,+\infty [$ with values in $[0,+\infty [$. For $f$ and $g$ in $\mathcal{P}$, one defines the function $h=f\circ g$ by setting, for every real number $x\ge 0$: $h(x)=f(g(x)).$ One considers $u$ and $v$, two functions of $\mathcal{P}$ defined, for every real number $x\ge 0$, by: $u(x)=e^x-1,v(x)=\ln (x+1).$

The function $f$ is called a $\text{polynomial function}$ of $\mathcal{P}$ if there exist an integer $d\ge 0$ and real numbers $a_0,a_1,\dots ,a_d$ greater than or equal to $0$ such that, for every real number $x\ge 0$: $f(x)=a_d{x}^d+a_{d-1}{x}^{d-1}+\cdots +a_{1}x+a_0.$ The real numbers $a_0,a_1,\dots ,a_d$ are called the coefficients of the polynomial function $f$.

Let $\mathcal{F}$ be a set of functions of $\mathcal{P}$. One considers the following properties:

$\text{(P1)}$ $\mathcal{F}$ contains $u$ and $v$. $\text{(P2)}$ $\mathcal{F}$ contains all bounded constant functions. $\text{(P3)}$ If $f$ and $g$ belong to $\mathcal{F}$, then $f+g$ belongs to $\mathcal{F}$. $\text{(P4)}$ If $f$ and $g$ belong to $\mathcal{F}$, then $f\circ g$ belongs to $\mathcal{F}$. $\text{(P5)}$ If $f$ and $g$ belong to $\mathcal{F}$ with $f\ge g$, then $f-g$ belongs to $\mathcal{F}$. $\text{(P6)}$ If $f$ and $g$ belong to $\mathcal{F}$, then $f\times g$ belongs to $\mathcal{F}$.

$\text{1.}$ Let $\mathcal{T}$ be the set of functions of $\mathcal{P}$ having the properties $\text{(P1)}$, $\text{(P2)}$, $\text{(P3)}$, $\text{(P4)}$ and $\text{(P5)}$. $\text{a.}$ Let $i$ be the function defined, for every real number $x\ge 0$, by $i(x)=x$. Show that $i$ belongs to $\mathcal{T}$. $\text{b.}$ Let $p$ be the function defined, for every real number $x\ge 0$, by $p(x)=2x^2-3x+4$. Show that $p$ belongs to $\mathcal{T}$. $\text{c.}$ Let $f$ be a polynomial function of $\mathcal{P}$. Show that $f$ belongs to $\mathcal{T}$. $\text{d.}$ Is the function $\exp$ always in $\mathcal{T}$?

$\text{2.}$ Let $\mathcal{F}$ be a set of functions of $\mathcal{P}$ which has the properties $\text{(P1)}$, $\text{(P2)}$, $\text{(P3)}$, $\text{(P4)}$ and $\text{(P5)}$. One does not suppose here that $\mathcal{F}$ has property $\text{(P6)}$. Is the result of the previous question still valid?

$\text{3.}$ Let $\mathcal{F}$ be a set of functions of $\mathcal{P}$ which has the properties $\text{(P1)}$, $\text{(P2)}$, $\text{(P4)}$, $\text{(P5)}$ and $\text{(P6)}$. One does not suppose here that $\mathcal{F}$ has property $\text{(P3)}$.

$\text{a.}$ Let $a$ be a natural integer. One sets, for every real number $x\ge 0$, the function defined by: $Q_a(x)=(x+1{)}^a-1.$ Show that $Q_a\in \mathcal{F}$. $\text{b.}$ Let $a$ be a natural integer. Demonstrate that there exist integers $a_1,\dots ,a_d$ greater than or equal to $0$ such that: $(x+1{)}^a=a_d{x}^d+a_{d-1}{x}^{d-1}+\cdots +a_{1}x+1.$ Being given a real number $x\ge 0$, one introduces a random variable $X$ following the binomial law of parameters $d$ and $\frac{x}{x+1}$. $\text{c.}$ Let $f$ be a polynomial function of $\mathcal{P}$ such that $f(0)=0$. Show that there exist a real number $c\ge 0$ and a natural integer $d$ such that the function $c(x+x^2+\cdots +x^d)-f(x)$ be a polynomial function whose coefficients are all positive or zero. $\text{d.}$ Deduce that if $f$ is a polynomial function of $\mathcal{P}$ such that $f(0)=0$, then $f$ belongs to $\mathcal{F}$. $\text{e.}$ Let $f$ be a function of $\mathcal{P}$. $\bullet$ One says $f$ is $\text{segmentary}$ if it verifies the property: for every real number $a>0$ there exists a real number $b>0$ such that, for all $x$ verifying $0\le x\le a$, one has $0\le f(x)\le b$. $\bullet$ One says $f$ is $\text{bounded}$ if it verifies the property: there exists a real number $b>0$ such that, for every real number $x\ge 0$, one has $0\le f(x)\le b$. One now denotes by $\mathcal{S}$ the set of segmentary functions and $\mathcal{B}$ the set of bounded functions. $\text{i.}$ Let $f$ be a function of $\mathcal{B}$. Show that $f$ is segmentary. Is the converse true? $\text{ii.}$ Show that $\mathcal{S}$ satisfies the properties $\text{(P1)}$ to $\text{(P6)}$. $\text{iii.}$ Show that $\mathcal{B}$ satisfies the properties $\text{(P1)}$, $\text{(P2)}$, $\text{(P4)}$, $\text{(P5)}$ and $\text{(P6)}$ but does not satisfy property $\text{(P3)}$. $\text{f.}$ Is a polynomial function of $\mathcal{P}$ necessarily in $\mathcal{F}$?

Topic: Equazioni funzionali, Insiemi e funzioni, Algebra, Probabilità Metodo: Induzione, Casework, Fattorizzazione Abilita: Astrazione, Lettura attenta, Manipolazione algebrica Area: Algebra e Analisi, Combinatoria, Logica e Probabilita Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

*Notabili famiglie di funzioni su [0,+inf): mostrare che l’insieme di funzioni polinomiche è contenuto in / caratterizzato da gruppi chiusi sotto somma, composizione, differenza e prodotto (proprietà P1-P6). *

Indichiamo con $\mathcal{P}$ l’insieme di funzioni definite su $[0,+\infty [$ con valori in $[0,+\infty [$. Per $f$ e $g$ in $\mathcal{P}$, si definisce la funzione $h=f\circ g$ impostando, per ogni numero reale $x\ge 0$: $h(x)=f(g(x)).$ Si considera $u$ e $v$, due funzioni di $\mathcal{P}$ definite, per ogni numero reale $x\ge 0$, da: $u(x)=e^x-1,v(x)=\ln (x+1).$

La funzione $f$ è chiamata $\text{polynomial function}$ di $\mathcal{P}$ se esiste un intero $d\ge 0$ e numeri reali $a_0,a_1,\dots ,a_d$ superiori o uguali a $0$ in modo tale che, per ogni numero reale $x\ge 0$: $f(x)=a_d{x}^d+a_{d-1}{x}^{d-1}+\cdots +a_{1}x+a_0.$ I numeri reali $a_0,a_1,\dots ,a_d$ sono chiamati i coefficienti della funzione polinomica $f$.

Let $\mathcal{F}$ essere un insieme di funzioni di $\mathcal{P}$. Si considerano le seguenti proprietà:

$\text{(P1)}$ $\mathcal{F}$ contiene $u$ e $v$. $\text{(P2)}$ $\mathcal{F}$ contiene tutte le funzioni costanti limitate. $\text{(P3)}$ Se $f$ e $g$ appartengono a $\mathcal{F}$, allora $f+g$ appartiene a $\mathcal{F}$. Se $f$ e $g$ appartengono a $\mathcal{F}$, allora $f\circ g$ appartiene a $\mathcal{F}$. $\text{(P5)}$ Se $f$ e $g$ appartengono a $\mathcal{F}$ con $f\ge g$, allora $f-g$ appartiene a $\mathcal{F}$. $\text{(P6)}$ Se $f$ e $g$ appartengono a $\mathcal{F}$, allora $f\times g$ appartiene a $\mathcal{F}$.

$\text{1.}$ $\mathcal{T}$ sia l’insieme di funzioni di $\mathcal{P}$ che hanno le proprietà $\text{(P1)}$, $\text{(P2)}$, $\text{(P3)}$, $\text{(P4)}$ e $\text{(P5)}$. $\text{a.}$ $i$ sia la funzione definita, per ogni numero reale $x\ge 0$, da $i(x)=x$. Indicare che $i$ appartiene a $\mathcal{T}$. $\text{b.}$ $p$ sia la funzione definita, per ogni numero reale $x\ge 0$, da $p(x)=2x^2-3x+4$. Indicare che $p$ appartiene a $\mathcal{T}$. $\text{c.}$ $f$ sia una funzione polinomial di $\mathcal{P}$. Indicare che $f$ appartiene a $\mathcal{T}$. $\text{d.}$ La funzione $\exp$ è sempre in $\mathcal{T}$?

$\text{2.}$ $\mathcal{F}$ sia un insieme di funzioni di $\mathcal{P}$ che ha le proprietà $\text{(P1)}$, $\text{(P2)}$, $\text{(P3)}$, $\text{(P4)}$ e $\text{(P5)}$. Qui non si suppone che $\mathcal{F}$ abbia la proprietà $\text{(P6)}$. Il risultato della domanda precedente è ancora valido?

$\text{3.}$ $\mathcal{F}$ sia un insieme di funzioni di $\mathcal{P}$ che ha le proprietà $\text{(P1)}$, $\text{(P2)}$, $\text{(P4)}$, $\text{(P5)}$ e $\text{(P6)}$. Qui non si suppone che $\mathcal{F}$ abbia la proprietà $\text{(P3)}$.

$\text{a.}$ $a$ sia un intero naturale. Un set, per ogni numero reale $x\ge 0$, la funzione definita da: $Q_a(x)=(x+1{)}^a-1.$ Mostra che $Q_a\in \mathcal{F}$. $\text{b.}$ $a$ sia un intero naturale. Dimostrare che esistono integri $a_1,\dots ,a_d$ superiori o uguali a $0$ in modo tale che: $(x+1{)}^a=a_d{x}^d+a_{d-1}{x}^{d-1}+\cdots +a_{1}x+1.$ Dato un numero reale $x\ge 0$, si introduce una variabile casuale $X$ seguendo la legge binomica dei parametri $d$ e $\frac{x}{x+1}$. $\text{c.}$ $f$ sia una funzione polinomial di $\mathcal{P}$ tale che $f(0)=0$. Mostrare che esiste un numero reale $c\ge 0$ e un intero naturale $d$ in modo tale che la funzione $c(x+x^2+\cdots +x^d)-f(x)$ sia una funzione polinomica i cui coefficienti sono tutti positivi o zero. $\text{d.}$ Deduce che se $f$ è una funzione polinomial di $\mathcal{P}$ tale che $f(0)=0$, allora $f$ appartiene a $\mathcal{F}$. $\text{e.}$ $f$ deve essere una funzione di $\mathcal{P}$. $\bullet$ Si dice $f$ è $\text{segmentary}$ se verifica la proprietà: per ogni numero reale $a>0$ esiste un numero reale $b>0$ tale che, per tutte le $x$ che verificano $0\le x\le a$, si ha $0\le f(x)\le b$. $\bullet$ Si dice $f$ è $\text{bounded}$ se verifica la proprietà: esiste un numero reale $b>0$ tale che, per ogni numero reale $x\ge 0$, si ha $0\le f(x)\le b$. Ora uno denota con $\mathcal{S}$ l’insieme delle funzioni segmentarie e $\mathcal{B}$ l’insieme delle funzioni limitate. $\text{i.}$ $f$ deve essere una funzione di $\mathcal{B}$. Indicare che $f$ è segmentato. È vero il contrario? $\text{ii.}$ Indicare che $\mathcal{S}$ soddisfa le proprietà $\text{(P1)}$ a $\text{(P6)}$. Indicare che $\mathcal{B}$ soddisfa le proprietà $\text{(P1)}$, $\text{(P2)}$, $\text{(P4)}$, $\text{(P5)}$ e $\text{(P6)}$, ma non soddisfa la proprietà $\text{(P3)}$. $\text{f.}$ Una funzione polinomial di $\mathcal{P}$ è necessariamente in $\mathcal{F}$?

src_cgen_2019__Q01

Jovial numbers: integers p that admit a strictly increasing sequence of integers >=2 ending at p whose reciprocals sum to 1; examples, two integer sequences, and an optimal upper bound for jovial numbers of fixed order proved by induction.

A natural integer $p\ge 2$ is said to be $\text{jovial of order }k$ if there exist integers $a_1,\dots ,a_k$ such that: $2\le a_1<a_2<\cdots <a_k,a_k=p\text{and}\frac{1}{a_1}+\cdots +\frac{1}{a_k}=1.$ Thus, $12$ is jovial of order $4$ because $\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{12}=1$. The integer $p\ge 2$ is said to be $\text{jovial}$ if there exists an integer $n\ge 1$ such that $p$ is jovial of order $n$.

$\text{2.1 Some examples}$ $\text{1.}$ Show that if $p$ is jovial of order $n$, then $n\ge 1$. $\text{2.}$ Show that there is no jovial integer of order $1$. Show that $2$ and $4$ are not jovial. $\text{3.}$ Show that no prime integer is jovial. $\text{4.}$ What is the smallest jovial integer? $\text{5.}$ Determine all the jovial integers of order $3$. $\text{6.}$ Let $p$ be an integer. Show that $2p$ and $p(p+1)$ are jovial. $\text{7.}$ Show that whether $p$ is jovial does not depend on the order.

$\text{2.2 Two integer sequences}$ One defines the sequences $(u_n{)}_{n\ge 0}$ and $(v_n{)}_{n\ge 0}$ by $u_1=1$ and, for every integer $n\ge 1$, $u_{n+1}=u_n(1+u_n).$ $\text{1.}$ Show, for every $n\ge 3$, that $u_n$ is an odd jovial integer of order $n$. $\text{2.}$ Show, for every integer $n\ge 1$, that $v_{n+1}=v_1{v}_2\cdots v_n+1$.

$\text{2.3 An optimal upper bound for jovial numbers of fixed order}$ Let $a$ be a non-null natural integer. One denotes by ${\mathcal{H}}_a$ the following property: if $x_1,\dots ,x_n$ are strictly positive integers, and $b$ a strictly positive number, such that $x_1<x_2<\cdots <x_n\le a\text{and}\frac{1}{x_1}+\cdots +\frac{1}{x_n}+\frac{1}{a}=1,$ then $a+1\le v_{n+1}$ and $x_1{x}_2\cdots x_n\le v_1{v}_2\cdots v_{n+1}$. One wishes to demonstrate by recurrence that ${\mathcal{H}}_a$ is true for every integer $n\ge 1$. $\text{1.}$ Demonstrate that the property ${\mathcal{H}}_1$ is true.

In the following questions, one considers an integer $n\ge 2$, one supposes the property ${\mathcal{H}}_{a-1}$ is true. One considers the strictly positive integers $x_1,\dots ,x_n$ and a strictly positive rational number $a$ such that: $x_1<x_2<\cdots <x_n\le a\text{and}\frac{1}{x_1}+\cdots +\frac{1}{x_n}+\frac{1}{a}=1.$ $\text{2.}$ Show that $x_1\ge 2$ and that $a<x_1{x}_2\cdots x_n$. $\text{3.}$ One supposes in this question that $\frac{1}{x_1}+\cdots +\frac{1}{x_{n-1}}+\frac{1}{q}=1$ and that $x_n\ge x_{n-1}$. $\text{a.}$ Show that there exists a strictly positive integer $q$ such that: $\frac{1}{x_1}+\cdots +\frac{1}{x_{n-1}}+\frac{1}{q}=1.$ $\text{b.}$ Show that $x_n-1\le q$. $\text{c.}$ Deduce that $q+1\le v_n$ and then that $x_1\cdots x_n\le v_1{v}_2\cdots v_n{x}_n$. $\text{d.}$ Show that $a+1\le v_{n+1}$ and $x_1\cdots x_n\le v_1{v}_2\cdots v_{n+1}$. $\text{4.}$ One supposes in this question that $\frac{1}{x_1}+\cdots +\frac{1}{x_{n-1}}+\frac{1}{x_n}<1$. $\text{a.}$ Show that $x_n\ge a$. $\text{b.}$ Show that there exist two unique strictly positive rational numbers $r$ and $t$ such that: $\frac{1}{x_n}+\frac{1}{x_n-1}+\frac{1}{x_n-2}+r=1\text{and}\frac{1}{x_1}+\cdots +\frac{1}{x_{n-2}}+\frac{1}{t}=1.$ $\text{c.}$ Show that $r=x_n+1+\frac{x_n-2}{x_n^2-2x_n+2}$ and then that $(x_n-2)(r+1)\ge x_n^2$. $\text{d.}$ Show that $t\ge r\ge x_n$. $\text{e.}$ Deduce that $a+1\le v_{n+1}$ and $x_1\cdots x_n\le v_1{v}_2\cdots v_{n+1}$. $\text{5.}$ One supposes in this question that $\frac{1}{x_1}+\cdots +\frac{1}{x_{n-1}}<1$. $\text{a.}$ Show that there exists a strictly positive rational number $b$ such that: $\frac{1}{x_1}+\cdots +\frac{1}{x_{n-1}}+\frac{1}{b}=1.$ $\text{b.}$ Show that $(x_n-1)(b+1)\ge x_n(a+1)$. $\text{6.}$ Deduce that the proposition ${\mathcal{H}}_a$ is true. $\text{Hint: In the case where }\frac{1}{x_1}+\cdots +\frac{1}{x_{n-1}}+\frac{1}{x_n}<1,\text{ one may try to replace }{x}_n\text{ by }{x}_n-1\text{ and }a\text{ by }b.$ $\text{7.}$ Show, for every integer $n\ge 3$, that $u_n$ is the largest jovial integer of order $n$.

Topic: Teoria dei Numeri, Algebra, Combinatoria Metodo: Induzione, Estremalità, Ricorsione, Fattorizzazione Abilita: Manipolazione algebrica, Lettura attenta, Riconoscimento di pattern Area: Aritmetica e Teoria dei Numeri, Algebra e Analisi, Combinatoria, Logica e Probabilita Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

Nomeri interi joviali: numeri interi p che ammette una sequenza di numeri interi >=2 che finiscono a p e la cui reciprocità somma a 1; esempi, due sequenze di numeri interi e un limite superiore ottimale per i numeri interi joviali di ordine fisso dimostrato da induzione.

Si dice che un intero naturale $p\ge 2$ sia $\text{jovial of order }k$ se esistono interi $a_1,\dots ,a_k$ tali che: $2\le a_1<a_2<\cdots <a_k,a_k=p\text{and}\frac{1}{a_1}+\cdots +\frac{1}{a_k}=1.$ Quindi, $12$ è giovial dell’ordine $4$ perché $\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{12}=1$. Si dice che il numero intero $p\ge 2$ sia $\text{jovial}$ se esiste un numero intero $n\ge 1$ tale che $p$ sia giovial dell’ordine $n$.

$\text{2.1 Some examples}$ $\text{1.}$ Indicare che se $p$ è di ordine $n$, allora $n\ge 1$. $\text{2.}$ Indicare che non esiste un intero giovial dell’ordine $1$. Indicare che $2$ e $4$ non sono gioviali. $\text{3.}$ Indicare che nessun numero intero primo è giovial. $\text{4.}$ Qual è il più piccolo intero giovial? $\text{5.}$ Determinare tutti gli integri joviali dell’ordine $3$. $\text{6.}$ $p$ sia un numero intero. Indicare che $2p$ e $p(p+1)$ sono gioviali. $\text{7.}$ Indicare che l’esistenza di $p$ non dipende dall’ordine.

$\text{2.2 Two integer sequences}$ Si definiscono le sequenze $(u_n{)}_{n\ge 0}$ e $(v_n{)}_{n\ge 0}$ da $u_1=1$ e, per ogni numero intero $n\ge 1$, $u_{n+1}=u_n(1+u_n).$ $\text{1.}$ Mostra, per ogni $n\ge 3$, che $u_n$ è un numero intero giovial pari dell’ordine $n$. $\text{2.}$ Indicare, per ogni numero intero $n\ge 1$, che $v_{n+1}=v_1{v}_2\cdots v_n+1$.

$\text{2.3 An optimal upper bound for jovial numbers of fixed order}$ $a$ sia un intero naturale non-zero. Una denota con ${\mathcal{H}}_a$ la seguente proprietà: se $x_1,\dots ,x_n$ sono numeri interi rigorosamente positivi, e $b$ un numero rigorosamente positivo, tale che $x_1<x_2<\cdots <x_n\le a\text{and}\frac{1}{x_1}+\cdots +\frac{1}{x_n}+\frac{1}{a}=1,$ allora $a+1\le v_{n+1}$ e $x_1{x}_2\cdots x_n\le v_1{v}_2\cdots v_{n+1}$. Si desidera dimostrare con ricorrenza che ${\mathcal{H}}_a$ è vero per ogni numero intero $n\ge 1$. $\text{1.}$ Dimostra che la proprietà ${\mathcal{H}}_1$ è vera.

Nelle seguenti domande, si considera un intero $n\ge 2$, si suppone che la proprietà ${\mathcal{H}}_{a-1}$ sia vera. Si considerano i numeri interi strettamente positivi $x_1,\dots ,x_n$ e un numero razionale strettamente positivo $a$ in modo tale che: $x_1<x_2<\cdots <x_n\le a\text{and}\frac{1}{x_1}+\cdots +\frac{1}{x_n}+\frac{1}{a}=1.$ $\text{2.}$ Mostri che $x_1\ge 2$ e che $a<x_1{x}_2\cdots x_n$. In questa domanda si suppone che $\frac{1}{x_1}+\cdots +\frac{1}{x_{n-1}}+\frac{1}{q}=1$ e $x_n\ge x_{n-1}$. $\text{a.}$ Mostra che esiste un intero rigorosamente positivo $q$ tale che: $\frac{1}{x_1}+\cdots +\frac{1}{x_{n-1}}+\frac{1}{q}=1.$ $\text{b.}$ Mostra che $x_n-1\le q$. $\text{c.}$ Deduci quel $q+1\le v_n$ e poi quel $x_1\cdots x_n\le v_1{v}_2\cdots v_n{x}_n$. $\text{d.}$ Indicare che $a+1\le v_{n+1}$ e $x_1\cdots x_n\le v_1{v}_2\cdots v_{n+1}$. In questa domanda si suppone che $\frac{1}{x_1}+\cdots +\frac{1}{x_{n-1}}+\frac{1}{x_n}<1$. $\text{a.}$ Mostra che $x_n\ge a$. $\text{b.}$ Mostra che esistono due numeri razionali unici strettamente positivi $r$ e $t$ in modo tale che: $\frac{1}{x_n}+\frac{1}{x_n-1}+\frac{1}{x_n-2}+r=1\text{and}\frac{1}{x_1}+\cdots +\frac{1}{x_{n-2}}+\frac{1}{t}=1.$ $\text{c.}$ Mostra che $r=x_n+1+\frac{x_n-2}{x_n^2-2x_n+2}$ e quindi che $(x_n-2)(r+1)\ge x_n^2$. $\text{d.}$ Mostra che $t\ge r\ge x_n$. $\text{e.}$ Deduce che $a+1\le v_{n+1}$ e $x_1\cdots x_n\le v_1{v}_2\cdots v_{n+1}$. In questa domanda si suppone che $\frac{1}{x_1}+\cdots +\frac{1}{x_{n-1}}<1$. Indicare che esiste un numero razionale rigorosamente positivo $b$ tale che: $\frac{1}{x_1}+\cdots +\frac{1}{x_{n-1}}+\frac{1}{b}=1.$ $\text{b.}$ Indicare che $(x_n-1)(b+1)\ge x_n(a+1)$. $\text{6.}$ Deduce che la proposizione ${\mathcal{H}}_a$ sia vera. $\text{Hint: In the case where }\frac{1}{x_1}+\cdots +\frac{1}{x_{n-1}}+\frac{1}{x_n}<1,\text{ one may try to replace }{x}_n\text{ by }{x}_n-1\text{ and }a\text{ by }b.$ $\text{7.}$ Indicare, per ogni intero $n\ge 3$, che $u_n$ è il più grande intero giovial dell’ordine $n$.

src_cgen_2019__Q02

More than one chance in two for everyone: non-transitive dice and urns; compute and compare winning probabilities, analyze a choosing game, use the Fibonacci sequence and prove a non-transitive distribution exists for every n by induction.

$\text{3.1 Dice and urns}$ $\text{1.}$ In this question, one supposes that one has three urns $A$, $B$ and $C$ that contain each tokens indistinguishable by touch. The tokens of $A$ bear the numbers $11$, $6$, $10$, $3$ and $1$; those of $B$ bear the numbers $9$, $8$, $7$, $2$ and $5$; those of $C$ bear the numbers $11$, $5$, $4$, $3$ and $4$. One draws independently one token from each of the urns, one denotes respectively by $X_A$, $X_B$ and $X_C$ the numbers of the tokens drawn in $A$, $B$ and $C$. $\text{a.}$ One supposes here that the three urns contain each five tokens numbered such as above. Calculate the three probabilities $\mathbb{P}(X_A>X_B)$, $\mathbb{P}(X_B>X_C)$ and $\mathbb{P}(X_C>X_A)$. $\text{b.}$ Claire and Paul play at the following game: one of them begins by choosing a die, then the other chooses one of the two remaining dice that she contests. They each throw their die and the one who obtains the larger number wins. Does Claire have an interest in choosing her die before Paul or in letting him choose first? $\text{c.}$ Finally, it is decided that it is Paul who chooses first. Which die or dice does he have an interest in choosing? $\text{d.}$ Claire and Paul then decide to modify the rules. One of them chooses one of the three dice. Then the other takes die $D_2$ first. Which die does Claire have an interest in choosing, and in letting choose first?

$\text{2.}$ In this question, one supposes that one has three balanced six-faced dice $D_1$, $D_2$ and $D_3$, where the faces of $D_1$ bear the numbers $0$, $0$, $4$, $4$, $4$, $4$; those of $D_2$ bear the numbers $3$, $3$, $3$, $3$, $3$, $3$; and those of $D_3$ bear the numbers $6$, $6$, $2$, $2$, $2$, $2$. $\text{a.}$ One throws independently each of the three dice and one denotes respectively by $X_1$, $X_2$ and $X_3$ the numbers indicated by the upper face of the dice $D_1$, $D_2$ and $D_3$. Calculate the three probabilities $\mathbb{P}(X_1>X_2)$, $\mathbb{P}(X_2>X_3)$ and $\mathbb{P}(X_3>X_1)$. $\text{b.}$ Claire and Paul play at the following game: one of them begins by choosing a die, then the other chooses one of the two remaining dice. They each throw their die and the one who obtains the larger number wins. Does Claire have an interest in choosing her die before Paul or in letting him choose first? $\text{c.}$ Finally, it is decided that it is Paul who chooses first. Which die or dice does he have an interest in choosing? $\text{d.}$ Claire and Paul then decide to modify the rules: one of them chooses one of the three dice, then the other takes die $D_2$. Which die does Claire have an interest in choosing?

$\text{3.2 The Fibonacci sequence and the urns}$ The Fibonacci sequence $(F_n{)}_{n\ge 0}$ is defined by $F_0=0$, $F_1=1$ and, for every integer $n\ge 0$, $F_{n+2}=F_{n+1}+F_n.$ $\text{1.}$ Show, for every integer $n\ge 3$, that $\sqrt{2}{F}_n<F_{n+1}<2F_n$. $\text{2.}$ Let $k\ge 4$ be an integer. In this question, one supposes that one has three urns $A$, $B$ and $C$ as well as $3F_k$ tokens indistinguishable by touch, numbered from $1$ to $3F_k$. One distributes these tokens in the following manner: $\bullet$ the $F_{k-2}$ tokens of largest numbers are placed in $A$; $\bullet$ the $F_{k-1}$ tokens of largest numbers remaining are placed in $B$; $\bullet$ the $F_k$ tokens of largest numbers remaining are placed in $C$; $\bullet$ the $F_{k-1}$ tokens of largest numbers remaining are placed in $A$; $\bullet$ the $F_{k-2}$ last tokens are placed in $B$. One draws independently one token from each of the urns $A$, $B$ and $C$, one denotes respectively by $X_A$, $X_B$ and $X_C$ the numbers of the tokens drawn in $A$, $B$ and $C$. $\text{a.}$ Show the two inequalities $\mathbb{P}(X_A>X_B)\ge \frac{1}{2}$ and $\mathbb{P}(X_B>X_C)\ge \frac{1}{2}$. $\text{b.}$ Claire and Paul play at the following game: one of them begins by choosing one of the three urns; then the other player chooses one of the two remaining urns that he contests. They each draw a token from their urn and the one who draws the larger number wins. Does Claire have an interest in choosing her urn before Paul or in letting him choose first?

$\text{3.3 Non-transitive urns}$ Let $n\ge 3$ be an integer. One has three urns $A$, $B$ and $C$ and $3n$ tokens indistinguishable by touch, numbered from $1$ to $3n$. One distributes the tokens in the three urns so that each urn contains $n$ tokens. One draws then independently one token from each of the three urns, and one denotes respectively by $X_A$, $X_B$ and $X_C$ the numbers of the tokens drawn in $A$, $B$ and $C$. One says that such a distribution is non-transitive when the probabilities $\mathbb{P}(X_A>X_B)$, $\mathbb{P}(X_B>X_C)$ and $\mathbb{P}(X_C>X_A)$ are all strictly greater than $\frac{1}{2}$. $\text{1.}$ In this question, one considers a non-transitive distribution of the $3n$ tokens numbered from $1$ to $3n$. One forms three new urns $D$, $E$, $F$: urn $D$ contains the content of the urn $A$, as well as the tokens numbered $3n+1$ and $3n+6$; urn $E$ contains the content of the urn $B$, as well as the tokens numbered $3n+4$ and $3n+5$; urn $F$ contains the content of the urn $C$, as well as the tokens numbered $3n+2$ and $3n+3$. Each of the urns $D$, $E$ and $F$ thus contains $n+2$ tokens. One draws then independently one token from each of the urns $D$, $E$ and $F$, and one denotes respectively by $X_D$, $X_E$ and $X_F$ the numbers of the tokens drawn in $D$, $E$ and $F$. $\text{a.}$ Show that the probabilities $\mathbb{P}(X_D>X_E)$, $\mathbb{P}(X_E>X_F)$ and $\mathbb{P}(X_F>X_D)$ are strictly greater than $\frac{1}{2}$. $\text{b.}$ Show that each of the probabilities $\mathbb{P}(X_D>X_E)$, $\mathbb{P}(X_E>X_F)$ and $\mathbb{P}(X_F>X_D)$ is strictly greater than $\frac{1}{2}$. $\text{2.}$ Let $n\ge 3$ be an integer. One denotes by ${\mathcal{N}}_n$ the following property: it is possible to distribute $3n$ tokens indistinguishable by touch, numbered from $1$ to $3n$, in three urns $A$, $B$ and $C$ so that the two conditions below are simultaneously satisfied: $\bullet$ Each of the three urns contains $n$ tokens. $\bullet$ If one draws independently one token from each of the urns and denotes respectively by $X_A$, $X_B$ and $X_C$ the numbers of the tokens drawn in $A$, $B$ and $C$, then the probabilities $\mathbb{P}(X_A>X_B)$, $\mathbb{P}(X_B>X_C)$ and $\mathbb{P}(X_C>X_A)$ are strictly greater than $\frac{1}{2}$. $\text{a.}$ Show that the properties ${\mathcal{N}}_3$ and ${\mathcal{N}}_4$ are true. $\text{b.}$ Show, for every integer $n\ge 3$, that the assertion ${\mathcal{N}}_n$ is true.

Topic: Probabilità, Combinatoria, Algebra Metodo: Induzione, Conteggio, Casework, Ricorsione Abilita: Conteggio sistematico, Modellizzazione, Lettura attenta Area: Combinatoria, Logica e Probabilita, Algebra e Analisi Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

More than one chance in two for everyone: non-transitive dice and urns; compute and compare winning probabilities, analyze a choosing game, use the Fibonacci sequence and prove a non-transitive distribution exists for every n by induction.

$\text{3.1 Dice and urns}$ $\text{1.}$ In this question, one supposes that one has three urns $A$, $B$ and $C$ that contain each tokens indistinguishable by touch. The tokens of $A$ bear the numbers $11$, $6$, $10$, $3$ and $1$; those of $B$ bear the numbers $9$, $8$, $7$, $2$ and $5$; those of $C$ bear the numbers $11$, $5$, $4$, $3$ and $4$. One draws independently one token from each of the urns, one denotes respectively by $X_A$, $X_B$ and $X_C$ the numbers of the tokens drawn in $A$, $B$ and $C$. $\text{a.}$ One supposes here that the three urns contain each five tokens numbered such as above. Calculate the three probabilities $\mathbb{P}(X_A>X_B)$, $\mathbb{P}(X_B>X_C)$ and $\mathbb{P}(X_C>X_A)$. $\text{b.}$ Claire and Paul play at the following game: one of them begins by choosing a die, then the other chooses one of the two remaining dice that she contests. They each throw their die and the one who obtains the larger number wins. Does Claire have an interest in choosing her die before Paul or in letting him choose first? $\text{c.}$ Finally, it is decided that it is Paul who chooses first. Which die or dice does he have an interest in choosing? $\text{d.}$ Claire and Paul then decide to modify the rules. One of them chooses one of the three dice. Then the other takes die $D_2$ first. Which die does Claire have an interest in choosing, and in letting choose first?

$\text{2.}$ In this question, one supposes that one has three balanced six-faced dice $D_1$, $D_2$ and $D_3$, where the faces of $D_1$ bear the numbers $0$, $0$, $4$, $4$, $4$, $4$; those of $D_2$ bear the numbers $3$, $3$, $3$, $3$, $3$, $3$; and those of $D_3$ bear the numbers $6$, $6$, $2$, $2$, $2$, $2$. $\text{a.}$ One throws independently each of the three dice and one denotes respectively by $X_1$, $X_2$ and $X_3$ the numbers indicated by the upper face of the dice $D_1$, $D_2$ and $D_3$. Calculate the three probabilities $\mathbb{P}(X_1>X_2)$, $\mathbb{P}(X_2>X_3)$ and $\mathbb{P}(X_3>X_1)$. $\text{b.}$ Claire and Paul play at the following game: one of them begins by choosing a die, then the other chooses one of the two remaining dice. They each throw their die and the one who obtains the larger number wins. Does Claire have an interest in choosing her die before Paul or in letting him choose first? $\text{c.}$ Finally, it is decided that it is Paul who chooses first. Which die or dice does he have an interest in choosing? $\text{d.}$ Claire and Paul then decide to modify the rules: one of them chooses one of the three dice, then the other takes die $D_2$. Which die does Claire have an interest in choosing?

$\text{3.2 The Fibonacci sequence and the urns}$ The Fibonacci sequence $(F_n{)}_{n\ge 0}$ is defined by $F_0=0$, $F_1=1$ and, for every integer $n\ge 0$, $F_{n+2}=F_{n+1}+F_n.$ $\text{1.}$ Show, for every integer $n\ge 3$, that $\sqrt{2}{F}_n<F_{n+1}<2F_n$. $\text{2.}$ Let $k\ge 4$ be an integer. In this question, one supposes that one has three urns $A$, $B$ and $C$ as well as $3F_k$ tokens indistinguishable by touch, numbered from $1$ to $3F_k$. One distributes these tokens in the following manner: $\bullet$ the $F_{k-2}$ tokens of largest numbers are placed in $A$; $\bullet$ the $F_{k-1}$ tokens of largest numbers remaining are placed in $B$; $\bullet$ the $F_k$ tokens of largest numbers remaining are placed in $C$; $\bullet$ the $F_{k-1}$ tokens of largest numbers remaining are placed in $A$; $\bullet$ the $F_{k-2}$ last tokens are placed in $B$. One draws independently one token from each of the urns $A$, $B$ and $C$, one denotes respectively by $X_A$, $X_B$ and $X_C$ the numbers of the tokens drawn in $A$, $B$ and $C$. $\text{a.}$ Show the two inequalities $\mathbb{P}(X_A>X_B)\ge \frac{1}{2}$ and $\mathbb{P}(X_B>X_C)\ge \frac{1}{2}$. $\text{b.}$ Claire and Paul play at the following game: one of them begins by choosing one of the three urns; then the other player chooses one of the two remaining urns that he contests. They each draw a token from their urn and the one who draws the larger number wins. Does Claire have an interest in choosing her urn before Paul or in letting him choose first?

$\text{3.3 Non-transitive urns}$ Let $n\ge 3$ be an integer. One has three urns $A$, $B$ and $C$ and $3n$ tokens indistinguishable by touch, numbered from $1$ to $3n$. One distributes the tokens in the three urns so that each urn contains $n$ tokens. One draws then independently one token from each of the three urns, and one denotes respectively by $X_A$, $X_B$ and $X_C$ the numbers of the tokens drawn in $A$, $B$ and $C$. One says that such a distribution is non-transitive when the probabilities $\mathbb{P}(X_A>X_B)$, $\mathbb{P}(X_B>X_C)$ and $\mathbb{P}(X_C>X_A)$ are all strictly greater than $\frac{1}{2}$. $\text{1.}$ In this question, one considers a non-transitive distribution of the $3n$ tokens numbered from $1$ to $3n$. One forms three new urns $D$, $E$, $F$: urn $D$ contains the content of the urn $A$, as well as the tokens numbered $3n+1$ and $3n+6$; urn $E$ contains the content of the urn $B$, as well as the tokens numbered $3n+4$ and $3n+5$; urn $F$ contains the content of the urn $C$, as well as the tokens numbered $3n+2$ and $3n+3$. Each of the urns $D$, $E$ and $F$ thus contains $n+2$ tokens. One draws then independently one token from each of the urns $D$, $E$ and $F$, and one denotes respectively by $X_D$, $X_E$ and $X_F$ the numbers of the tokens drawn in $D$, $E$ and $F$. $\text{a.}$ Show that the probabilities $\mathbb{P}(X_D>X_E)$, $\mathbb{P}(X_E>X_F)$ and $\mathbb{P}(X_F>X_D)$ are strictly greater than $\frac{1}{2}$. $\text{b.}$ Show that each of the probabilities $\mathbb{P}(X_D>X_E)$, $\mathbb{P}(X_E>X_F)$ and $\mathbb{P}(X_F>X_D)$ is strictly greater than $\frac{1}{2}$. $\text{2.}$ Let $n\ge 3$ be an integer. One denotes by ${\mathcal{N}}_n$ the following property: it is possible to distribute $3n$ tokens indistinguishable by touch, numbered from $1$ to $3n$, in three urns $A$, $B$ and $C$ so that the two conditions below are simultaneously satisfied: $\bullet$ Each of the three urns contains $n$ tokens. $\bullet$ If one draws independently one token from each of the urns and denotes respectively by $X_A$, $X_B$ and $X_C$ the numbers of the tokens drawn in $A$, $B$ and $C$, then the probabilities $\mathbb{P}(X_A>X_B)$, $\mathbb{P}(X_B>X_C)$ and $\mathbb{P}(X_C>X_A)$ are strictly greater than $\frac{1}{2}$. $\text{a.}$ Show that the properties ${\mathcal{N}}_3$ and ${\mathcal{N}}_4$ are true. $\text{b.}$ Show, for every integer $n\ge 3$, that the assertion ${\mathcal{N}}_n$ is true.

src_cgen_2019__Q03