Le pozioni di Hardy e Ron

[Marco]

Ciao. Chi ha fatto la Squadre ci ha già sbattuto il cranio, ma gli altri non lo hanno ancora visto. E allora:

Alla lezione di pozioni
Durante la lezione di pozioni, Hardy e il suo amico Ron Perelman devono scegliere due ingredienti sui 36 disponibili e mischiarli nella speranza di ottenere una pozione con qualche proprietà. La loro amica Hermita gli ha detto che se i primi due ingredienti non hanno effetto conviene riprovare con altri due (cambiandoli
entrambi): può capitare che anche in questo caso non ottenga nulla, ma allora – lo assicura – mischiando un ingrediente da ciascuna coppia (in qualunque modo) si otterrà per forza una pozione utile. Quante sono come minimo le combinazioni di due ingredienti che danno una pozione utile?

E, aggiungo io, se cambiamo 36 con N? Descrivere le possibili configurazioni di pzioni utili/inutili.

Non vorrei la sola risposta numerica, ma una vera dimostrazione olympic-style. Chi si lancia?

[Ale the punisher]

Mah, stile olimpionico non mi cimento (scrivo cose incomprensibili), comunque se non mi ricordo male (l'ho fatta anch'io la gara a squadre per il dini di Pisa) bisognava fare il coefficente binomiale di 36 su 2 e poi togliere 36 che erano i casi che si potevano escludere perché si dovevano considerare a terne...

[Marco]

Ok. così viene 594, che è il risultato corretto per N=36. Tuttavia non è sempre vero che il risultato sia
$ \binom{N}{2} - N $.
E due righe sul perché non si può fare di meglio?

[piever]

Mi butto:
non ci possono, per ipotesi, essere 4 elementi tutti fra loro incompatibili, ovvero, dati 3 elementi tra loro incompatibili, questi 3 sono compatibili con tutti quelli esterni alla terzina. Ogni terzina elimina 3 combinazioni di coppie di ingredienti per cui se $ 3|N $ allora le combinazioni sono $ {N \choose 2} - N $
Se $ N\equiv 1 \mod 3 $ allora otteniamo $ {N \choose 2} - N +1 $ ossia sottraiamo 3 combinazioni per ogni terzina incompatibile e avanza un elemento compatibile con tutti gli altri. Invece se $ N\equiv 2 \mod 3 $ allora otteniamo $ {N \choose 2} - N +1 $ ossia oltre alle solite terzine incompatibili c'è una coppia di elementi incompatibili.

[Marco]

piever:dati 3 elementi tra loro incompatibili,

Ah, ah! Altolà. Potrebbero non esistere 3 elementi tra loro incompatibili.

Se ci sono, hai dimostrato quei tre lì sono un triangolo che vive da solo (una componente connessa). E se non ci sono? E poi, chi ti assicura che riarrangiando completamente il grafo non si possa fare di meglio?

[piever]

Effettivamente la mia dimostrazione ha qualche falla ma possiamo tranquillamente vederla così: bisogna trovare elementi con le caratteristiche tali da avere la maggior quantità possibile di coppie non funzionanti. Bisogna vedere ora con che schema stabilire gli ingredienti tra loro incompatibili in modo da massimizzare la quantità di coppie non funzionanti.
Con tutte coppie si eliminano $ \frac{n}{2} $ o $ \frac{n-1}{2} $ combinazioni (dipende dal fatto che $ N $ può essere pari o dispari); con tutte terzine invece si eliminano $ N $ o $ N-1 $ combinazioni. Quattro o più elementi incompatibili fra loro non possono esistere, l'unica possibilità che rimane è che ci sia un elemento incompatibile con vari elementi, tra loro compatibili: in quel caso però si possono eliminare al massimo $ N-1 $ combinazioni (questo sistema è dunque equivalente a quello delle terzine se $ 3 \not | N $).

[Marco]

Beh, tieni presente quel che ho scritto sull'altro filo: il grafo bipartito (1,N-1) è quasi ottimo (a volte senza quasi...). Dalla tua dimostrazione sembra che componenti con 4 o più nodi non possano esistere... eppure te ne sto esibendo una con ben N nodi.... something's missing.

[piever]

Marco:

Beh, tieni presente quel che ho scritto sull'altro filo: il grafo bipartito (1,N-1) è quasi ottimo (a volte senza quasi...). Dalla tua dimostrazione sembra che componenti con 4 o più nodi non possano esistere... eppure te ne sto esibendo una con ben N nodi.... something's missing.

piever:

Quattro o più elementi incompatibili fra loro non possono esistere, l'unica possibilità che rimane è che ci sia un elemento incompatibile con vari elementi, tra loro compatibili: in quel caso però si possono eliminare al massimo $ N-1 $ combinazioni (questo sistema è dunque equivalente a quello delle terzine se $ 3 \not | N $).

Non ci siamo capiti: io intendevo dire che non possono esistere 4 elementi tali che, scelti due a caso al loro interno, sicuramente quei due sono incompatibili. Ho valutato anche la tua ipotesi, ma è ottimale solo se $ 3 \not | N $ (come ho già detto) e in quel caso corrisponde a ciò che si otterrebbe con le terzine.
A questo punto la dimostrazione sembrerebbe soddisfacente.

[Marco]

Mah, direi proprio di no!

Tu dici: "non ci possono essere 4 elementi tra loro incompatibili" (i.e. il grafo non può contenere grafi completi con 4 vertici) e deduci che gli elementi sono associati a coppie o a terzine. Chi ti dice che non esista un grafo molto grosso, con più archi di quel che ti aspetti, che non viola l'ipotesi?

