Gammel Putnam Skriv et svar


Dette spørsmålet er en metode for identifisering og hindring av automatiserte innsendinger.
Smil
:D :) :( :o :shock: :? 8-) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:
BBCode er
[img] er
[flash] er AV
[url] er
Smil er
Emne
   

Utvid visningen Emne: Gammel Putnam

Re: Gammel Putnam

Innlegg mingjun » 29/07-2019 16:34

La $P'=\left\{S|S\in P_n,|S|=n-1\right\}$. Vi starter med observasjonen at $f$ er unikt bestemt av verdiene til $f(S), S\in P'$ samt $f\left(\left\{1,2,\dots,n\right\}\right)$. Det er fordi enhver mengde i $P_n$ med størrelse mindre enn $n$ kan uttrykkes som et unikt snitt mellom mengder i $P'$, og at $$f(S_1\cap S_2 \cap \dots \cap S_k)=\min\left(f(S_1),f(S_2 \cap \dots \cap S_k)\right)=\dots =\min\left(f(S_1),f(S_2),f(S_3),\dots,f(S_k)\right).$$ Man kan overbevise seg selv om at den genererte $f$ stemmer overens med definisjonene pga de gitte grunnene.

Nå trenger vi kun å telle antall gyldige verdier $f(S), S\in P'$ og $f\left(\left\{1,2,\dots,n\right\}\right)$. Den eneste måten et sett verdier ikke kan være gyldige på er hvis $f\left(\left\{1,2,\dots,n\right\}\right)<f(S), S\in P'$, ettersom snittet av de to mengdene er nøyaktig $S$ og vi får $f(S)=f(\left(\left\{1,2,\dots,n\right\}\cap S\right)=\min\left(f\left(\left\{1,2,\dots,n\right\}\right),f(S)\right)=f\left(\left\{1,2,\dots,n\right\}\right)<f(S)$. Dermed har vi at for hver verdi av $f\left(\left\{1,2,\dots,n\right\}\right)$, må $f(S)$ være ikke større enn nevnte verdi. Følgelig kan vi summere over alle mulige verdier av $j:=f\left(\left\{1,2,\dots,n\right\}\right)$ : $$c\left(n,m\right)=\sum_{j=1}^{m} j^n,$$ siden det er $n$ elementer i $P'$. $\blacksquare$

Gammel Putnam

Innlegg Gustav » 03/07-2019 22:48

La $P_n$ være mengden av delmengder av $\{1,2,...,n\}$. La $c(n,m)$ være antallet funksjoner $f:P_n\to \{1,2,...,m\}$ slik at $f(A\cap B)=\min \{f(A),f(B)\}$.

Vis at $$ c(n,m)=\sum_{j=1}^m j^n$$

Topp