2009-02-13

Numbers that Grow on Trees

Bengt has come up with a whole new kind of number system, which he has decided to call "Dendriux". Each number is expressed as a full binary tree - that is, a tree diagram where each node has either two child nodes or none. It's also binary in a different sense; each node contains either a 1 or a 0.
The numerical value is calculated as follows:
- A node with a 1 has a value which is 1 less than it otherwise would be.
- A (0) node with no children has the value 2.
- A (0) node with children of value n and m has the value of the sum of the nth and the mth prime number (counting 2 as prime number number one).
  1. Some numbers can be written more than one way. Find, for example, all ways of writing 10, 11 and 12.
  2. Suppose that f(x) is the number of ways in which the number x can be written. Find the asymptotic upper bound (the "ordo") for f(x).
  3. (hard) Is it really possible to write all positive integers this way? Prove it.

2009-02-05

Nightly Tag

Alban is visiting Bengt, and after some drinking they start getting childish and decide to play tag. Bengt is surprisingly fast for his size; more specifically, he is k times faster than Alban. They are both moving at constant speed.
Bengt is chasing Alban, and they are a distance d apart. Then suddenly the sun sets, and Bengt can no longer see more than 1 m ahead.
  1. Suppose Alban is performing a brownian motion. What curve should Bengt follow in order to catch him as quickly as possible?
  2. For which values of k and d is it likely that Bengt will catch Alban?
  3. Now suppose Alban can follow any curve. What curve should Bengt follow to be sure of catching him?
  4. For which values of k and d can Bengt be sure of catching him?
  5. Eventually they get tired of the game. They lie down it the grass and start idly chatting about spaceships.
    Repeat all the above questions, but now assuming that Bengt and Alban are in space; that is, they move in three dimensions rather than two, they have a constant (magnitude of) acceleration instead of constant speed, with Bengt accelerating k times faster than Alban, and their initial relative speed is s.