Bipartizioni

[giobimbo]

Sia n un numero pari e $I_n$ l'insieme dei numeri da 1 a n; siano A e B due sottoinsiemi di $I_n$, ciascuno con n/2 elementi e tali che la loro unione formi $I_n$; diciamo che A e B formano una bipartizione di $I_n$ se esiste un ordinamento $(a_1, a_2, ..., a_{n/2})$ degli elementi di A e un ordinamento $(b_1, b_2, ..., b_{n/2})$ degli elementi di B tali che l'insieme dei prodotti
{$a_i*b_i$ modulo (n+1)} per i = 1, 2, ..., n/2
sia uguale all'insieme B.


Vediamo subito degli esempi. Sia n=2 e $I_2$={1, 2}, obbligatoriamente A={1} e B={2} e
{1*2 (mod 3)} = {2} = B
quindi A={1} e B={2} formano una bipartizione.


Sia n=4 e $I_4$={1, 2, 3, 4}, ci sono tre possibili suddivisioni di $I_4$:
caso uno: A={1, 2} e B={3, 4}
caso due: A={1, 3} e B={2, 4}
caso tre: A={1, 4} e B={2, 3}

Esaminiamo solo il caso uno, quindi con A={1, 2} e B={3, 4}. Ci sono due possibili ordinamenti distinti:
ordinamento uno: (1, 2) e (3, 4)
ordinamento due: (1, 2) e (4, 3)
da cui moltiplicando modulo 5 otteniamo i due insiemi:
{1*3, 2*4} = {3, 3}
{1*4, 2*3} = {4, 1}
nessuno dei quali è uguale a B={3, 4}, dunque la suddivisione del caso uno non è una bipartizione. Provando con gli altri due casi si scoprirà che non esiste una bipartizione per n=4.

Problema 1. Trovare una bipartizione per almeno altri due valori di n.

Problema 2. Dimostrare che c'è un numero infinito di valori di n per cui esiste una bipartizione.

[Sancho Panza]

Problema 1. Trovare una bipartizione per almeno altri due valori di n.

Per n=6

$I_6$={1, 2, 3, 4, 5, 6},

A={1, 2, 4} e B={3, 5, 6}

ordinamento: (4 ,1 , 2) e (6, 5, 3)
da cui moltiplicando modulo 7 otteniamo i due insiemi:
{4*6 (Mod 7), 1*5 (Mod 7), 2*3 (Mod 7)} = {3, 5, 6}
quindi A={1, 2, 4} e B={3, 5, 6} formano una bipartizione.



Per n=8

$I_8$={1, 2, 3, 4, 5, 6, 7, 8},

A={1, 2, 4, 5} e B={3, 6, 7, 8}

ordinamento: (1 ,4 , 2, 5) e (3, 6, 8, 7)
da cui moltiplicando modulo 9 otteniamo i due insiemi:
{1*3 (Mod 9), 4*6 (Mod 9), 2*8 (Mod 9), 5*7 (Mod 9)} = {3, 6, 7, 8}
quindi A={1, 2, 4, 5} e B={3, 6, 7, 8} formano una bipartizione.

[giobimbo]

Mi hai liberato la mente, grazie Sancho Panza!
Sto ancora studiando l'argomento, ma mi ero fossilizzato sul fatto che esistessero bipartizioni solo per n=4k+2, roba da pazzi.

[Tino]

Ciao ragassi.

Io ci ho pensato un po', ... conclusione: congetturo che perché esista una bipartizione di I_n sia sufficiente che n+1 sia un primo congruo a 3 modulo 4.

Mi rendo conto che questa congettura è un po' allegra

Però sotto l'ipotesi che n+1 sia primo, credo si possa dedurre la disparità di n/2, partendo dal fatto che data una bipartizione (A,B) 1 deve appartenere ad A...

Purtroppo non sono pervenuto ad altre conclusioni tanto concrete da essere degne di essere postate.

