Cittá dispari al contrario

[fph]

Nell'ultimo dei miei post c'è una soluzione del caso "n dispari" del tuo problema, molto stringata ma funzionante. Per il caso n pari, ho provato a usare la stessa idea ma non ci sto riuscendo al primo colpo.
(a proposito, ho dato un'occhiata alla dimostrazione di Gargantua e non mi torna il passo (b): chi ti dice che levando due membri a un club restino rispettate tutte le condizioni che lo coinvolgono (intersezione con gli altri club dispari))?

[Ratio]

Ma, scusate, la mia è completamente sbagliata?
Forse non è per niente formalizzata, ma le idee mi sembrano buone.

[Ratio]

b) Per massimizzare il numero di club, dobbiamo minimizzare il numero di membri dei clubs (cioè portarlo a 2); ecco la dimostrazione di questa proposizione:
consideriamo un club con n membri, dove n è diverso dal numero minimo di membri possibili per un club (cioè 2); se sottraiamo al club un numero pari di membri, ognuno di questi può a sua volta formare un club sovrapponendosi a un numero dispari di membri del club di partenza; quindi diminuire il numero di membri del club è conveniente, dal momento che mi fa aumentare il numero totale dei clubs; ne consegue che il numero massimo di clubs lo avrò con clubs dotati di un numero minimo di membri, cioè 2.
Ora, dal momento che mi ritrovo solo clubs di 2 membri, l'unica sovrapposizione possibile è quella uguale a 1.

Io credo invece che il numero di membri (che ho, non so perché posto come $ f_m $) è sempre in funzione di n (n inteso come numero di abitanti).
Se ad esempio abbiamo $ n=5 $ ed $ f_m=2 $ come te proponi, al massimo avrò 3 club. Con $ f_m=4 $, invece, ne ho ben 5.

[dorothyhung]

@Ratio Tu dici che per massimizzare il numero dei club allora il numero dei partecipanti ad ogni club deve essere uguale, mi sfugge il motivo, potresti spiegarmelo?

@fph sono interessata al tuo metodo, perchè mi piacerebbe capirlo meglio, solo per questo continuo a fare domande! Provo a riscrivere quello che ho capito e vediamo se è ok.

Praticamente è come se ad ogni Club $ C_i $ assocciassi il suo vettore di incidenza. E poi considerandone una combinazione lineare devo dimostrare che sono linearmente indipendenti, così avrei che il loro numero deve essere minore o uguale a quello dello spazio vettoriale considerato. Giusto?

Ora mi è chiara questa dimostrazione nel caso in cui si abbia che in ogni Club c'è un numero dispari di persone e nell'intersezione di ogni coppia un numero pari. Ma se considero il mio problema, e prendo una combinazione lineare dei vettori, arrivo ad un'uguaglianza del tipo $ (m-1)\lambda_i=0 $ mod 2. Dove $ \lambda_i $ erano i coefficienti che avevo inserito nella combinazione lineare dei vettori di incidenza e m è il numero dei Club. Ma da questo non riesco a concludere! Perchè dovrei provare a suppore $ m=1 $ mod 2. O non saprei come procedere.

[Ratio]

@Ratio Tu dici che per massimizzare il numero dei club allora il numero dei partecipanti ad ogni club deve essere uguale, mi sfugge il motivo, potresti spiegarmelo?

Per massimizzare il numero di club dobbiamo massimizzare anche il numero di membri in comune a due di essi presi a caso, che quindi dovrà essere $ f_m-1 $ perchè dispari e in più vicino possibile a $ f_m $.
Quindi tutti i club, per poter massimizzare il numero di membri in comune, devono avere $ f_m $ membri.
Mi sembra anche logica come considerazione: posso avere il massimo di combinazioni di n oggetti se le posizioni $ f_m $ che possono occupare sono tutte massime (mantenedo come C.E. $ f_m $ pari e $ f_m \le n $).

[fph]

@fph sono interessata al tuo metodo, perchè mi piacerebbe capirlo meglio, solo per questo continuo a fare domande!

Non c'è problema, il problema è divertente e a me fa piacere parlare di queste tecniche, se sono sembrato brusco negli scorsi messaggi non l'ho fatto apposta!

Praticamente è come se ad ogni Club $ C_i $ assocciassi il suo vettore di incidenza. E poi considerandone una combinazione lineare devo dimostrare che sono linearmente indipendenti, così avrei che il loro numero deve essere minore o uguale a quello dello spazio vettoriale considerato.

