Structural Reasoning and Challenge Clinic

Retrieval Prompts

1. State the skeleton of a proof by contradiction.
2. What must you verify for every legal move when using an invariant argument?
3. List the three properties an algorithmic construction must have.
4. What structural observation justifies choosing DP over divide-and-conquer?
5. What is the difference between a constructive and a non-constructive existence proof?

Contradiction Drill

Prove each by contradiction. Write the assumption, the derived impossibility, and the conclusion explicitly:

1. log_2 3 is irrational
2. there are infinitely many prime numbers
3. for any n, the numbers n! + 2, n! + 3, ..., n! + n are all composite
4. no triangle has two right angles

Invariant Drill

Find an invariant (or monovariant) and use it to decide each question. If the goal is unreachable, state why. If reachable, give a construction:

1. starting from (0, 0) with moves (+2, +3) or (+3, +2), can you reach (13, 17)?
2. on a 4 x 4 grid of lights all off, a move flips any row or any column. Can you end with exactly one light on?
3. 25 coins are arranged in a row. A move flips any three consecutive coins. Starting from all heads, can you reach all tails?
4. in a room of 15 people, each person shakes hands with some subset of the others. Prove that two people shook the same number of hands

Construction Drill

Produce a constructive proof for each. State the building step, the progress measure, the termination, and the correctness:

1. every simple connected graph has a spanning tree
2. every positive integer greater than 1 has a prime factorization
3. given a sorted array and a target, construct a binary search that returns the index or reports absence
4. given two strings, construct a sequence of single-character insertions, deletions, and substitutions that transforms one into the other (argue termination)

Divide-and-Conquer and DP Drill

For each problem, classify the strategy and write the recurrence:

1. mergesort an array of length n
2. compute the k-th smallest element of an unsorted array in expected O(n) (hint: partition-based selection)
3. count the number of distinct binary search trees on n nodes
4. find the edit distance between two strings
5. compute the convex hull of n points in the plane
6. find the longest increasing subsequence of a sequence of n numbers

Contest-Flavored Challenge Set

Solve at least three of these with full Polya discipline (understand, plan, execute, look back):

1. given an n x n grid, how many shortest paths are there from (0,0) to (n,n)?
2. prove that for any n, the n-th Fermat number F_n = 2^{2^n} + 1 is coprime with every other Fermat number
3. a graph on 10 vertices has 28 edges. Prove it contains a triangle
4. given a sequence of n distinct integers, prove it contains an increasing or decreasing subsequence of length at least ceil(sqrt(n)) (Erdős-Szekeres)
5. show that in any 2n + 1 consecutive integers, at least one is coprime with all the others

Evidence Check

This page is complete only if you can identify, for a fresh problem, whether contradiction, invariant, construction, divide-and-conquer, or DP is the right structural move, and write the opening of the proof accordingly.