[Bruno]

...

Mi tocca abbandonarvi subito, ma volevo
dire che ieri ho provato anch'io a pensarci,
con carta e penna, anche se non sono
riuscito a trovare nulla - in un tempo
ragionevolmente breve, intendo.

Sancho Panza, complimenti per aver scovato
una soluzione al primo problema di Giobimbo,
ma mi farebbe piacere che mi (ci) spiegassi
come sei arrivato a quelle bipartizioni.
Forse hai usato qualche routine o hai fatto dei
tentativi (ponderati) con un foglio di calcolo?
Inoltre, ci saranno solo quelle bipartizioni per
gli n indicati?

E' interessante la tua congettura, Tino:
potrebbe essere. Naturalmente, è interessante
pure capire che cosa potremmo dire sugli n+1
non primi.

A lunedì!


Bruno

[giobimbo]

Grazie alla soluzione di Sancho Panza ho trovato che per n=8 c'è un'altra bipartizione:
A={1, 2, 5, 7}, B={3, 4, 6, 8}
Ogni bipartizione si può ottenere da 2 ordinamenti distinti.

@Tino: sono partito anch'io da quei due assunti, n+1=primo della forma 4k+3 da cui A e B con numero dispari di elementi, ma se qualcuno trova altre vie, benvenuto lo stesso. Come dice Bruno, ogni cosa in più che si scopre può essere interessante, in special modo per me.

[Tino]

Olà.

Credo di aver provato la mia congettura. In modo non del tutto elementare, ma mi adopererò per trovare una dimostrazione che non coinvolga nulla di non elementare.

Il procedimento è carino perché è costruttivo.

Mi servono questi due fatti:

1) Ci sono infiniti primi congrui a 3 modulo 4.

2) Se tolgo lo zero da un campo finito ottengo un gruppo ciclico.

Con questi due fatti assodati credo di poter dimostrare che ci sono infiniti n tali che I_n ammetta una bipartizione. Spendo subito il primo fatto asserendo che è sufficiente provare che se n+1 è un primo congruo a 3 modulo 4 allora I_n ammette una bipartizione.

Per comodità, poiché n è pari, invece di n considero 2n. Il problema è quindi: mostrare che se n è dispari e p:=2n+1 è primo allora I_2n ammette una bipartizione.

Spendo qui il secondo fatto: $F_p=\mathbb{Z}/p\mathbb{Z}$ è un campo, di conseguenza esiste a diverso da 0 in Z/pZ tale che F_p privato dello zero sia un gruppo ciclico generato da a.

Consideriamo per esempio il caso n=5. 2n+1=11, quindi siamo in affari.
Un generatore di $F_{11}^*$ (=F_11 privato dello 0) è 2, nel senso che le potenze successive di 2 modulo 11,

$2,4,8,5,10,9,7,3,6,1$

esauriscono $F_{11}^*$. Sia dunque $a:=2$, e consideriamo il sottogruppo $\langle a^2 \rangle$ e la classe laterale $a \langle a^2 \rangle$. Ordiniamo tali due insiemi (che evidentemente formano una partizione di $F_{11}^*$) in modo crescente rispetto alle potenze (ovvero: sia $a_i=a^{2(i-1)}$ per i=1,...,5, e sia $b_i=a^{2(i-1)+1}$ per i=1,...,5):

$A:=\{1,a^2,a^4,a^6,a^8\}$
$B:=\{a,a^3,a^5,a^7,a^9\}$

Come si vede, i prodotti consecutivi esauriscono B (ricordo che $a^{10}=1$). Più esplicitamente:

$A=\{1,4,5,9,3\}$
$B=\{2,8,10,7,6\}$

Partendo da questa intuizione, ho cercato di generalizzare l'argomento: consideriamo un n dispari tale che p=2n+1 sia un numero primo. Sia a un generatore del gruppo ciclico $F_p^*$. In questo modo $a^{2n}=1$, e di più, poiché a genera un gruppo di cardinalità 2n, a ha ordine 2n. Consideriamo ora

