siano $NQ$ l'insieme degli interi positivi che *non* sono quadrati perfetti, e $\mathbb{Z}^+$ l'insieme degli interi positivi. definisco una funzione sugli interi positivi $f:NQ\to \mathbb{Z}^+$ nel seguente modo contorto:
$f(n) = \min_S \{\max S\}$, dove $S$ varia tra tutti i sottoinsiemi di $\mathbb{Z}^+$ con le seguenti tre proprietà:
* $S$ è finito;
* $s > n$ per ogni $s\in S$;
* $n\cdot \prod_{s\in S} s$ è un quadrato perfetto.
ad esempio, $f(2) = 6$, perché $S = \{3,6\}$ soddisfa le proprietà richieste, e nessun sottoinsieme di $\{3,4,5\}$ lo fa, e $f(3) = 8$ perché $S = \{6,8\}$ soddisfa le tre richieste, mentre nessun sottoinsieme di $\{4,5,6,7\}$ lo fa.
dimostrare che $f$ è iniettiva.
che putnam!
Re: che putnam!
hai perfettamente ragione. correggo il testo.
Supponiamo per assurdo che esistano $n, m \in NQ$, $n < m$, tali che $f(n)=f(m)=:a$.
Abbiamo allora $S_n = \{b_1 < \ldots < b_h<a\}, S_m = \{c_1 < \ldots < c_k<a\} \subset NQ$, con $b_1>n$, $c_1>m$,
$\displaystyle n \cdot \prod_{x \in S_n} x =A^2, \qquad m\cdot \prod_{y \in S_n} y =B^2$.
Inoltre non esistono sottoinsiemi $S$ di $\{ n+1, \ldots, a-1\}$ tali che $n \cdot \prod_{x \in S}x$ sia un quadrato perfetto,
e non esistono sottoinsiemi $R$ di $\{ m+1, \ldots, a-1\}$ tali che $m \cdot \prod_{y \in R}y$ sia un quadrato perfetto.
Sia $D:= S_n \cap (S_m \cup \{m\})$. Certamente $a \in D$, dunque $D$ è non vuoto.
Allora $\displaystyle (AB)^2= n \cdot \prod_{x \in S_n}x \cdot \prod_{y \in S_m \cup \{m\}} y= n \cdot \prod_{x \in S_n\setminus D}x \cdot \prod_{y \in (S_m \cup \{m\}) \setminus D} y \cdot \prod_{z \in D}z^2$, quindi $\displaystyle \left( \frac{AB}{\prod\limits_{z \in D} z}\right)^2 = n \cdot \prod_{x \in (S_n \cup S_m \cup \{m\})\setminus D} x$
Ora, $\displaystyle \frac{AB}{\prod\limits_{z \in D} z} \in \mathbb{N}$ (perchè ogni $z$ di $D$ divide sia $A^2$ che $B^2$) , dunque $\displaystyle \left( \frac{AB}{\prod\limits_{z \in D} z}\right)^2$ è un quadrato perfetto.
Posto $S:=(S_n \cup S_m \cup \{m\})\setminus D$, abbiamo che $S$ è non vuoto (altrimenti $n$ sarebbe un quadrato perfetto),
e che $n \cdot \prod_{x \in S}x$ è un quadrato perfetto. Dato che $\text{max}S<a$, abbiamo $f(n)<a$, assurdo.
Abbiamo allora $S_n = \{b_1 < \ldots < b_h<a\}, S_m = \{c_1 < \ldots < c_k<a\} \subset NQ$, con $b_1>n$, $c_1>m$,
$\displaystyle n \cdot \prod_{x \in S_n} x =A^2, \qquad m\cdot \prod_{y \in S_n} y =B^2$.
Inoltre non esistono sottoinsiemi $S$ di $\{ n+1, \ldots, a-1\}$ tali che $n \cdot \prod_{x \in S}x$ sia un quadrato perfetto,
e non esistono sottoinsiemi $R$ di $\{ m+1, \ldots, a-1\}$ tali che $m \cdot \prod_{y \in R}y$ sia un quadrato perfetto.
Sia $D:= S_n \cap (S_m \cup \{m\})$. Certamente $a \in D$, dunque $D$ è non vuoto.
Allora $\displaystyle (AB)^2= n \cdot \prod_{x \in S_n}x \cdot \prod_{y \in S_m \cup \{m\}} y= n \cdot \prod_{x \in S_n\setminus D}x \cdot \prod_{y \in (S_m \cup \{m\}) \setminus D} y \cdot \prod_{z \in D}z^2$, quindi $\displaystyle \left( \frac{AB}{\prod\limits_{z \in D} z}\right)^2 = n \cdot \prod_{x \in (S_n \cup S_m \cup \{m\})\setminus D} x$
Ora, $\displaystyle \frac{AB}{\prod\limits_{z \in D} z} \in \mathbb{N}$ (perchè ogni $z$ di $D$ divide sia $A^2$ che $B^2$) , dunque $\displaystyle \left( \frac{AB}{\prod\limits_{z \in D} z}\right)^2$ è un quadrato perfetto.
Posto $S:=(S_n \cup S_m \cup \{m\})\setminus D$, abbiamo che $S$ è non vuoto (altrimenti $n$ sarebbe un quadrato perfetto),
e che $n \cdot \prod_{x \in S}x$ è un quadrato perfetto. Dato che $\text{max}S<a$, abbiamo $f(n)<a$, assurdo.