Unsolved problem [entries|reading|network|archive]
simont

[ userinfo | dreamwidth userinfo ]
[ archive | journal archive ]

Wed 2014-02-19 10:52
Unsolved problem
LinkReply
[personal profile] simontFri 2014-02-21 15:23

Aha, now I think I've got a proof of rationality. Suppose we have some dissection containing an irrational fragment. We will show it isn't optimal (under my extended criterion that if two dissections' shortest fragment lengths are equal then you tie-break by looking at the second shortest distinct length and so on).

Choose a basis B for R as a vector space over Q, and choose it so that it includes an actual rational q. Write every fragment length in the dissection as its unique weighted sum of elements of B. Rational lengths will therefore be represented as straightforward multiples of q.

The shortest irrational fragment length, being irrational, must have a nonzero coefficient for at least one element of B that isn't q; let b be such an element. Look at the coefficients of b across all fragments of the dissection. They must sum to zero in every input and output stick (because those sticks' lengths are all rational, hence have zero coefficient of everything other than q). So if we pick any real ε and adjust every fragment length by ε times its coefficient of b, we must get a system of adjustments that preserves every input and output stick length, and which always adjusts equally long sticks by the same amount. So in particular we can choose ε so that it has the correct sign to slightly increase the shortest irrational length (and has absolute value small enough not to make any two lengths cross over each other), and then applying those adjustments yields a strictly better solution.

Hence, no dissection with any irrational fragment can be optimal (under the extended criterion including tie-breaking), and in particular no dissection with an irrational shortest fragment can be optimal even under the original criterion. []

(Slightly icky because it uses the Axiom of Choice, almost certainly unnecessarily. But AC is obviously true, right? So no problem really. :-)

Link Reply to this | Parent | Thread
[personal profile] jackMon 2014-03-10 13:14

I now actually read this proof, and it sounds right to me, though I don't guarantee I haven't missed some exception.

What confused me in the pub is, you use the axiom of choice to get a basis for R over Q. But don't you just need a basis over Q for the vector space generated by the fragment lengths you actually have, not over any possible irrationals? Isn't that just some subset of the fragment lengths, throwing away any non-linearly-independent ones?

Link Reply to this | Parent | Thread
[personal profile] simontMon 2014-03-10 13:33

Ah! Yes, good thought. And that vector space is finite-dimensional, because we have at most finitely many frag lengths, and hence we don't need AC to conclude that it has a basis. Well done.

Link Reply to this | Parent
navigation
[ go | Previous Entry | Next Entry ]
[ add | to Memories ]