PART B Please complete in BLOCK CAPITALS
Student Number Name Signature
This information will not be visible to the marker.
PART A Please complete clearly
Exam Number
as shown on your university card
Proofs & Problem Solving
MATH08059
Friday 12 May 2023
13:00–15:00
Number of questions: 8
Total number of marks: 100
IMPORTANT PLEASE READ CAREFULLY
Before the examination
1. Put your university card face up on the desk.
2. Complete PART A and PART B above. By completing PART B you are accepting the
University Regulations on student conduct in an examination (see back cover).
3. Complete the attendance slip and leave it on the desk.
4. In this examination, candidates are allowed to have three sheets (six sides) of A4 paper with
whatever notes they desire written or printed on one or both sides of the paper. Magnifying
devices to enlarge the contents of the sheets for viewing are not permitted. No further notes,
printed matter or books are allowed.
5. A scientific calculator is permitted in this examination. It must not be a graphic calculator. It
must not be able to communicate with any other device.
During the examination
1. Write clearly, in ink, in the space provided after each question. If you need more space then
please use the extra pages at the end of the examination script or ask an invigilator for
additional paper.
2. Attempt all questions.
3. If you have rough work to do, simply include it within your overall answer – put brackets at the
start and end of it if you want to highlight that it is rough work.
At the end of the examination
1. This examination script must not be removed from the examination venue.
2. There are extra pages for working at the end of this examination script. If used, you should
clearly label your working with the question to which it relates.
3. Additional paper and graph paper, if used, should be attached to the back of this examination
script. Write your examination number on the top of each additional sheet.
[Do not write on this page]
MATH08059 Do not write above this line May 2023
1. Let M be the set {n ∈ N : n > 1}. Let P be the statement
(∀n ∈ N) (n ∈ M ) ∧ (∀a, b ∈ M )(n ̸= ab) =⇒ (∃c ∈ N)(n = c2 ) .
(a) Find the logical negation ¬P of P , simplifying fully. Your final answer should consist of
symbols only (no words).
[5 marks]
(b) Now express ¬P in words only (no symbols), as simply as possible.
[3 marks]
(c) Describe the set
A = {n ∈ N : (n ∈ M ) ∧ (∀a, b ∈ M )(n ̸= ab) ∧ (∃c ∈ N)(n = c2 )}
as simply as possible, justifying your answer.
[3 marks]
[Total for this question: 11 marks]
[Space for working continues. . . ]
Page 1 of 26 [Please turn over]
MATH08059 Do not write above this line May 2023
If you have used additional space for working then please tick here:
Page 2 of 26
MATH08059 Do not write above this line May 2023
2. (a) By induction, prove that
n
X 1 √
√ ⩾ n,
k=1 k
for every integer n ⩾ 1.
[8 marks]
(b) Does the infinite series
∞
X 1
√
k=1 k
converge? Justify your answer.
[3 marks]
[Total for this question: 11 marks]
[Space for working continues. . . ]
Page 3 of 26 [Please turn over]
MATH08059 Do not write above this line May 2023
[Space for working continues. . . ]
Page 4 of 26
MATH08059 Do not write above this line May 2023
If you have used additional space for working then please tick here:
Page 5 of 26 [Please turn over]
MATH08059 Do not write above this line May 2023
3. (a) Find the value of the following limit:
2n2 + 4n − 3
lim .
n→∞ 4n2 − 3n cos(n)
Prove your answer using the ϵ-N definition of a limit (without using any rules for limits).
[10 marks]
(b) Complex-valued sequences and their limits can be defined by just replacing real numbers with
complex numbers in the relevant definitions. In detail:
A complex-valued sequence is an ordered list (zn )∞ n=1 such that for each n ∈ N, zn ∈ C. A
complex-valued sequence (zn )∞n=1 is defined to converge to a limit w ∈ C if for every ϵ > 0,
there is an N > 0 such that for every n > N , |zn − w| < ϵ. Here |zn − w| denotes the modulus
of the complex number zn − w.
Prove that if (zn )∞
n=1 converges to a limit w ∈ C, then the real-valued sequence (xn )n=1
∞
converges to u, where xn denotes the real part of zn for each n ∈ N and u denotes the real
part of w.
[6 marks]
[Total for this question: 16 marks]
[Space for working continues. . . ]
Page 6 of 26
MATH08059 Do not write above this line May 2023
[Space for working continues. . . ]
Page 7 of 26 [Please turn over]
MATH08059 Do not write above this line May 2023
If you have used additional space for working then please tick here:
Page 8 of 26
MATH08059 Do not write above this line May 2023
4. (a) Use the Euclidean algorithm to find gcd(290, 333) and express gcd(290, 333) as an integer
linear combination of 290 and 333.
[4 marks]
(b) Suppose that
29
0.a + [Link] = ,
33
where a, b ∈ {0, 1, . . . , 9} are not necessarily distinct (recall that 0.a and [Link] denote periodic
decimal numbers). Find the values of a and b.
[10 marks]
[Total for this question: 14 marks]
[Space for working continues. . . ]
Page 9 of 26 [Please turn over]
MATH08059 Do not write above this line May 2023
[Space for working continues. . . ]
Page 10 of 26
MATH08059 Do not write above this line May 2023
If you have used additional space for working then please tick here:
Page 11 of 26 [Please turn over]
MATH08059 Do not write above this line May 2023
5. Find all rectangles with integer side lengths whose area equals their perimeter.
[Total for this question: 7 marks]
[Space for working continues. . . ]
Page 12 of 26
MATH08059 Do not write above this line May 2023
If you have used additional space for working then please tick here:
Page 13 of 26 [Please turn over]
MATH08059 Do not write above this line May 2023
6. (a) Does there exist at least one solution to 2023x = 20 mod 23? Give a proof.
[4 marks]
(b) Show that x = 8 is a solution to x2023 + 20 = 0 mod 23.
[5 marks]
(c) For the equation
x100 + 3x99 + 45x50 + 9x2 + 27x + 1 = 0,
are there any integer solutions? Give a proof.
[5 marks]
[Total for this question: 14 marks]
[Space for working continues. . . ]
Page 14 of 26
MATH08059 Do not write above this line May 2023
[Space for working continues. . . ]
Page 15 of 26 [Please turn over]
MATH08059 Do not write above this line May 2023
If you have used additional space for working then please tick here:
Page 16 of 26
MATH08059 Do not write above this line May 2023
7. A box contains 10 red balls, labelled r1 , r2 , . . . , r10 , and 10 blue balls, labelled b1 , b2 , . . . , b10 .
(a) How many distinct subsets of 10 balls can we obtain from the box?
[2 marks]
(b) How many distinct subsets of 10 balls taken from the box contain exactly 3 red balls?
[3 marks]
(c) Using a combinatorial argument, prove that
n
!2
2n
!
n
=
X
,
n t=0
t
for every n ∈ N.
[7 marks]
[Total for this question: 12 marks]
[Space for working continues. . . ]
Page 17 of 26 [Please turn over]
MATH08059 Do not write above this line May 2023
[Space for working continues. . . ]
Page 18 of 26
MATH08059 Do not write above this line May 2023
If you have used additional space for working then please tick here:
Page 19 of 26 [Please turn over]
MATH08059 Do not write above this line May 2023
8. Let A, X and Y be sets. Given functions f : A → X and g : A → Y , we can define a function
(f, g) : A → X × Y by (f, g)(a) = (f (a), g(a)) for all a ∈ A.
(a) If f and g are injective, must (f, g) be injective? Give a proof or counterexample.
[4 marks]
(b) If f and g are surjective, must (f, g) be surjective? Give a proof or counterexample.
[5 marks]
(c) Given subsets S ⊆ X and T ⊆ Y , prove that (f, g)−1 (S × T ) = f −1 (S) ∩ g −1 (T ).
[6 marks]
[Total for this question: 15 marks]
[Space for working continues. . . ]
Page 20 of 26
MATH08059 Do not write above this line May 2023
[Space for working continues. . . ]
Page 21 of 26 [Please turn over]
MATH08059 Do not write above this line May 2023
If you have used additional space for working then please tick here:
Page 22 of 26 [End of questions]
MATH08059 Do not write above this line May 2023
This is an extra page for working. Please indicate clearly the question number to which your working
relates, otherwise your working may not be marked.
Page 23 of 26
MATH08059 Do not write above this line May 2023
This is an extra page for working. Please indicate clearly the question number to which your working
relates, otherwise your working may not be marked.
Page 24 of 26
MATH08059 Do not write above this line May 2023
This is an extra page for working. Please indicate clearly the question number to which your working
relates, otherwise your working may not be marked.
Page 25 of 26
MATH08059 Do not write above this line May 2023
This is an extra page for working. Please indicate clearly the question number to which your working
relates, otherwise your working may not be marked.
Page 26 of 26
[Do not write on this page]
Exam Hall Regulations
The following is a copy of a Notice which is displayed in Edinburgh University Examination Halls for the
information of students and staff.
The University of Edinburgh Exam Hall Regulations
1. An examination attendance sheet is laid on the desk for each student to complete upon arrival. These
are collected by an invigilator after thirty minutes have elapsed from the start of the examination.
Students are not normally allowed to enter the examination hall more than thirty minutes after the start
of the examination.
2. Students arriving after the start of the examination are required to complete a “Late arrival form” which
requires them to sign a statement that they understand that they are not entitled to any additional time.
Students are not allowed to leave the examination hall less than thirty minutes after the
commencement of the examination or within the last fifteen minutes of the examination.
3. Books, papers, briefcases and cases must be left at the back or sides of the examination room. It is an
offence against University discipline for a student to have in their possession in the examination any
material relevant to the work being examined unless this has been authorised by the examiners.
4. Students must take their seats within the block of desks allocated to them and must not communicate
with other students either by word or sign, nor let their papers be seen by any other student.
5. Students are prohibited from deliberately doing anything that might distract other students. Students
wishing to attract the attention of an invigilator shall do so without causing a disturbance. Any student
who causes a disturbance in an examination room may be required to leave the room, and shall be
reported to the University Secretary.
6. Personal handbags must be placed on the floor at the student’s feet; they should be opened only in full
view of an invigilator.
7. An announcement will be made to students that they may start the examination. Students must stop
writing immediately when the end of the examination is announced.
8. Answers should be written in the script book provided. Rough work, if any, should be completed within
the script book and subsequently crossed out. Script books must be left in the examination hall.
9. During an examination, students will be permitted to use only such dictionaries, other reference books,
computers, calculators and other electronic technology as have been issued or specifically authorised
by the examiners. Such authorisation must be confirmed by the Registry.
10. The use of mobile telephones is not permitted and mobile telephones must be switched off during an
examination.
11. It is an offence against University discipline for any student knowingly
• to make use of unfair means in any University examination
• to assist a student to make use of such unfair means
• to do anything prejudicial to the good conduct of the examination, or
• to impersonate another student or allow another student to impersonate them
12. Students will be required to display their University Card on the desk throughout all written degree
examinations and certain other examinations. If a card is not produced, the student will be required to
make alternative arrangements to allow their identity to be verified before the examination is marked.
13. Smoking and eating are not allowed inside the examination hall.
14. If an invigilator suspects a student of cheating, they shall impound any prohibited material and shall
inform the Examinations Office as soon as possible.
15. Cheating is an extremely serious offence, and any student found by the Discipline Committee to have
cheated or attempted to cheat in an examination may be deemed to have failed that examination or
the entire diet of examinations, or be subject to such penalty as the Discipline Committee considers
appropriate.
