Challenge Problems

This page collects challenge problems that have been posed in cs2102.

By solving a challenge problem, you earn the glory and admiration of your classmates and the course staff (and maybe even the whole Internet if your solution is clever enough!). If that’s not enough, you also are rewarded “bonus points” (the number varies at the discretion of the teacher, but typically a value from about ½ to a full problem set (or even more).

You can submit a candidate answer for a challenge problem by sending me a Direct Message in Slack, or sending an email with subject line “Challenge Solution”.

# Open Challenges

**Challenge 8.** From Class 20: Prove that the
Huntington-Hill Method used to apportional seats in the US Congress
satisfies the quota property when used for a sets of states where
each state has population at least *D* (where *D* is defined as the
total country population divided by the number of representatives).
The quota property states that each state receives either the floor
of its population / *D* or one more than that delegates.

**Challenge 2.** From Class 3: It is trivial to show that
numbers in Java or C are not we-ordered, but quite challenging to show
this for Python. Write a Python program that demonstrates the fact
that integers in Python are not well-ordered. (Note: although I’m
continuing to list this as a “open challenge”, I don’t think there
will be a satisfactory solution. It is not enough to show a Python
program running out of memory trying to represent a large number, or
to show that `math.inf`

is not really infinity (obviously), but a
satisfactory solution would need to show some well accepted arithmetic
property being violated by the way arithmetic works on integers in
Python.)

```
import sys
a = sys.float_info.max
assert (a + 1 == a)
```

# Closed Challenges

(Challenges are not ever really “closed”, in the sense that if you can come up with a substantially better solution than the one posted, it is possible to win a closed challenge. The meaning of a “closed” challenge is that I believe there has been a winning solution, and that it is unlikely for someone to find a substantially better one.)

**Challenge 1.** From Class 2: I wasn’t very satisfied with
my proof of the “Odd-Even Lemma” in class. I hope a student will come
up with a better proof. Come up with a proof that passes the
“skeptical reader” test and would convince someone with no prior
knowledge of odd and even numbers.

- John Fry’s solution using the well-ordering principle
- Paul Sander’s solution using a game proof (although most game-style proofs are not so entertaingly written as Pauls, using a game to prove something is a very common strategy, especially in security and cryptography proofs.)
- Avi Parikh’s solution using proof by contradiction

**Challenge 3.** (From Class 8) Apparently, people were not entirely convinced by my
proof sketch in class that the egg came before the chicken. So, we’ll
make it a challenge problem to write the best proof that answers the
question of “which came first, the chicken or the egg?” (That is, you
can either prove the egg came first, or prove the chicken came first).
A convincing proof would need to include clear definitions of “chicken”
and “egg”, and use inference rules, as well as axioms based on
biological assumptions (clearly stated), to make an irrefutable argument
supporting your position.

**Challenge 4.** (From Class 9) How many self-inverting relations, *R*: *N*_{k} → *N*_{k}, are there? (Where *N*_{k} is the set of all non-negative integers less than *k*, and a relation is self-inverting if *R* = *R*^{-1}.)

**Challenge 5.** (From PS3 Solutions) Prove that the four-clause solution given for question 6 is the shortest possible equivalent 3CNF formula.

**Challenge 6.** (From PS3 Solutions) Provide a full and convincing proof for Problem 11.

**Challenge 7.** From Class19: Determine the carinality of
the set of all *Tree* objects (as defined on PS8), and provide a convincing
proof supporting your answer.