97. Funzioni abbastanza diverse

[Federiko]

Sia $p$ un primo e $n$ un intero tali che $p\ge n>3$. Sia $S$ l'insieme delle funzioni da $\{1,2,...,n\}$ a $\{1,2,...,p\}$. Sia $A\subseteq S$ con la seguente proprietà: per ogni coppia di funzioni $f,g$ in $A$, esistono almeno tre $i\in\{1,2,...,n\}$ tali che $f(i)\neq g(i)$. Quanti elementi contiene al massimo $A$?

Mi accontento anche se risolvete soltanto il caso $n=p$ che non presenta alcune scocciature

[Federiko]

Vabbè, è passato molto tempo e nessuno ha ancora risposto.. Semplifico un pochino il problema:
Dimostrare che $\max |A| \ge p^{n-2}$

[Valenash]

Allora provo io a risolvere il problema semplificato, sperando che la mia soluzione sia giusta

Allora, costruisco l'insieme $B$ delle funzioni da $\{1,2,..., n-2\}$ a $\{1,2,...,p\}$. Queste sono in numero di $p^{n-2}$ poichè ci sono $p$ modi di scegliere l'immagine di ciascuno degli $n-2$ elementi del dominio.
Mostro ora che $|A| \ge |B|$
Ora, tra tutte le funzioni che appartengono a $B$, alcune coppie di funzioni avranno almeno 3 valori $i$ tali per cui $f(i)\ne g(i)$, altre avranno solamente due valori per cui accade ciò, altre ancora solamente un valore.
A questo punto basta mostrare che si può creare una funzione iniettiva da $B$ ad $A$ per avere la tesi.
Ciò è vero poichè per ogni coppia di funzioni appartenenti a $B$ tali per cui c'è un solo valore di $i$ per cui $f(i)\ne g(i)$ (con $f, g$ appartenenti a $B$), si possono creare altre due funzioni $h$ e $t$ da $\{1,2,..., n\}$ a $\{1,2,...,p\}$, tali per cui gli elementi da $1$ a $n-2$ abbiamo la stessa immagine che hanno rispettivamente $f$ e $g$, mentre gli elementi $n-1$ e $n$ abbiano due immagini diverse nel codominio (inteso nel senso che le due immagini di $n-1$ e $n$ della funzione $h$ siano diverse dalle due immagini degli stessi valori della funzione $t$).
A questo punto è ovvio che $h$ e $t$ hanno almeno 3 valori $i$ tali per cui $h(i)\ne t(i)$, per il modo in cui sono state costruite. Inoltre, partendo da ogni funzione in $B$ se ne crea un altra in $A$, ma non è detto che tutte le funzioni di $A$ possano derivare da una funzione di $B$.
Dunque, abbiamo creato la funzione iniettiva e dimostrato che $|A| \ge |B|$, e dato che $|B| \ge p^{n-2}$, allora $|A| \ge p^{n-2}$.
(c.v.d.)

[Federiko]

Non va bene.. Infatti tu hai creato soltanto una funzione iniettiva dalle coppie di elementi di $B$ alle coppie di elementi di $A$. Rifletti, tu trovi $h$ da $f$, ma $h$ dipende anche dalla scelta di $t$ e quindi di $g$ !

[Anér]

Io comincerei a contare quante funzioni diverse a due a due in almeno 2 (e non per forza 3) posizioni si possono prendere, che è un problema ulteriormente semplificato e si fa più o meno allo stesso modo ( e viene $ p^{n-1} $).

[Federiko]

[per andrea] Più in generale, è facile dimostrare che se voglio le funzioni diverse in almeno $k$ valori, $\max |A|\ge p^{n-k+1}$

[Anér]

Piazzo la mia soluzione, poi Cucciolo piazzerà la sua (ci siamo messi d'accordo così).
$p^{n-2}$ funzioni si fanno: prendiamo tutte quelle che soddisfano il seguente sistema di congruenze:
$\sum_{i=1}^n f(i)\equiv 0 \pmod{p}$
$\sum_{i=1}^n i\cdot f(i)\equiv 0\pmod{p}$
Queste sono tante quanti i modi di scegliere f(1), f(2), ... f(n-2) a piacere, perché gli ultimi due valori sono determinati dal sistema che diventa di due equazioni e due incognite e con determinante diverso da 0 modulo p. Inoltre se due funzioni del gruppo coincidono in n-2 punti allora sono la stessa per lo stesso motivo, ossia perché gli ultimi due valori devono essere quelli che soddisfano il sistema di due equazioni e due incognite che si crea imponendo gli n-2 valori che sappiamo essere uguali. Ancora una volta il determinante non può mai essere nullo, perché il determinante è quello di una delle sottomatrici 2 per 2 della seguente:
1 1 1 1 ... 1
1 2 3 4 ... n

Se poi avessimo $p^{n-2}+1$ funzioni reciprocamente compatibili, le divido nelle $p^{n-2}$ classi di equivalenza in base all'uguaglianza sui primi n-2 valori, ovvero metto nella stessa classe due funzioni f e g se e solo se f(1)=g(1), f(2)=g(2), ... , f(n-2)=g(n-2).
Per pigeonhole c'è una classe che contiene almeno $ \lfloor \frac{p^{n-2}+1}{p^{n-3}}\rfloor=2 $ funzioni, ma questo è assurdo perché due funzioni distinte non possono coincidere in n-2 valori, ovvero dovevamo sperare che ogni classe contenesse al più una funzione.
Quest'ultimo argomento si adatta anche al caso "funzioni diverse in almeno k punti", ma la prima parte no, non sono sicuro di poter trovare una matrice n per k tale che ogni sottomatrice k per k abbia determinante non nullo modulo p (anche se qualcosa mi dice che ci si può credere).

[Federiko]

Benissimo, per me puoi andare col prossimo problema. Per la prima parte io ho fatto diversamente:
Fatto: L'insieme delle funzioni da $\{1,2,...,n\} \rightarrow \{1,2,...,p\}$ è in bigezione con l'insieme dei polinomi a coefficienti in $\mathbb Z_p$ di grado $\le n-1$. Infatti per interpolazione c'è sempre uno e un solo polinomio di questo tipo tale che
$$\left\{ \begin{array}\\
P(1)=f(1)\\
P(2)=f(2)\\
...\\
P(n)=f(n)
\end{array}
\right .$$
e ovviamente ogni polinomio è una funzione.

Chiarito questo, se io prendo come insieme delle funzioni i polinomi di grado $\le n-k$, questi sono $p^{n-k+1}$ e due di loro non possono essere uguali in più di $n-k$ valori (per il grado) , ergo differiscono per almeno $k$ valori.