Travelling Salesman

The Travelling Salesman is a classic problem. Given n cities, and for each pair of them the time it takes to travel from one to the other, find the fastest way to visit all cities, without visiting any more than once, and then come back to the starting city. This problem is well known to be NP-complete. But there might be ways to simplify it a little. Since Bengt refuses to go on holiday if it can't be done in the most efficient way, and it's clear he needs to get out more, we should try to help him.

1. Suppose the world is flat, cities are pointlike, and the time it takes to travel between them is proportional to the physical distance. Is it still NP-complete? Show that it is, or find a polynomial-time solution.
2. What if the world is spherical? Does that make a difference?
3. What if we have up to k dimensions? Or up to n dimensions?
4. Going back to the flat world, what if some roads are a little bit slower, so that the time to move between two cities is between 1 and k times the distance? What if it's between 1 and n?
5. Suppose we don't need to get back to the starting position. Does that make a difference? If not, why did they bother including that in the problem definition?
6. (hard) Suppose we don't care about finding the quickest route, but we want to avoid being on the road (between two cities) for more than a day at a time. Is there a polynomial-time solution for that?

Bengt, Fermat, and Mersenne

Fermat had a lot of clever ideas in mathematics, but the Fermat primes were maybe not his brightest one. He claimed that any number on the form 2^(2^n)+1 is a prime, and made it plausible by showing it to be true for all n up to 4. Sadly, like so many other beautiful ideas in science, it was ruined by the Germans; Euler showed that it is not true for n = 5. (Actually, Euler was from Switzerland, but never mind that now.) A bunch of other Fermat numbers have been tested, but so far none of them have turned out to be primes. It has been proven that at least up to n = 32, there are no more Fermat primes. What a bust. Another guy who thought about primes was Mersenne, and his idea was 2^n-1, where n is a prime. Those things are not always primes either, but at least it happens fairly often. Bengt has what he thinks sounds like an awesome idea. You might call them the Bengt numbers, but to be honest he's not quite sure enough that they're going to work out that he wants to name them after himself. After all, you don't want to end up looking silly like Fermat. Here's his idea: n! is divisible by all the numbers up to n. Therefore n!+1 can't be divisible by any of them, so it must be a prime. The same is true for n!-1, so you get two primes for the price of one. Bengt is happy having come up with such a brilliant idea, so he goes off to treat himself to some chocolate, and forgets all about the whole thing.

1. First, we'll play around with the Mersenne numbers for a bit. Find the first that isn't a prime.
2. Now let's see if we can help poor Fermat out. So 2^n+1 didn't work, and 2^(2^n)+1 doesn't work. What about 2^(2^(2^n))+1? Actually, never mind that - let's go a little crazy and say 2^(2^(2^(2^(2^(2^n)))))+1. Are those all primes?
3. It's probably a good idea that Bengt didn't name those numbers after himself. Explain where he got it wrong, and find a counterexample.
4. What if n is always prime? Counterexample?
5. Even if it doesn't work for every n, it might still work for infinitely many n. Does it? Are there infinitely many n for which n!+1 and n!-1 are both primes?
6. (hard) Is there any function that does what Bengt want - that is, there are infinitely many n such that f(n)+1 and f(n)-1 are primes?

Fun with the ISO 216 Standard

ISO 216 is a lovely standard. It's the one that defines the A4 paper size, and all its friends. Bengt likes papers, not just for writing on, but also for other things, like making paper airplanes. He claims that the A4 size is particularly good for making paper planes, but that would most likely be a bit of a mess to try to prove, so we'll leave this out of this problem.

One other thing they can be used for is to measure lengths. See, the meter isn't really a very convenient unit of measurement - it's historically based on the circumference of the Earth, which to be honest isn't something most people have an intuitive grasp on. The foot is better in that sense, but since people's feet aren't all the same length, that's also not quite ideal. In fact, there may not be any obvious things in nature to base a length unit on, because most things in everyday life vary in size. But a standardised paper size - well, it may not be "in nature", but papers sure are pretty much everywhere these days, and they're a convenient size too. And we could potentially set the definition of the paper size so that it fits with some scientific constant - say, a nanolightsecond; that way, the definition would be convenient for both scientists and normal people.

But there is a slight problem with the A4 as it stands: It's based on area, not length. A0 has the area 1 m², and each subsequent one has half that area. It would probably be better to define them by saying that, for example, the short side of the first one would be one meter. It's a little known fact that the same ISO standard actually defines that as well - it's called the B series. So, for example, the B4 is a quarter of a meter wide.

