Exam 2024 (C)

1b

Let G=(V,E) be a tree with |V|≥2Prove: ∃v∈V such that removing vertex v and all its edges will result in a graphG′=(V∖{v},E′)such that in all connected components of G′ there is at most |V|2 verticesProof:Let ∃ tree G=(V,E):∀v∈V:∃ connected component of G′=(V∖{v},E′):|[u]∼|>n2

2a

Let ALet f:A→ALet g:P(A)→P(A),g(B)=f−1[B]Prove or disprove: g is surjective⟹f is surjectiveDisproof:Let f:N→N,f(n)=n+1f is not surjectiveLet C∈P(N)Let B={n+1|n∈C}⊆Ng(B)=f−1[B]=C

2b

Let ALet f:A→ALet g:P(A)→P(A),g(B)=f−1[B]Prove or disprove: g is surjective⟹f is injectiveProof:Let g be surjective

3

Let f:N→N,{f(n)<nn≠1f(n)≤nn=1

3a

Prove: ∀n∈N:∃k∈N:∀m≤n:fk(m)=1Proof:{f(n)<nn≠1f(n)≤nn=1⟹[f(n)=n⟹f(n)=n=1]Let n∈NLet k=nLet m≤nfn(m)≤fn−1(m)≤⋯≤f(m)≤mLet ∀i∈[1,n]:fi(m)<fi−1(m)⟹|{fn(m),fn−1(m),…,f(m),m}|=n+1>|[m]|=m{fn(m),fn−1(m),…,f(m),m}⊆[m]−Contradiction!⟹∃i∈[1,n+1]:fi(m)=fi−1(m) then f(fi−1(m))=fi−1(m)=1⟹fn+1(m)=fn(m)=⋯=fi−1(m)=1⟹fk(m)=1

3b

Is there k∈N:∀n∈N:fk(n)=1?Solution:Let f(n)={n−1n>11n=1Let k∈NLet n=k+2⟹f(n)=k+1,f2(n)=k,…,fk(n)=2≠1⟹∀k∈N:∃n∈N:fk(n)≠1⟹The answer is no, such k does not exist

4a

How many ways there are to sit 30 students in two circles, such that in one circle there areexactly 20 students and in the other there are exactly 10 students?Solution:Let us first choose 10 students to sit in the second circle(3010)Let us then arrange students in the first circle:19!Let us then arrange students in the second circle:9!⟹The answer is: (3010)19!9!=30!20⋅10=30!200

4b

How many ways there are to sit 30 students in two circles?Solution:Let one of the circle have 0 peopleThen there are 29! ways to arrange 30 students in a circleLet us choose 1≤i≤29 people to go to the first circle29!+29!+∑i=129(30i)(30−i−1)!(i−1)!=∑i=12930!(30−i)i+2⋅29!

4c

How many ways there are to rearrange 30 students in a circle such thatfor each student the left neighbor is new?Solution:Let us enumerate students in the circle from 1 to 30Let us choose number 1≤i≤30Let us count the number of ways to sit 30 students in a way thatneighbors (i,(i+1)mod30) sit as they wereLet Ai={ ways to arrange students such that (i,(i+1)mod30) sit as they were }|Ai|=(30−1−1)!Let us now choose k such numbers1≤i1≤i2≤⋯<ik≤30|Ai1∩Ai2∩⋯∩Aik|=(30−1−k)!⟹By the Inclusion-Exclusion principle: |⋃i=130Ai|=∑k=130(−1)k−1(30k)(30−1−k)!Total number of ways to sit 30 students in a circle is 29!⟹The answer is: 29!−∑k=130(−1)k−1(30k)(30−1−k)!=∑k=030(−1)k(30k)(29−k)!

4d

How many ways there are to arrange 30 students in a circle such thatEach student has a number and only one student has a number bigger than his neighborsSolution:Note that this special student can only have number 3029 can only be near 30⟹There are 2 ways28 can only be near 29 or 30⟹There are also 2 ways27 can only be near 28 or one of (29,30)⟹There are also 2 waysAnd so on until we get to 1 which can only be placed between 2 and the other number⟹The answer is 228

5

Let X be a setR≠∅⊆P(X) is called a ring if ∀A,B∈R:[A∩B∈R]∧[A△B∈R]

5a

Let R⊆P(X) be a ringProve: ∃K∈R:∀A∈R:A△K=AProof:∀A,B∈R:[A∩B∈R]∧[A△B∈R]R≠∅⟹∃C∈R⟹(C∩C∈R)∧(C△C∈R)⟹C∈R∧∅∈R∀D:D△∅=D⟹∃K=∅∈R:∀A∈R:A△K=A△∅=A

5b

Let X be a setLet {Ri}i∈I be a family of ringsProve: ⋂i∈IRi is a ringProof:Let A,B∈⋂i∈IRi⟹∀i∈I:A,B∈Ri⟹∀i∈I:(A∩B∈Ri)∧(A△B∈Ri)⟹(A∩B∈⋂i∈IRi)∧(A△B∈⋂i∈IRi)⟹⋂i∈IRi is a ring

5c

Let R⊆P(X) be a ringProve: ∀A,B∈R:(A∖B∈R)∧(A∪B∈R)Proof:∀A,B∈R:[A∩B∈R]∧[A△B∈R]Let A,B∈RA∩B∈R,A△B=(A∪B)∖(A∩B)∈R(A△B)△(A∩B)=A∪B⟹A∪B∈R(A∩B)△A=((A∩B)∪A)∖(A∩B∩A)=A∖(A∩B)A∖(A∩B)={x|x∈A∧x∉A∩B}={x|x∈A∧(x∉A∨x∉B)}=={x|(x∈A∧x∉A)∨(x∈A∧x∉B)}=A∖B⟹A∖B∈R

5d

Let R⊆P(X)R is called an algebra if ∃E∈R:∀A∈R:A∩E=ALet R={A∈P(X)|A is finite}Prove: R is algebra⟺X is finiteProof:Let X be finite⟹R=P(X) is finite⟹X∈R∀A∈P(X):X∩A=A⟹R is an algebraLet R be an algebra⟹∃E∈R:∀A∈R:A∩E=AE∈R⟹E is finiteLet T={{x}|x∈X}T⊆R⟹∀{x}∈T:E∩{x}={x}⟹∀x∈X:{x}⊆E⟹x∈E⟹X⊆E⟹X is finite