Final problems

Over the term, I will provide weekly problems which are intended for the final. On the final, you will be asked to do the following.

State one of these problems
Describe (briefly) why you chose it, what you found interesting about it.
Describe what you have done towards a solution of this problem.

Problem 1

We will call a Doodle a line drawing which may cross itself many times. For example, the following are all doodles.

The question is the following.

Question: Under what conditions on the doodle (in terms if its layout, how big it is, any other property you can think of) is it possible to trace over the doodle in one continuous sketch without ever having to trace over any segment of it twice?

Problem 2

Recall that the Pythagorean theorem stated the following.

Given a right-angled triangle with side lengths a and b, and hypotenuse c, then

$a^{2}+b^{2}=c^{2}$ .

We know that (a₀, b₀, c₀) = (3,4,5), (a₁, b₁, c₁) = (5,12,13) and (a₂, b₂, c₂) = (6,8,10) are integer solutions to this equation. What other integer solutions can you find? How many are there? Can you find all of them, or at least find patterns to them?

Problem 3

The ABC puzzle

This puzzle is about manipulating strings of letters. The goal is to use the four given rules to try to transform the string "AC" into the string "AB". The rules are as follows.

Rule 1: If you have a string which ends in the letter 'C', then you may add a 'B' on the end.

Example: From the string "AC" we can obtain the string "ACB".

Rule 2: If the sub-string "CCC" occurs (consecutively!) in a string, then you may replace it with a 'B'.

Example: From the string "ABCACCCB" we can obtain "ABCABB".

Rule 3: If the sub-string "BB" occurs (consecutively, again) in a string, then you may remove it.

Example: From "ABCABB" we can obtain "ABCA".

Rule 4: If you have the string "Ax" where x represents any string, then you can produce the string "Axx" i.e. you can double what follows after an initial 'A'

Examples: From " $A\underbrace {BCC} _{x}$ " you may produce " $A\underbrace {BCC} _{x}\underbrace {BCC} _{x}$ ".

Note also that you can not undo any of these rules; they only work in one direction. The goal is then to take the initial string "AC" and turn it into "AB" using these rules.

Problem 4

It isn't hard to see that given only a straight-edge (an unmarked ruler) and compass, that you can add together lengths. That is given a line segment of length A and one of length B, you can produce one of length A + B (and even one of length A - B, when A is larger than B).

The goal of this problem is to show that you can do much more than that. That is, given

A line segment of length A
A line segment of length B
A line segment of length 1 (for reference)

come up with a way, using only the given tools, to produce a line segment of each of the following lengths:

One of length AB.
One of length A/B.
One of length ${\sqrt {A}}$ .

Note that you should be able to provide a justification that your construction actually does what you claim it does!