Still, there's another slight problem: Every other size will have half the length, but the metric system is based on powers of ten, not two. So once you get down to B10, the width is 31.25 mm - or rather, it's 31 mm, since the standard requires that they be rounded off to the nearest millimeter, which is clearly an abomination.

If you ask Bengt, this is further proof that the decimal system is inherently flawed, and we should use base sixteen instead - in that case, the area of an A4 would be exactly one d(m²), which is admittedly a confusing unit, as it's easily confused with the much smaller (dm)², but anyway. And the B8 would be one dm wide, so we could for example give all children a little notepad in that size, and use that as our unit of measurement, so we would all grow up with a remarkably accurate intuition for length units, and there would be no need to fight over it, which would probably lead to world peace.

Now, just to make fun of the decimal system and all that, let's try to construct a paper size which does the same thing but with each subsequent area being a tenth of the previous area, rather than half. It should have such proportions that if you fold the short side in half, and the long side in fifths, you get the same proportions again. It would be awfully tricky to fold anything like that, but that's sort of the idea.

1. What is the width of an A0?
2. On a side note - how long is a nanolightsecond, in, say, feet?
3. What proportions would the "decimal" system have? Suppose the short side is 1 m, how long would the long one be?
4. Is there a simple similar system where both the areas and lengths have integer ratios?
5. How far does the A series go, before they get rounded off to nothing?

The Problem with Bathtubs

Bengt is in the bath. It's very hot, because Bengt thinks real men bathe in at least 50°C, but that has nothing to do with the problem. Suddenly he notices a little bit of lint in the water. Yuck! He pulls out the plug to let the water out and get rid of the lint. We can assume that the lint is in a random location and has the same density as the water; it behaves essentially like a randomly selected water molecule. But Bengt is annoyed at how slowly the water is flowing, so he considers whether it might possibly help to add more water. That way the pressure and therefore the rate of flow would increase, right?

1. Is there any way adding water could decrease the expected time for the lint to disappear? Assume that the added water appears uniformly; that is, we can think of it in an entirely statistical way, with water molecules being added and removed at random. The only physics involved is the increased rate of flow from the pressure.
2. What if we involve a little more physics? Presumably Bengt has the sense to add the new water at the opposite end of the bathtub from the drain. Could it reasonably be expected to be a good idea?

Bengt vs. Peano, part s(0)

In the last problem, we took arithmetic down to what seems like a very fundamental level, seemingly without any preconceived ideas or assumptions. But Bengt is not satisfied.

Now, you might say, there's that definition symbol that we haven't defined, right? Peano himself famously asked "How do you define a definition?" But Bengt thinks this is a stupid question, because obviously you don't. The definition symbol is not part of the system, it's outside the system, so it's fine.

We've also sort of skipped over the issue of precedence - unless of course you decided to deal with that in your answer to the last problem, in which case, good on you - but that's not a problem either, because we could just express "x+y" as "+(x, y)" instead, that is, use only prefix operators.

No, what Bengt has a problem with is all those variables. What is x? Well, it varies, obviously, that's kind of the point of variables, but Bengt is not happy with that. Also we're assuming that there are functions, which takes arguments, and all that. And what about all those definitions of numbers? That's a great many definitions, isn't it? So either we have to make an infinite number of definitions, or we're stuck writing numbers as s(s(s(s(s(...

Bengt would like to sort out all that stuff and make everything simple. In the new system, every rule has to contain an exact sequence of symbols on each side.

Decimal numbers would be a little cumbersome to define, so we might resort to binary - once we've got that down, it's easy enough to do the same with any other base. Alternatively, we could use unary numbers, which would probably make things even easier to define, but is a pretty messy way of writing numbers. Also, to make sure we know where a number starts and ends, we'll enclose them in brackets. So eleven is written as [1011] in binary, or [•••••••••••] in unary.

Furthermore, it's probably a good idea to write the operators prefix instead of infix, so we don't have to worry about precedence and parentheses and all that. So 1+1=2 could be written (in binary) as =+[1][1][10].