$A:=\{a^0,a^2,a^4,...,a^{2n-4},a^{2n-2}\}=\{a^{2k}\ |\ k=0,...,n-1\}$
$B:=\{a^1,a^3,a^5,...,a^{2n-3},a^{2n-1}\}=\{a^{2k+1}\ |\ k=0,...,n-1\}$

Voglio mostrare che i prodotti (nell'ordine dato) esauriscono B. Il prodotto di $a^{2k}$ e $a^{2k+1}$ è naturalmente $a^{4k+1}$. Consideriamo dunque l'applicazione

$f:A \to B,\ a^{2k} \mapsto a^{4k+1}$

Se l'immagine di f è proprio B, allora abbiamo finito: i prodotti nell'ordine esauriscono B. Quindi si tratta di mostrare che f è suriettiva. Poiché f è una funzione di A in B, due insiemi finiti con la stessa cardinalità, f è suriettiva se e solo se è iniettiva. Basta dunque mostrare che f è iniettiva. Supponiamo che per dati $k,h \in \{0,1,...,n-1\}$ si abbia $f(a^{2k})=f(a^{2h})$. Allora $a^{4k+1}=a^{4h+1}$, ovvero $a^{4(k-h)}=1$. Poiché l'ordine di a è 2n, questo significa che 2n divide 4(k-h), e quindi diciamo

$2nt=4(k-h)$

per un opportuno intero t. Ma n è dispari! Quindi necessariamente t è pari, diciamo t=2s, e quindi abbiamo

$ns=k-h$

Abbiamo trovato che la differenza di due interi compresi tra 0 e n-1 è un multiplo di n. Quindi necessariamente essi coincidono: k=h.

Spero non ci siano errori..

Naturalmente ci sono altri problemi aperti:
Per quali n esiste una bipartizione?
Quante bipartizioni esistono per un n dato?

...

[giobimbo]

Complimenti, Tino, mi hai convinto.

Il procedere della tua dimostrazione segue la stessa strada della mia, anche se non ho usato l'algebra astratta esplicitamente, infatti non sarei stato capace a dimostrare che f è biiettiva. Ho notato le affinità con la teoria dei campi, le classi laterali, ecc. ma siccome non mi spiegavano lo strano comportamento dei primi della forma 4k+1, non ho insistito su quella via. Inoltre mi interessavano soprattutto gli ordinamenti, la loro forma e il loro numero, per la qual cosa ho trovato dei risultati interessanti ma, come ho scritto prima, ci sto ancora rimuginando sopra. Aspetto un paio di giorni (o di più, se preferisci) poi metto la mia dimostrazione.

giobimbo ha scritto:

le classi laterali

Ehm, intendevo i laterali (di un gruppo)...

[Bruno]

...

Per quel che ricordo, Tino, sembra anche a
me che la tua prova sia convincente.
Non avendo la tua disinvolta confidenza con
gli argomenti che utilizzi (non li maneggio da
parecchio tempo), sarei però più propenso
a cercare altre vie.
D'altra parte, pur rimanendo nell'ambito della
condizione sufficiente, mi sembra anche che
non sia per niente facile trovare queste vie
alternative, evitando di finire in passaggi lunghi
e complicati. Ma potrei sbagliare.

Interessa molto anche a me sapere in quanti
modi si possa bipartire In , nei casi in cui sia
possibile farlo. E m'interessa sapere come
scrivere concretamente le varie soluzioni.

Comunque, bel lavoro



Bruno

[Tino]

Eh, ...
Anch'io sono abbastanza convinto che la dimostrazione funzioni, e in effetti ne preferirei una che usi strumenti meno potenti.

[giobimbo]

Ecco una dimostrazione alternativa, la seconda che ho trovato.
Se p è un numero primo diverso da 2 allora Fermat, col suo piccolo teorema, ci dice che per ogni elemento x di $I_{(p-1)}$ abbiamo $x^{(p-1)}(mod \ p) = 1$. Più tardi Eulero scopre che esiste almeno un elemento r di $I_{(p-1)}$ tale che $r^i (mod \ p) = 1$ solo per i=(p-1) o, equivalentemente, che:
{ $r^1 (mod \ p), \ r^2 (mod \ p), ..., \ r^{(p-1)} (mod \ p)$ } = $I_{(p-1)}$.

In Teoria dei numeri gli elementi ${r^1 (mod \ p), \ r^2 (mod \ p)$, ecc., si dicono residui e l'elemento r si chiama radice primitiva: r è l'elemento generatore di gruppo ciclico di cui parla Tino.

A questo punto, come Tino, ho colto l'isomorfismo
A * B = B potenze Pari * potenze Dispari = potenze Dispari
ma ho proseguito oltre
A * B = B potenze Pari * potenze Dispari = potenze Dispari esponenti Pari + esponenti Dispari = esponenti Dispari
perché è più facile maneggiare le somme che i prodotti.


Passiamo alla parte costruttiva facendo le somme modulo (p-1) in questo modo:
(p-1) + 1, 2 + 3, 4 + 5, 6 + 7, ..., (p-3) + (p-2).
Otteniamo una sequenza di (p-1)/2 elementi che inizia con 1 e aumenta di 4 per volta. Ora, se p è della forma 1+4k, p farà parte della sequenza, ma siccome sommiamo modulo (p-1) si troverà scritto come 1 e sarà quindi seguito da 5, 9, ecc.
Se invece p è della forma 1+2+4k troveremo nella sequenza l'elemento 1+2=3 che sarà seguito da 7, 11, ecc.
Riassumendo, abbiamo due diverse sequenze:

p = 1 + 4k ---> 1, 5, 9, ..., (p-4), 1, 5, 9, ..., (p-4)
p = 1 + 2 + 4k ---> 1, 5, 9, ..., (p-2), 3, 7, ..., (p-4)

e la seconda contiene esponenti dispari tutti diversi; allora
$(r^{(p-1)} (mod \ p), \ r^2 (mod \ p), \ r^4 (mod \ p), ..., \ r^{(p-3)} (mod \ p) )$
è un ordinamento di A, l'insieme delle potenze Pari di r e
$(r^1 (mod \ p), \ r^3 (mod \ p), \ r^5 (mod \ p), ..., \ r^{(p-2)} (mod \ p) )$
è un ordinamento di B, l'insieme delle potenze Dispari di r e il loro prodotto dà l'insieme
{ $r^1 (mod \ p), \ r^5 (mod \ p), \ r^9 (mod \ p), ..., \ r^{(p-2)} (mod \ p), \ r^3 (mod \ p), ..., r^{(p-4)} (mod \ p)$ } = B


Per concludere, un esempio usando i dati di Tino, p=11 e r=2. Otteniamo i due ordinamenti
(1, 4, 5, 9, 3) di A e (2, 8, 10, 7, 6) di B, il cui prodotto dà l'insieme
{ $2^1 (mod \ 11), \ 2^5 (mod \ 11), \ 2^9 (mod \ 11), \ 2^3 (mod \ 11), \ 2^7 (mod \ 11)$ } = {2, 10, 6, 8, 7} = B
come si verifica facilmente.

[Bruno]

...

Giusto: il concetto mi torna!
Grazie, Giobimbo

Colgo l'occasione per sottoporre alla
vostra attenzione l'articolo pubblicato
questo mese dal Prof. Umberto Cerruti
nel suo stupendo Blog.
L'argomento, con cui hanno a che fare
(in parte, almeno) anche le cose dette
sopra da Tino e Giobimbo, è profondo
e non può essere semplicemente letto.
Però trovo questo articolo scritto bene,
come sempre, e pure molto stimolante.

Bruno