首页 >
> 详细

Compsci 120 The University of Auckland

Assignment 4

Due: Friday, October 30th, by 23.59pm Semester 2, 2020

There are four problems listed below. To get full credit on this assignment, you should pick any

three of them to complete!

Note that you do not have to follow the suggested proof techniques. Any correct proof is worth the

max possible number of points.

The same rules from Assignments 1, 2, and 3 (show all working, late assignments cannot be accepted,

etc.) all still apply here. Best of luck, and enjoy the problems!

1. Direct proofs and proofs by cases.

(a) Let n be a positive integer number. Prove that if p is a prime factor of n

2

, then p is a

factor of n.

(b) Suppose n and x are two positive integers, n > 2. Prove that if n

x ≡ n − 2 (mod n − 1),

then n = 3.

(c) Consider a correct claim with its incorrect proof.

Claim: Prove that n

3 + 5n is divisible by 6 for every positive integer n.

Proof. Because every n can be written in the form 6q + n%6 consider the following 5

cases:

Case 1: n%6 = 1. Then n

3%6 = 13%6 = 1 and 5n%6 = 5. Hence (n

3 + 5n)%6 =

1 + 5 = 6, which is divisible by 6.

Case 2: n%6 = 2. Since n

3 + 5n = n(n

2 + 5) the only way n(n

2 + 5) can be divisible

by 6 is if n

2 + 5 is divisible by 6. Indeed, (n

2 + 5)%6 = n

2%6 + 5%6 = (n%6)2 + 5 =

4 + 5 = 9. The number is not divisible by 6, so this case is not possible.

Case 3: n%6 = 3. Then n

3%6 = 33%6 = 1 and 5n%6 = 3. Hence (n

3 + 5n)%6 =

3 + 3 = 6, which is divisible by 6.

Case 4: n%6 = 4. Then n

3%6 = 43%6 = 4 and 5n%6 = 2. Hence (n

3 + 5n)%6 =

4 + 2 = 6, which is divisible by 6.

Case 5: n%6 = 5. Then n

3%6 = 53%6 = 5 and 5n%6 = 1. Hence (n

3 + 5n)%6 =

5 + 1 = 6, which is divisible by 6.

Since in all the cases n

3 + 5n is divisible by 6 or a case is not possible n

3 + 5n is a multiple

of 6 for every positive integer n.

Find ALL logical mistakes in the proof. You do not need to prove this claim.

2. Proof by contradiction

(a) Given a graph G, define k(G) to be the greatest possible natural number n such that Kn

(the complete graph on n vertices) is a subgraph of G. Recall that the chromatic number

χ(G) of G is the smallest possible number of colours sufficient to color the vertices of G

so that no two adjacent vertices receive the same color (see Assignment 3 Question 3).

Prove that χ(G) ≥ k(G).

(b) Let x, y, z be three integer numbers. Prove that if x2 + y2 = z2, then x is even or y is

even.

1

(c) Consider a correct claim with its incorrect proof.

Claim: Consider the equation x

2+y2−3 = 0. A pair (x0, y0) is called a rational solution

of x2 + y2 − 3 = 0 if

• x0 and y0 are rational;

• x20 + y20 − 3 = 0

The equation x2 + y2 − 3 = 0 has no rational solutions.

Proof. Assume that it is not true that x2 + y2 − 3 = 0 has no rational solutions. That is,

every solution (x, y) of x2 + y2 − 3 = 0 is rational. Consider one of these solutions, say

(a, b), then

• a and b are rational;

• a2 + b2 − 3 = 0

Since a, b are rational there are integer numbers pa, Therefore qb is a multiple

of qa. So there is an integer t, such that qa = tqa.

Now qa = tqa and qb = kqa. It is not possible. Therefore our assumption was incorrect

and x

2 + y

2 − 3 = 0 has no rational solutions.

Find ALL logical mistakes in the proof. You do not need to prove this claim.

3. Proofs by construction

(a) Prove that for any given natural number n > 2 there is a graph G on n vertices with the

following properties:

i. G has exactly (n − 2)(n − 1)

2

many edges;

ii. At least one vertex of G is connected to exactly n − 2 other vertices of G by an edge.

(b) Design an algorithm which, on input a tree T represented in the form of the picture,

