Famiglia di partizioni molto diverse.

[Carlein]

Forse lo troverete un pò facile, ma per alcuni versi io l'ho trovato interessante.
Sia A un insieme con $ p^n $ elementi, p primo,n intero positivo. Supponiamo di avere una famiglia F di partizioni di A,tale che ciascuna partizione della famiglia ha classi di lunghezza divisibile per p, e se pesco una classe da una partizione in F e una classe da un'altra partizione in F, allora hanno al più un elemento in comune. Trovare qual'è il massimo che |F| può assumere.

[dario2994]

Assumo per comodità $A=\{1,2,\dots, p^n\}$
Mostro che $ |F|\le \frac{p^n-1}{p-1} $.
Siano $I_1,I_2,\dots I_{|F|}$ le classi delle varie partizioni che contengono 1. Sia $J_k=I_k\backslash \{1\}$.
Per le ipotesi: $|J_a\cap J_b|=0$ per ogni scelta di a,b. Ma allora vale:
$\displaystyle p^n-1=|A|\backslash\{1\}\ge \left|\bigcup_{i=1}^{|F|}J_i\right|=\sum_{i=1}^{|F|}|J_i|\ge \sum_{i=1}^{|F|}(p-1)=|F|(p-1)$
Da cui $ |F|\le \frac{p^n-1}{p-1} $

E ora tocca mostrare l'esempio... che è un poco un caos... per trovare come scriverlo ho impiegato un bel pezzo... l'idea non è originalissima, è mezza copiata dal thread "campi proiettivi finiti" che avevo piazzato qualche mese fa... l'idea è sempre quella di sfruttare un poco la struttura di $Z_{p^n}$ (lì bastava $Z_p$)
Lo mostro per induzione su $n$. Il passo base mi pare credibile
Definisco per $0\le k<p:\ B_k=[kp^{n-1}+1,(k+1)p^{n-1}]$.
E ora costruisco per $1\le a\le p^{n-1}$ e $0\le b<p^{n-1}$ l'insieme $C_{a,b}$ (che è una classe delle future partizioni) che rispetta le seguenti proprietà (è chiaro che definisco univocamente l'insieme):
$C_{a,b}\subseteq A$
$|C_{a,b}|=p$
$C_{a,b}\cap B_k\equiv a+kb\pmod{p^{n-1}}$
Ora definisco per $0\le i<p^{n-1}$ la partizione $P_i$ di $A$:
$P_i=\{C_{1,i},C_{2,i},\dots , C_{p^{n-1},i}\}$
Perchè è davvero una partizione? Beh se $|C_{x,i}\cap C_{y,i}|>0$ allora dovrei avere che vale per qualche $0\le k<p$ $x+ki\equiv y+ki\pmod{p^{n-1}}$ ma allora x=y.
Ora... perchè le partizioni rispettano le ipotesi? Se per assurdo $|C_{u,v}\cap C_{a,b}|\ge 2$ esistono $0\le k_1<k_2<p$ tali che:
$a+k_1b\equiv u+k_1v\pmod{p^{n-1}}$ e $a+k_2b\equiv u+k_2v\pmod{p^{n-1}}$ da cui si ottiene facilmente:
$(b-v)(k_1-k_2)\equiv 0\pmod{p^{n-1}}$ da cui $b=v$ e da questo ottengo $a=u$ e quindi nada perchè le classi con intersezione almeno 2 devono coincidere per forza.

Bene, ora che ho usato tutto l'alfabeto , ho creato soltanto $p^{n-1}$ partizioni che rispettano le ipotesi... che fare? Bon è il momento di pigliarne $\frac{p^{n-1}-1}{p-1}$ che funzionano per $|A|=p^{n-1}$ che esistono per ipotesi induttiva. Ora che le ho prese le "moltiplico per p" cioè da ognuna ne creo una per $|A|=p^n$ ricopiando la stessa partizione in $B_0,B_1,\dots, B_{p-1}$. E queste le aggiungo alla famiglia $F$ di partizioni che sto costruendo.
Queste perchè fungono? Beh perchè le loro classi appartengono completamente ad un solo $B_i$ quindi l'intersezione con una classe di $P_j$ è al massimo 1, tra loro funzionano per ipotesi induttiva... quindi fine dato che: $\frac{p^{n-1}-1}{p-1}+p^{n-1}=\frac{p^n-1}{p-1}$

p.s. come problema in effetti non è difficile, ma scriverlo... tostissimo
p.p.s. forse è superfluo dire che ci saranno un miliardo di errorini...

[Carlein]

