MTH4140 Home

MTH4140: Midterm 1 Practice 3

Problem 1

Which of the following statements are true?

  • (A) If \( R \) is a relation on \( A \), then \( R\times R = A\times A\times A\times A \).

  • (B) A transitive relation on the set \( S \) must be a subset of \( S\times S \).

  • (C) If \( f:A\to A \) is a function then the set \( V=\left\{\left(x,f(x)\right):x\in A\right\} \) is a relation on \( A \).

  • (D) If \( P \) is a reflexive relation on \( Q \) then \( Q \) is a symmetric relation on \( P \).

  • (E) If \( P \) is a relation on \( Q \) then \( P\times Q \) is also a relation on \( Q \).

Problem 2

Provide an example of a set \( S \) of \( 3 \) elements and a function \( f:S\times S\to S \) that is not surjective.

Problem 3

Determine which pairs of graphs below are isomorphic.

\(\quad\) \(\quad\)

Problem 4

Which of the pictures below can be drawn without lifting the pen from the paper and without tracing the same line twice?

\(\quad\) \(\quad\)

Problem 5

A sequence of integers \( \left(a_n\right)_{n=1}^{\infty} \) satisfies \( a_1=6 \), \( a_2=20 \), and \( a_{n+2}=2a_{n+1}+8a_n \) for \( n\geq 1 \). Prove that \[ a_n=\frac{4 \cdot 4^n-{ } \left(-2\right)^n }{3} \quad\mbox{ for every } n\geq 1.\]

Problem 6

Assume that the set \( V \) is defined as \( V =\left\{ 1,2,\dots, 43 \right\}^{6} \). Assume that \( E \) is the set of all pairs \( (u,v) \) such that \( u=\left(a_1, \dots, a_{6}\right) \) and \( v=\left(b_1,b_2, \dots, b_{6}\right) \) are elements of \( V \) for which the number \( \left(a_1-b_1\right)\cdot\left(a_2-b_2\right) \cdots \left(a_{6}-b_{6}\right) \) is not divisible by \( 7 \). Determine whether the graph \( (V,E) \) has a path that visits every edge exactly once.