Discrete-math 26

Discrete-math 26

Exam 2024 (2)

A is a set,|A|≥1Let f:P(A)×P(A)→P(P(A))∀B,C⊆A:f(B,C)={D|D⊆B∩C}Prove or disprove:1.It is possible that f is injective2.It is possible that f is surjectiveDisproof for 1:Let AA≠∅⟹∃a∈Af(∅,{a})=f({a},∅)=P(∅)={∅}⟹∀A:f is not injectiveDisproof for 2:Let AA≠∅⟹∃a∈A⟹{a}∈P(A)⟹{{a}}∈P(P(A))∀X:∅∈P(X)∀B,C⊆A:f(B,C)=P(B∩C)⟹∅∈f(B,C)⟹f(B,C)≠{{a}}⟹∀A:f is nor surjective

Exam 2024 (3)

Let A be a setLet f:A→ALet B⊆ALet B1=B,∀n∈N:Bn+1=f−1[Bn]1.Prove: if for any B⊆A:⋂n∈NBn=∅ then f has no fixed points2.Prove or disprove: f has no fixed points⟹∀B⊆A:⋂n∈NBn=∅Proof for 1:If A is an empty set, then f is an empty function which has no fixed pointsLet A≠∅Let ∀B⊆A:⋂n∈NBn=∅Let f has a fixed point xLet B={x}⟹x∈f[B]Base case. Let n=1x∈B⟹x∈B1Induction step. Let x∈BnBn+1=f−1[Bn]x∈Bn,f(x)=x⟹x∈f−1[Bn]=Bn+1⟹By induction: x∈⋂n∈NBn⟹⋂n∈NBn≠∅−Contradiction!⟹f has no fixed pointsDisproof for 2:Let A=NLet f(n)=2nLet B=NBase case. Let n=1B1=B=NInduction step. Let Bn=NBn+1=f−1[Bn]=f−1[N]Let x∈f−1[N]⟹x∈N⟹f−1[N]⊆NLet x∈N⟹2x∈N⟹f(x)=2x⟹x∈f−1[{2x}]⊆f−1[N]⟹N⊆f−1[N]⟹Bn+1=f−1[N]=N⟹By Induction ∀n∈N:Bn=N⟹⋂n∈NBn=N

Exam 202?

Let A=[n],n∈NLet G=(V,E) be a simple graphV=P(A)E={{X,Y}|X,Y⊆A∧[(X⊂Y)∨(Y⊂X)]}1.Find |V|2.Find |E|3. Show that there are exactly two vertices with odd degreeSolution for 1:|V|=|P(A)|=2|A|=2nSolution for 2:Let k∈[n]Let X∈V|P(X)|=2kNumber of supersets of X is 2n−kX∈P(X),X is a superset of X⟹deg(X)=2k+2n−k−2∑X∈Vdeg(X)=∑k=0n(nk)(2k+2n−k−2)⟹|E|=12⋅∑k=0n(nk)(2k+2n−k−2)=12(∑k=0n2k(nk)+∑k=0n2n−k(nk)−2∑k=0n(nk))By binomial theorem: |E|=12(3n+3n−2n+1)=3n−2nSolution for 2:deg(X)=2k+2n−k−2Let k≠0,k≠n⟹deg(X) is evenLet k=0⟹X=∅,deg(X)=2n−1Let k=nX=[n],deg(X)=2n−1⟹There are exactly two vertices of odd degree: ∅,[n]