Cittá dispari al contrario

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
dorothyhung
Messaggi: 39
Iscritto il: 25 ott 2006, 17:06

Cittá dispari al contrario

Messaggio da dorothyhung » 29 mag 2008, 15:18

Supponiamo di avere una cittá con $n$ abitanti. In questi cittá si sono dei club, che soddisfano le seguenti regole:

1. ogni club ha un numero di membri pari
2. presi due club il numero di membri che fa parte di entrambi é sempre dispari

Provare che se $n$ é dispari ci sono al massimo $n$ club, mentre se $n$ é pari ce ne sono al massimo $n-1$.

Sto cercando di provare questo, ma non riesco a formalizzare... qualcuno saprebbe aiutarmi?

Avatar utente
Gargantua
Messaggi: 20
Iscritto il: 03 set 2006, 22:24
Località: Sassari

Messaggio da Gargantua » 29 mag 2008, 17:24

Se con $n$ intendi un qualunque numero a tre cifre con la cifra delle unità uguale a quella delle centinaia, sul primo punto ci sono (tra un po' posto la dimostrazione), ma il secondo è falso, perché il numero massimo non è $n-1$, ma $n$ -1; infatti consideriamo la seguente situazione, in cui $n$ è pari:

- costruiamo clubs di due membri, in modo tale che il primo membro sia comune a tutti i clubs, mentre il secondo membro vari per ogni club; insomma c'è un abitante che appartiene a tutti i clubs del villaggio, mentre tutti gli altri abitanti appartengono a un club diverso, formato da loro stessi e dall'abitante "prezzemolino".

questo scenario rispetta le due regole, perché i clubs hanno tutti un numero pari di membri (in particolare 2), mentre presi a caso due clubs sicuramente il numero di abitanti in comune è dispari (in particolare 1); ma i clubs sono ben $n$ -1

Ho capito male il problema?
Come osiamo parlare di leggi del caso? Non è forse il caso l'antitesi di ogni legge?
Gauss

Avatar utente
Desmo90
Messaggi: 160
Iscritto il: 17 lug 2007, 16:23
Località: sulla retta critica a nord di 1/2

Messaggio da Desmo90 » 29 mag 2008, 17:35

gargantua ha scritto:Se con $n$ intendi un qualunque numero a tre cifre con la cifra delle unità uguale a quella delle centinaia
no, penso che $ sia solo il simbolo che viene usato di solito per scrivere le formule in latex(negli altri forum)[/quote]
Quindi $ $n $ è un numero naturale qualsiasi.

Avatar utente
Gargantua
Messaggi: 20
Iscritto il: 03 set 2006, 22:24
Località: Sassari

Messaggio da Gargantua » 29 mag 2008, 18:55

Ah, grazie!!! :D
Ora torna tutto.
Come osiamo parlare di leggi del caso? Non è forse il caso l'antitesi di ogni legge?
Gauss

dorothyhung
Messaggi: 39
Iscritto il: 25 ott 2006, 17:06

Messaggio da dorothyhung » 29 mag 2008, 19:00

sì scusatemi! dovevo scriverlo diversamente!

dorothyhung
Messaggi: 39
Iscritto il: 25 ott 2006, 17:06

Messaggio da dorothyhung » 29 mag 2008, 19:05

sì scusatemi! dovevo scriverlo diversamente!

bestiedda
Messaggi: 213
Iscritto il: 15 nov 2007, 20:20

Messaggio da bestiedda » 29 mag 2008, 19:25

solo la prima parte:

noto innanzitutto che se ci sono elementi condivisi da tutti i club, allora il numero di club è sicuramente inferiore al numero di elementi: infatti ogni club potrebbe condividere con gli altri clubs SOLAMENTE quegli elementi condivisi da tutti. Chiamando $ x $ il numero di elementi in comune, $ y $ il numero di club e $ k $ il numero di elementi all'interno di ogni club, allora abbiamo che $ x+(k-x)y $ è il numero totale di elementi, e $ x+(k-x)y>y $ sempre.
Quindi abbiamo che non ci devono essere elementi condivisi da tutti i club. Per fare in modo che questo accada e che $ y=n $ dobbiamo avere $ k=n-1 $. Infatti: Chiamiamo gli abitanti 1,2,3......n; il primo gruppo contiene $ 1,2,3....n-1 $; il secondo gruppo contiene $ 2,3,4.....n $; il terzo contiene$ 3,4,5.....n,1 $ eccetera. Il n-esimo gruppo conterrà $ n,n+1,n+2....k-1 $. Il numero di clubs è quindi $ n $. Se avessimo $ k<n-1 $ avremmo che sicuramente ci sarebbe $ y<n $ perchè il terzo gruppo deve avere elementi in comune col primo e quindi non "parte" da $ 3 $ ma da un numero molto più alto


che faticaccia.....chiedo preventivamente scusa a tutti coloro che rimarranno orripilati nel leggere la mia spiegazione :lol: ma sono del tutto nuovo a questo tipo di problemi e ho anche grosse difficoltà nel formalizzare. Apprezzate lo sforzo :lol:

edit: mannaggia mi rendo solo dopo la dimostrazione di gargantuà del mio errore: credevo che ogni club dovesse contenere un numero uguale di elementi :evil:
Ultima modifica di bestiedda il 29 mag 2008, 20:23, modificato 1 volta in totale.
marco

Avatar utente
Gargantua
Messaggi: 20
Iscritto il: 03 set 2006, 22:24
Località: Sassari

Messaggio da Gargantua » 29 mag 2008, 20:13

La mia dimostrazione funziona così: prima dimostrerò che non possono esistere dei "sottoclubs", cioè dei clubs in cui tutti i membri appartengono anche a un club più grande (a); poi dimostrerò che per massimizzare il numero di clubs dobbiamo costruire solo clubs di 2 membri (b); infine dimostrerò che c'è solo un modo di formare clubs siffatti e che questo modo porta a un numero di clubs come in soluzione (c).

a) Iniziamo con l'evidenziare che non possono esistere sottoinsiemi, cioè i membri di un club non possono appartenere anche tutti a un club più grande; infatti in quel caso, chiamando $ a $ il numero di membri del club più piccolo e $ b $ il numero di membri in comune ai due club, avremmo $ a = b $, un assurdo, dal momento che sappimao che $ a $ deve essere pari e $ b $ dispari.

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.