A me torna,se ho capito la tua costruzione c'è un piccolo typo nella definizione di $ B_k $ dovrebbe essere $ [kp^{n-1},(k+1)p^{n-1}] $.

Una soluzione un pò più intuitiva esce fuori in $ (\mathbb{Z}_p)^n $. Uno si convince facilmente ad esempio che in $ \mathbb{R}^n $ i fasci di rette parallele sono esempi di partizioni del genere( due rette distinte si incontrano in al più un punto):in questa costruzione il fatto di avere R non ha niente di speciale, ma va bene qualunque campo. Quindi per ogni retta passante per l'origine associo il fascio di rette parallele ad essa,e così ottengo una partizione in F. Una retta passante per l'origine sono i multipli di un vettore nonnullo di $ (\mathbb{Z}_p)^n $. quindi tutte le $ p^n-1 $ possibilità si raggruppano in blocchi da p-1. Quindi si ottiene $ (p^n-1)/(p-1) $ elementi in F.

[dario2994]

A me torna,se ho capito la tua costruzione c'è un piccolo typo nella definizione di $ B_k $ dovrebbe essere $ [kp^{n-1},(k+1)p^{n-1}] $.

Gli errori nella definizione di $B_k$ erano ben 2 Corretti (non oso immaginare la quantità di errori, sviste, typo, imprecisioni e minchiate varie che salvo potrebbe trovare nella soluzione )

Una soluzione un pò più intuitiva esce fuori in $ (\mathbb{Z}_p)^n $. Uno si convince facilmente ad esempio che in $ \mathbb{R}^n $ i fasci di rette parallele sono esempi di partizioni del genere( due rette distinte si incontrano in al più un punto):in questa costruzione il fatto di avere R non ha niente di speciale, ma va bene qualunque campo. Quindi per ogni retta passante per l'origine associo il fascio di rette parallele ad essa,e così ottengo una partizione in F. Una retta passante per l'origine sono i multipli di un vettore nonnullo di $ (\mathbb{Z}_p)^n $. quindi tutte le $ p^n-1 $ possibilità si raggruppano in blocchi da p-1. Quindi si ottiene $ (p^n-1)/(p-1) $ elementi in F.

Mi pare, ma potrebbe essere una cagata, che le nostre 2 famiglie di partizioni siano le stesse in realtà
E mi verrebbe da chiedermi se per caso non ci fosse un'unica famiglia che rispetta le richieste delle ipotesi e abbia cardinalità massima... non so la risposta, ma lo piazzo a mò di bonus che è figo :

Bonus: Trovare tutte le famiglie $F$ di cardinalità $\frac{p^n-1}{p-1}$che rispettano le ipotesi.

[Carlein]

Uhm non ci ho ancora pensato per bene,ma è uscita qualche considerazione:
Il fatto che tu dicevi che forse esiste una sola costruzione l'ho interpretato come: rinominando A passo sempre da una famiglia ad un altra.Un'altro problema correlato è poi quante famiglie esistono:se a meno di rinominamenti ne esistesse una sola basterebbe contare in quanti modi una data famiglia viene lasciata fissa dalle permutazioni di A.
una cosa che forse è vera è questa:ogni famiglia massima la posso reinterpretare come il sistema di rette di $ (\mathbb{Z}_p)^n $;non ci ho pensato rigorosamente ma mi pare che si possa proprio fare passo passo,assegnare un origine, trovare n punti che poi saranno una base e definire gli altri come loro combinazione lineare: un motivo per cui penso si possa fare è che si può riconoscere l'equivalente per i punti di un insieme della dipendenza lineare e procedere a rovescio. Forse c'è qualche intoppo che io non vedo, comunque se trovo la calma provo a pensarci meglio. Se questo fosse vero mi sa che è facile mostrare che c'è una sola famiglia a meno di permutazioni di A.

inoltre questo mi fa venire in mente un altro problema:se tutto questo fosse vero allora contare quante sono le famiglia si riduce a contare quante sono le permutazioni di A che fissano una data famiglia. Che ridetto in altri termini sarebbe:quante sono le permutazioni di $ (\mathbb{Z}_p)^n $ che mandano rette in rette(ci sono senza dubbio tutte le affinità, ma ad esempio se p=2, ogni retta è formata da soli 2 punti,quindi ogni permutazione manda rette in rette, ma dovrebbe essere un pò un caso limite..)

Boh,pardon se è un pò vago; se mi viene qualcosa di più pulito in mente,lo scrivo
Ciaociao
p.s:se intendevi un altra cosa nel tuo post fammi sapere