L'unico claim che ti posso concedere è "se le componenti connesse hanno al massimo tre vertici, allora il grafo ottimale è quello con tanti triangolini ed una eventuale componente di resto".

il caso con componenti connesse più grandi, invece, manca totalmente.

[piever]

Che incubo questa dimostrazione!
Allora, provo a ricapitolare:
-mettenodoli a coppie, è poco conveniente
-a terzine elimino $ n $ o $ n-1 $ combinazioni

Ora:
devo dimostrasre che non può esistere una possibilità di unire gli elementi incompatibili in gruppi più grandi di 3 più conveniente che unirli a terzine (spero che questo basti):
trascuro i grafi composti da $ n\leq 3 $ nodi perché

se le componenti connesse hanno al massimo tre vertici, allora il grafo ottimale è quello con tanti triangolini ed una eventuale componente di resto

Esamino un grafo con $ n>3 $ nodi in cui gli archi congiungono i nodi "incompatibili": abbiamo che, se A è congiunto a B e A è congiunto a C (cosa che accade per forza almeno in un caso, perché metterli a coppie non conviene), allora B può essere congiunto SOLO con C e C può essere congiunto SOLO con B, e se congiungiamo B con C sappiamo che A, B e C non sono congiunti a nessun nodo esterno alla terzina, tutto questo si vede facilmente perché altrimenti si formerebbero 2 coppie incompatibili in cui un elemento di una coppia è incompatibile a un elemento dell'altra coppia, contraddicendo dunque l'ipotesi.
Per cui, in un gruppo di più di 3 nodi congiunti da vari archi sappiamo che l'unica possibilità è che ci sia un unico nodo congiunto a tutti gli altri. In questo caso, ovviamente, data una componente connessa di $ n $ elementi, essi sono collegati da $ n-1 $ archi, ovvero un numero uguale o minore a quello che si otterrebbe unendo quei termini a terzine, per cui le terzine sono SEMPRE un sistema ottimale.

[Marco]

Cominciamo ad esserci. Giusto per fissare un po' di terminologia, diciamo che un asterisco è un grafo connesso, in cui c'è un nodo speciale (che chiamo radice), congiunto a tutti gli altri nodi (che chiamo foglie), e nessuna foglia è congiunta ad un'altra foglia.

Claim: Le componenti connesse del grafo, o sono triangoli, o sono asterischi.

Dim.: Vediamo a seconda del numero di nodi in una componente connessa.

n=1. L'unico grafo è un nodo isolato, che è un asterisco con 0 foglie.

n=2. L'unico grafo connesso è una coppia di nodi congiunti, che è un asterisco con una foglia.

n=3. Ci sono solo due grafi connessi. Uno è un asterisco. L'altro è un triangolo.

n>3.

Siano F e R due nodi connessi. Esiste almeno un altro nodo, che chiamo Y. Dato che siamo in una componente connessa, esiste un percorso che parte da Y e arriva in F o in R. Per fissare le idee, diciamo che arriva in R senza passare da F (altrimenti scambio R e F). Diciamo che appena prima di arrivarci, passa per F'. R è la mia candiadata radice. Sia X l'insieme dei nodi congiunti con R (le candidate foglie). Si noti che X contiene almeno due nodi (F e F').

Dico che oltre a R e X non ci sono altri vertici. Infatti: sia Y un nodo nella componente connessa che non è in X. Esiste un percorso che connette Y a R. Tale percorso ad un certo punto arriva in X. Sia Y' l'ultimo nodo non in X (esiste, dato che almeno Y non è in X) e F il nodo successivo (necessariamente in X. Dato che X contiene almeno due nodi, non può esserci solo il nodo F, ma ci sarà almeno un altro nodo che chiamo F'. Allora le coppie (Y',F), (R,F') violano la regola delle quaterne (F e R sono congiunti).

Quindi c'è solo R e le foglie. Vediamo che le foglie non sono congiunte tra loro. Supponiamo che F e F' siano congiunte. La componente ha almeno quattro nodi, quindi c'è almeno una terza foglia F". Ma allora le coppie (F,F'), (R,F") violano la regola.

Ma allora la componente connessa è un asterisco.

---------------

Ora contiamo gli archi di un grafo con N vertici, con componenti connesse che sono solo asterischi o triangoli.

Si noti che un asterisco con k nodi ha k-1 archi.

Sia C il numero di componenti di tipo triangolo e C* il numero di componenti di tipo asterisco; sia V il numero di vertici nei triangoli e V* il numero di vertici negli asterischi; sia A il numero di archi nei triangoli e A* il numero di archi negli asterischi.

E' ovvio che:
V = A = 3C
V + V* = N
A* = V* - C* [questo perché ogni asterisco con k vertici ha k-1 archi]

da cui:
totale archi = A + A* = V* - C* + V = N - C*

Ossia il totale degli archi è massimo quando il numero di componenti asterisco è minimo.

Se N è multiplo di 3, il grafo di soli triangoli (e solo quello) permette di avere 0 asterischi, quindi è ottimale, con N archi

Se N non è multiplo di 3, deve esistere almeno un asterisco. Quindi i grafi ottimali sono tutti e soli quelli con un certo numero di triangoli e i restanti nodi che formano un asterisco; tali grafi hanno N-1 archi. []

Ad esempio, per N = 37, esistono 13 grafi ottimali con 36 archi: un grafo con k triangoli e con un asterisco con 37 - 3k nodi (con k che varia da 0 a 12).