c) Fissàti questi due punti, vediamo come è possibile disporre i nostri clubs da due membri affinché ogni club abbia un membro in comune con tutti gli altri.
Disponiamo il primo club; il secondo avrà sovrapposizione 1 con il primo; il terzo lo possiamo disporre in due modi: 1) se abbiamo consumato gli abitanti, lo formiamo unendo i membri non sovrapposti degli altri due club 2) se abbiamo ancora abitanti, dobbiamo obbligatoriamente disporlo come il secondo; ad ogni nuovo club ci si ripropone la scelta vista per il terzo, finchè non arriviamo a consumare gli abitanti; a quel punto, se i club formati fino a quel punto (n-1) sono pari (che equivale a dire che n è dispari), formiamo l'ultimo club come in 1) e otteniamo $ n-1+1 = n $ club, mentre se i club formati fino a quel punto sono dispari (che equivale a dire che n è pari), non possiamo formare altri club e in totale ne abbiamo realizzati $ n-1 $.

Spero di essere stato sufficientemente chiaro (anche se non ci giurerei...); sarebbe molto più semplice una dimostrazione grafica. :P
Come osiamo parlare di leggi del caso? Non è forse il caso l'antitesi di ogni legge?
Gauss

dorothyhung
Messaggi: 39
Iscritto il: 25 ott 2006, 17:06

Messaggio da dorothyhung » 30 mag 2008, 08:18

Grazie, sì questa dimostrazione è ok, pensavo però che forse si potrebbero usare dei vettori di incidenza, per dimostrarlo in modo più formale, qualcuno ha un'idea?

Avatar utente
Ratio
Messaggi: 62
Iscritto il: 29 nov 2007, 20:22
Località: Una realtà quadridimensionale (forse)

Messaggio da Ratio » 30 mag 2008, 10:09

Scusate, è la prima volta che posto una soluzione per combinatoria quindi posso probabilmente dire castronerie, ma ho usato un altro metodo:

Cosideriamo m il numero di club e $ f_1,f_2,f_3,...,f_m $ il numero di membri di ogni club, allora per massimizzare il numero di club dovremmo avere che $ f_1=f_2=f_3=...=f_m $. Ora, se n è dispari $ f_m=n-1 $ perché pari e necessariamente il più vicino possibile a n, percui il numero di club è uguale a $ {n \choose n-1} = n $.
Se n è pari $ f_m=n-2 $ perché necessariamente maggiore di n e il più vicino possibile ad n. Tuttavia possiamo distribuire nei club solo n-1 abitanti della città, perchè altrimenti non è possibile distribuendone in numero pari avere un numero dispari di membri in comune per qualsiasi coppia di club scelti. Percui il numero di club è dato da $ {n-1 \choose n-2} = n-1 $
Spero di non aver detto stupidaggini. Fatemi sapere :lol:
"L'apprendere molte cose non insegna l'intelligenza"
Eraclito

fph
Site Admin
Messaggi: 3682
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 30 mag 2008, 14:03

dorothyhung ha scritto:Grazie, sì questa dimostrazione è ok, pensavo però che forse si potrebbero usare dei vettori di incidenza, per dimostrarlo in modo più formale, qualcuno ha un'idea?
C'è un problema molto simile che si fa in modo eccezionalmente bello ma non elementare, se hai fatto un corso di geometria/algebra lineare all'università provo a spiegartelo. La soluzione si adatta facilmente per fare il caso n dispari del tuo problema, per n pari non so ma è meno immediato.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

dorothyhung
Messaggi: 39
Iscritto il: 25 ott 2006, 17:06

Messaggio da dorothyhung » 30 mag 2008, 15:23

Sì ho fatto i corsi che dici, me lo potresti spiegare? Grazie

fph
Site Admin
Messaggi: 3682
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 30 mag 2008, 17:41

Ok... adesso vediamo se gli altri moderatori me lo spostano in MNE :D
Dunque, il problema che ho visto io era:
I "clubs" questa volta sono tali che ognuno ha un numero dispari di membri e due clubs hanno intersezione pari; dimostrare che i clubs al massimo sono n.
Soluzione "eccezionalmente bella": chiamiamo n il numero di componenti della città e m il numero di clubs; sia $ \mathbb \mathbb F_2 $ il campo finito con due elementi; chiamiamo A la matrice in $ \mathbb F_2^{n \times m} $ che ha A_ij=1 se l'abitante numero i sta nel club numero m. Le condizioni del problema ci dicono che $ A^TA=I_m $ ($ I_m $=matrice identità mxm, ocio che i conti sono in $ F_2 $). Il rango del RHS è m, mentre il rango del LHS è al più min(n,m), quindi se n<m ho un assurdo.
(se qualcosa non è chiaro chiedi, sto dando per scontati parecchi lemmetti sul rango).
Ora, il tuo problema nel caso n dispari dovrebbe essere uguale: la matrice al RHS viene ee^T-I (con e si indica di solito il vettore di tutti uni) ed è di rango massimo (in un vecchio thread si era parlato di come calcolare il determinante di una matrice fatta così, se vuoi te lo recupero), quindi si conclude nello stesso modo. Per n pari la matrice non ha rango massimo (il vettore e sta nel suo ker) e non funziona più. Si potrebbe forse rimediare "orlando" la matrice opportunamente o facendo a mano una specie di decomposizione di Cholesky del RHS, ma non ci ho fatto troppi conti sopra.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

fph
Site Admin
Messaggi: 3682
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 30 mag 2008, 18:07

hmm... scusa, probabilmente ho scritto un paio di fesserie con pari e dispari, diciamo che correggo il post sopra così:
sia n dispari; supponiamo per assurdo di poter avere n+1 club diversi, allora costruendo A con solo questi clubs (m=n+1), A^TA=ee^T-I di dimensione n+1 pari, che ha rango massimo, assurdo perché A^TA ha rango al più n.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

dorothyhung
Messaggi: 39
Iscritto il: 25 ott 2006, 17:06

Messaggio da dorothyhung » 02 giu 2008, 08:51

Grazie mille per la dimostrazione che hai postato, questa mi è chiara, solo che ieri ho provato a lungo a cercare di dimostrare il mio caso, ma non riesco a conlcudere, avresti mica altri suggerimenti?

Rispondi