Io l'avevo messa in modo leggermente diverso in effetti... Se ho ben capito, traducendo in formule la tua versione viene: chiamiamo $ v_i $ i vettori di incidenza, supponiamo che ci sia una combinazione lineare che faccia zero $ \sum a_i v_i=0 $, e cerchiamo di dimostrare che tutti gli a_i sono nulli. Se è vero, allora i v_i sono linearmente indipendenti, quindi sono al più n (dimensione dello spazio vettoriale F2^n in cui vivono)
Prendiamo il prodotto scalare di questa relazione con ognuno dei $ v_j $ e abbiamo $ \sum a_i (v_j,v_i)=0 $ per ogni j, da cui:
-nel problema "facile" che ho esposto io (quello in cui i v_i sono ortonormali), abbiamo finito, perché sapendo quanto valgono i prodotti scalari otteniamo a_j=0 per ogni j
-nell'altro problema, viene invece $ \sum_{i \neq j} a_i = 0 $. Nel caso n dispari, questo sistema ha anche soluzioni non banali (a_i=1 tutti), quindi non sappiamo che fare, la dimostrazione sembra non funzionare. Nel caso n pari, questo sistema ha solo la soluzione banale, quindi di nuovo dimostriamo che gli a_i sono tutti nulli, ma questo ci dimostra un risultato più debole di quello richiesto dal problema: dimostra che il numero di clubs è al più n, mentre ci servirebbe n-1.

Hang on per il prossimo post, ti provo a rispiegare la mia versione (più una che credo funzioni per n pari)...

[fph]

Dunque, io invece facevo una versione leggermente diversa... Chiamiamo "e" il vettore di tutti uni di dimensione opportuna, e I la matrice identità di dimensione opportuna, F2 il campo con due elementi, R i reali (non ho voglia di fare i mathbb...).

Osservazione: ee^T-I è la matrice che ha tutti zeri sulla diagonale e tutti uni fuori.

Lemma 1: in uno spazio vettoriale F2^n di dimensione n pari, ee^T-I ha rango massimo. Dimostrazione: facciamo finta di essere in R^n per un attimo. Allora, gli autovettori di questa matrice sono e (con autovalore n-1) e una qualunque base dello spazio n-1 dimensionale ortogonale a e, ognuno con autovalore -1. Il determinante è il prodotto degli autovalori, quindi viene $ (n-1)(-1)^{n-1} $. Ora, fare il determinante in F2 è come farlo in Z (e quindi in R) e poi ridurlo modulo 2, quindi in F2 il determinante viene $ (n-1)(-1)^{n-1}=1 $ (perché n pari). []
Lemma 2: rango(BC)<=rango(C). Dimostrazione: in tanti modi... per esempio: il rango è la dimensione dell'immagine di una matrice; l'immagine di BC è l'immagine sotto B del sottospazio immagine di C, quindi se Im C ha dimensione al più n, applicare la matrice B potrà mandare a spasso quanto vuole questo sottospazio ma non potrà mai farlo crescere di dimensione. []

Dimostrazione del tuo problema nel caso n dispari: supponiamo per assurdo che ci siano più di n clubs, quindi almeno n+1. Prendiamo A=la matrice nx(n+1) che ha come i-esima colonna il "vettore di incidenza" dell'i-esimo club (cioè: numeriamo gli abitanti e i club, e poniamo a_{ij}=1 sse l'i-esimo abitante sta nel club j). Ora, dalle condizioni dell'ipotesi sappiamo che A^TA = ee^T-I (prova a farti i prodotti riga per colonna uno per uno e viene), dove il LHS e il RHS hanno dimensione n+1 (pari quindi). Qual è il rango del RHS? n+1 (per il lemma 1). Qual è il rango del LHS? Al più n (per il lemma 2, perché il rango di A è al più n).

Dimostrazione del tuo problema nel caso n pari (questa è nuova di questo post, spero che funzioni): supponiamo per assurdo che ci siano n clubs o più, e costruiamo la matrice A di dimensione nxn fatta accostando i vettori di incidenza dei primi n clubs (come sopra). e^TA=0, perché ogni colonna ha un numero pari di uni (dall'ipotesi). Quindi A non ha rango massimo. D'altra parte, come prima abbiamo A^TA=ee^T-I (entrambi i membri di dimensione n pari). Il RHS ha rango massimo per il lemma 1; il LHS non ha rango massimo per il lemma 2, quindi assurdo.

Spero che funzioni tutto...
Se hai altri dubbi o se trovi errori non farti problemi a riscrivere!

[dorothyhung]

Grazie mille! ora mi torna tutto e ho capito! sei stato davvero gentile!