outputs a colouring of its vertices with the property that no two adjacent vertices have

the same colour.

Note that the following operations can be perform on a picture of a tree without any

explanation:

• choosing a vertex;

• checking if two vertices are adjacent;

• checking if a vertex is coloured;

• checking if all vertices are coloured;

2

• finding the colour of a vertex;

• finding all neighbours of a vertex.

• colouring a vertex

(c) Consider a correct claim with its incorrect proof.

Claim: For every integer n ≥ 2, there is a graph on 2n vertices which has exactly 4

vertices of degree 2 and (2n − 4) vertices of degree 3.

Proof. Define the graph G on 2n vertices in the following way. Take a cycle graph C2n

and connect vertex i to vertex 2n − i + 1 by an edge for every 2 ≤ i ≤ n − 1.

The resulting graph has all the needed properties. Consider a vertex i, 2 ≤ i ≤ 2n − 1. It

is adjacent to i − 1, i + 1 and 2n − i + 1. Hence the degree of i is 3. Therefore, G satisfies

all the properties.

Find ALL logical mistakes in the proof. You do not need to prove this claim.

4. Mathematical induction

(a) Let x be a non-negative real number. Prove that

(1 + x)

n ≥ 1 + nx

for every natural number n.

(b) Prove that 72n − 1 is a multiple of 24 for every natural n.

(c) Consider a correct claim with its incorrect proof.

Claim: The solution of the following recurrence relation

(a1 = 3, a2 = 5

an+1 = 3an − 2an−1

is an = 2n + 1 for every positive integer n.

Proof. The induction statement P(n) is

(a1 = 3, a2 = 5

an+1 = 3an − 2an−1

Base case: You need to check the formula for n = 1. Indeed, if n = 1, then a1 = 2n+1 =21 + 1 = 3 as needed.

Induction step: Assume that an+1 = 2n+1 + 1 satisfies the recurrence relation then you

need to prove that an = 2n + 1 also satisfies the recurrence relation.

Indeed,

an+1 = 3an −2an−1 = 3(2n + 1)−2(2n−1 + 1) = 3 · 2n + 3−2n −2 = 2 · 2n + 1 = 2n+1 + 1.

The induction step is proved.

By the principle of mathematical induction an = 2n + 1 is the solution of the recurrence

relation for every positive integer n.

Find ALL logical mistakes in the proof. You do not need to prove this claim.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp

- 代写cmpt 214编程、代做programming语言、代写c/C++程序 2020-11-08
- 代写csci 2122课程、代做program编程实验、C++程序语言代写代 2020-11-08
- Fit5032语言编程代做、代写web程序实验、Web、Html程序语言代做 2020-11-08
- Com3503程序编程代做、Java，C++，Python留学生编程代写代写 2020-11-08
- 代写program程序课程、代写c++编程实验、C/C++编程语言代做 代做 2020-11-08
- Data留学生编程代做、代写python程序、Java，C++程序语言代写 2020-11-08
- 代写secj 1023实验编程、Programming程序代做、代写c++语 2020-11-08
- 代写cmpsc 465编程、代做java程序语言、Python，C++编程设 2020-11-07
- 代做mf 703语言编程、代写programming程序、Sql编程语言调试 2020-11-07
- 954246编程设计调试、代做programming程序、C++编程语言代写 2020-11-07
- Pstat 115程序实验代写、R编程语言调试、Data留学生程序代做 代写 2020-11-07
- Com1005课程编程代做、代写python程序、Java，C++程序语言调 2020-11-07
- Tcp留学生程序代写、Java程序设计调试、Java编程语言代写 帮做r语言 2020-11-07
- 代写program语言编程、代做data留学生程序、Python，Java编 2020-11-07
- 代做cosc2666编程、代写programming程序、C/C++程序语言 2020-11-07
- Digital编程设计代写、代做r程序实验、代写r留学生程序 调试matla 2020-11-07
- 代写programming程序实验、R程序语言调试、Data课程编程代做 代 2020-11-07
- Comp104-17B程序代写、代做c++编程实验、C++程序语言调试 帮做 2020-11-07
- Csc8501课程程序代做、C++编程语言调试、代写program编程课程 2020-11-07
- 代写css3留学生程序、代做html、Css编程语言、Data课程程序代做 2020-11-07