As a warm-up, we could start with logical expressions. We might define true and false as... oh, it doesn't matter, really, let's just say T and F. We can always define those as something else later. If we let for example the & symbol stand for "and" (which makes sense, since that's what it means) we could write

&TT:T
&TF:F
&FT:F
&FF:F

The trickiness appears of course when we want to deal with numbers, since we can't just spell out all possibilities. But that doesn't mean it can't be done. If we take our old pal the successor function, for example, it could be written (for unary) as
s[:[•

Now all that remains is to go from there to a complete arithmetic system, not using any variables or anything else that isn't a literal sequence of symbols.

1. Define the "or" operator.
2. Define addition for unary numbers. There are various ways, with or without using the successor function - feel free to try out more than one. Note that this function (and the others) should be able to handle any natural numbers.
3. And multiplication.
4. Define the successor function for binary numbers.
5. Define addition for binary numbers.
6. And multiplication.
7. Define binary numbers in terms of unary. This obviously solves (e) and (f) automatically, so it's nice if you've got some other solution to those as well.
8. What can't you do in this type of system that you can do in Peano's? You might want to look up "Peano's axioms" if you're not familiar with them.

Bengt vs. Peano, part 0

Bengt likes maths, and he likes starting from the very basics. So that's what we're doing today.

The foundations of arithmetic are often expressed by starting from one number, zero, and one function, the successor function. We denote those by 0 and s. (The successor function of a given number represents the following number, so s(x) is what you would normally call x+1.) From those, we can easily define things like the other natural numbers:
1 : s(0)
2 : s(1)
3 : s(2)
...

We can also define the basic operators. For example, addition can be described like so:
x + 0 : x
x + s(y) : s(x) + y

Just to horrify mathematicians, Bengt decides to include infinity in the natural numbers. Just like 0 and s, it is not defined as anything in particular. Then we need a couple more lines to define addition:
x + ∞ : ∞
∞ + x : ∞

To include things like the equals operator, which is essentially a function from two numbers to a truth value, we also need to define true and false. But Bengt decides to cheat a little by reusing the numbers, like in some programming languages. Let's be a little bit original and say that 0 denotes true, and ∞ denotes false.

1. Define multiplication.
2. Define subtraction. Since we're only dealing with natural numbers, we'll use a slightly unusual definition of subtraction; the smaller number is always subtracted from the larger one. That is, what we want is actually the absolute value of subtraction. Infinity minus infinity should be zero.
3. Define equality. Remember that you can use the things you have defined in (a) and (b) - or haven't, if you skipped those.
4. Define the => operator, that is, equal-or-greater-than.
5. Define the other => operator, that is, logical implication.
6. What about logical negation? Will that be interesting somehow?
7. Finally, put those operators to use by proving that 1+1=2.

The brachistochrone, the catenoid, and a skateboard ramp

Bengt has started a new construction project in his garage. He's been working for weeks, when Alban comes by to see the finished product.
"It's a... skateboarding ramp. Bengt, have you taken up skateboarding?"
"Ha! Hell no. Do I look like a skateboarder?"
"So why do you have a ramp?"
"For experiments, obviously. That's the only reason any sane person would build a skateboard ramp in their garage."
Alban ignores the issue of sanity, and Bengt continues.
"It's not any ordinary ramp, you see. It's a brachistochrone."
"Which means...?"
"It means that if you let something slide down one side - a ball, perhaps, or why not a skateboard, as long as it's infinitesimally small - it will always reach the bottom in the same time, regardless of how high up the ramp it starts."
"How do you know?"
"I can measure the time. I have a clock chain, look."
Bengt holds up a long thin chain. He holds it with both ends at the same height, so the chain forms a U-shaped curve. This curve is called the catenoid. There is no clock on the chain.
"There is no clock on the chain." says Alban.
"No, no. The chain is the clock. Look, you hold it up by one end, and dangle it. It swings with a certain frequency, so it can be used to measure the time. You can use a shorter chain if you want a higher frequency. Since each link has the same mass, you can use it to measure mass as well! It's a multi-purpose chain indeed. Also, it has 60 links, one for each second of a minute."
"That makes no sense."
"That there are sixty seconds to a minute? No, it doesn't. But that's not my fault, you'll have to blame the Babylonians."
"That's not what I meant."
"I know that. Anyway, there should be 16 hours to a day, 16 minutes to an hour, and 16 seconds to a minute."
Alban sighs. "That would make pretty long seconds, tho, wouldn't it?"
"Yes. So we need to add another unit. I think I'll call it a ters. There are 16 terses to a second."
"So if I make a terse statement, will I be able to finish it within one ters?"
"You? I doubt it."

1. What curve is it that Bengt has built?
2. When he holds up his chain, what curve does that form?
3. The word "brachistochrone" means "shortest time". So why is the brachiosaurus not a short lizard?
4. To measure mass with the chain, Bengt wants to take it apart, in such that he can combine any number of links from 1 up to 60. How many links does he need to open to achieve that?
5. Now suppose he wants to be able to form whole chains from the parts, at any length. So the difference is that all combinations have to have enough open links that he can put them back together without opening any more.
6. If a link has mass m and length l, and you hold it so that n links are doing a pendulum motion, what is the frequency? You can assume that the chain is homogeneous.
7. How long is a ters, according to Bengt's definition?

A Childish Problem

Bengt has no children of his own, for various reasons. Mainly because he's such a big baby himself, most likely. He does occasionally enjoy the company of children, though. Particularly the geeks. From them, he has now learned a classic old problem. The task is to continue the sequence:
1
11
21
1112
3112
211213

1. What is the next element in the sequence? It's probably easier if you think like a child.
   
2. We can imagine three possibilities for the long term behaviour of the sequence: either it settles on one element, repeating that, or it goes into a loop, repeating a subsequence, or it continues forever without looping. Which one is it?
   
3. We could start the sequence with some other start value. Which of the three behaviours are possible?

Misunderstanding Maths

Bengt and Alban are doing some calculations. Actually, Alban is doing some sort of homework, and Bengt is playing around with his calculator. Bengt tries to draw a graph, of sin²(x), but he has done something terribly wrong. The curve he gets looks a lot like k*sin(x), where k ≈ 0.841470985.
"This calculator is stupid." says Bengt.
"I think it's probably you who's made a mistake." replies Alban.
"I know that, you silly engineer. But it has a resolution of 96x64 pixels. I'm pretty sure my digital watch from the eighties has a higher resolution."
"Yeah, that is stupid. Anyway, I'm having some problems too."
"Good ones?"
"Maybe to you. It says here that the results are in the interval k ± s. But when I look at them, it seems that only a fraction f of them are."
"Interesting. What's f?"
"It's two thirds, I think… or maybe just a little more."

1. What has Bengt done wrong?
2. Is the curve that Bengt has found actually a constant times sin(x)?
3. What is causing Alban's confusion? And what is f?

Hole Puncher of Horrors

Bengt is building a machine. It is a most unusual kind of hole puncher. It consists of a holder for the papers, and a rather nasty-looking wheel with n sharp spikes pointing outwards at regular intervals. As the machine operates, the holder is pressed against the spike wheel, so that one spike makes a big hole in the paper. (One big hole is more effective than several small, says Bengt.) Occasionally, a spike will break. This is where it gets really clever, or so Bengt thinks. The broken spike falls off completely, making that side of the wheel lighter. If the centre of mass of the wheel is not in the axis, the wheel will spin to orient itself with the centre of mass downwards. That way, Bengt figures, the broken spike will automatically be replaced - at least for a while, until enough of them have been broken.Ideally, we would like to design the device so that this can happen as many times as possible before there is no longer a spike pointing at the paper.

At which angle on the wheel, relative to the downward angle, should the holder be located? Are some choices of n better than others? Obviously more would be better, but aside from that?

Bengt vs. Turing

Bengt's friend Alban is an engineering student, and he's trying to show Bengt that he's not completely ignorant in the more theoretical fields. As we all know, that sort of showing off can be dangerous when Bengt is involved.
"...and so, there is no program which, for any given input program and starting values, determines whether that program stops." says Alban.
"There is too."
"What? No, there really isn't."
"Is too."
"Now you're being silly."
"How much memory does your computer have?"
"16 gig, why?"
"Imagine if you had infinitely big programs. The algorithm itself might be infinitely long, and it might use an infinite amount of memory. Could there be a program which for any such program determines whether it stops?"
"If it's infinite, it doesn't stop, does it?"
"It might. It could stop on the first line, even if it has infinitely many after that."
"Okay, fine. In that case, no, obviously."
"Obviously indeed. Now let's say the programs are not infinite. For example, they might be no bigger than your 16 gig. Or more generally, n bits. Program and variables included. Is it still impossible?"
"I think so... isn't that what the theorem says?"
"I sure hope it doesn't. I can do it in O(2ⁿ) time."
"That's an insanely long time."
"But not infinite."
"Not even a little?"
"Afraid not."

1. It seems unlikely that Bengt has proven Turing wrong. Where is the leap in Bengt's reasoning?
2. Given his somewhat special version of the halting problem, can you find a solution that runs in O(2ⁿ) time?
3. Is there perhaps an even faster way? Can you find one that is faster than O(2ⁿ)? Or prove that there isn't one?
4. Let's ignore Bengt's sneaky redefinitions, and try another modification to the original halting problem. Let A be a program that may or may not stop, and let B be a program trying to check whether A stops. Let f(A,B) be the statement "B can determine whether A stops". The theorem says that "∃B ∀A f(A,B))" (there is a B that works for every A) is false. But what about "∀A ∃B f(A,B)" (for every A there is a B that works)? Can we, for every program, find a testing program that checks if it stops? If A is also allowed to take a number as input, does that make a difference?