Description
Problem 1 [10 points]. Let the domain of x be {−5, −3, −1, 1, 3}. Express using negations,
disjunctions, and conjunctions, but without quantifiers, the proposition ∃xP(x).
Problem 1 [10 points]. Negate the statements below so that negation symbols immediately
precedes predicates (e.g., ¬(P(x, y) → Q(x, y)) is not considered correct)
(∃x∀y(P(x, y) → Q(x, y))) → (∀x∀y∃z(P(x, y) → P(y, z))).
Problem 3 [10 points]. Following the greatest common divisor algorithm, find gcd(123, 46).
Show your work.
Problem 4 [20 points]. Prove via induction that for an undirected simple graph with n vertices,
there can be at most |E| =
n(n−1)
2
edges.
2
3
* 1
*
* * *
Problem 5 [5 points]. Recall that the 8-puzzle problem has eight movable pieces
and one empty swap space on a 3×3 game board. What is the size of the state space
if 3 of the pieces are labeled and 5 are unlabeled? That is, the game pieces can be
thought of as being labeled 1, 2, 3, ∗, ∗, ∗, ∗, ∗ (see the figure on the right). You only
need to provide the formula; there is no need to compute the final number.
Problem 6 [15 points]. List all complete graphs and complete bipartite graphs that are
planar. For each graph you list, provide a drawing showing that it is planar.
Problem 7 [10 points]. Give the smallest complete graph that is non-planar. Prove your claim.
[Hint: argue that edge crossings cannot be avoided somehow.]
1 2 3 4 n …
Problem 8 [20 points]. Consider a bar consisting of n numbered squares
(see the figure on the right). You are to break the bar into smaller ones,
each of which must contain one or more complete numbered squares. (1) How many different bars
can be obtained, including the original bar (10 points)? (2) How many possible ways are there
for doing the division (5 points)? Extending the bar to be an n × m bar formed by nm uniquely
numbered squares. We are to obtain smaller rectangular bars consisting of adjacent squares. (3)
How many different bars can be obtained, including the original bar (5 points)? [Hint: for the first
question, think about one different bar at a time and how a unique bar may be obtained.]
Page 1 c Jingjin Yu ◦ Rutgers University
