This might be too hard for me, pt. 1

Here is a problem we've been working on (originally taken from wu::riddles). Here is one way to describe it:

Draw a 1x1 square. In a minute, I'm going to take a ruler and draw a straight line that will "cut" accross some part of the square. It might be through the middle, or it might only be a small section of the corner; you don't know. You should draw anything you want inside the square so you can be certain that any line I draw must cross one of the lines in your drawing. The challenge is to do this with the shortest possible amount of drawing.

The first, and most obvious, suggestion would be this:

The blue lines are the solution. Obviously, it blocks all possible red lines (3 possible red lines shown), and the fact that it's symmetric makes it look pretty short. But how could we prove it was the shortest? In particular, we wanted to be sure there wasn't some weird scatter of short lines (with a shorter total length) that would also block all possible red lines.


(Here's an imagined weird scatter with few blocked red lines. Of course, a scatter like this could consist of a huge number of almost point-like line segments....so, pretty hard to think about on a case-by-case basis....)

One friend of ours suggested the following proof (actually "proof" since it turned out to be wrong). It's an interesting and useful form of argument, however.

Idea #1: Find the shortest solution for only some of the lines

Any solution that blocks all possible lines will at least have to block all the diagonal lines (in both directions).
If we can find the shortest solution that blocks just these lines, we'll know that a full solution has to be at least that long.

Let's divide the square into a bunch of parallel "slices"...

...and find the shortest solution for each "slice" that blocks only the diagonal lines from one side to the other (direction shown as the green arrow).

In this diagram, we have a slice (in black). We're only interested in blocking the green lines parallel to the one shown. The shortest solution for this slice will be a line perpendicular to the green ones we're blocking (such as the blue line shown).

So, if that blue line is the shortest solution for a slice, we can put that same solution together for all the slices...
As you can see, this blocks all the parallel diagonal lines in that direction (though, of course, it would let other lines through). But, if we're right so far, that's the shortest possible way to block those parallel lines (since for each little slice it was the shortest).

If we also want to block the diagonal lines in the other direction, we just repeat the procedure and overlay the results:
This is a scatter that we've constructed only to block the diagonal lines. BUT, we know that, for each direction, it does so with the shortest amount of drawing.

Since an actual solution (that blocks all the lines) will have to block those diagonal ones, and we know it has to be at least as long as this scatter to block the diagonal ones, the full solution will also have to be at least as long as this scatter.

But our "x" solution is exactly that long. It's easy to see why: instead of putting each little blue segment in a random spot, we line them all up along the diagonals.

You can imagine moving each bit perpendicular to its direction, and they line-up to make the x!

So, the "x" is the shortest possible way to block all the diagonals, but it also blocks all the other lines lines! Therefore, it must be the shortest full solution, because if there was another, shorter solution, we'd know it couldn't be blocking all the diagonal lines.

Since we thought the "x" solution was probably the best, we weren't very critical of the "proof" and thought we'd done a pretty good job!

Here's the problem:

This drawing is a shorter solution.

What went wrong with the original proof? Maybe lots of things, but one clear problem was how we broke the problem down into two smaller problems, and then re-combined them.

First we asked "what's the shortest way to block all the diagonal lines in one direction? Ok, let's keep that. Now let's do the same thing in the other direction to block all the other diagonal lines."

The problem is that one little bit of our "x" solution blocks lots of one type of diagonal (green), but none of the other type of diagonal (red)...
Whereas, a little piece of our 2nd solution can block both directions at once...

So maybe, even though our small pieces aren't the shortest for blocking lines in ONE direction or the other, they're the shortest for blocking blocking them together. Their overall blocking efficiency is better (we use this idea more in idea #3 below).

Idea #2: A Connected Solution is Always Shortest

The solution which beat the "x" is formed by adding two imaginary points so that, when you connect all the dots, they form 120-degree angles.

Someone pointed out that there's a theorem which says that this same method will produce the shortest path connecting any number of dots in the plane. So that seemed promising.

Of course, a shortest path connecting points is different than a shortest drawing that will block all possible lines, but it still seemed like a step in the right direction. Maybe we could connect the two problems together...

I hoped that this solution was, in fact, the shortest and we could prove it with a two-step argument:

1). If there's a "disconnected solution" (like a scatter), there will be a "connected solution" (continuous lines with no breaks) that's the same length or shorter.

2). Any "connected solution" must connect the vertecies of the square with each other.

3). Therefore, because of the shortest-path theorem, our solution will also be the shortest blocking solution.

However, we didn't get very far along this path until we found...

This was the shortest solution yet. It also showed the my old hope was wrong. I had hoped that the shortest solution would always be a connected one. Now we know that can't possibly be true.

Curious Student: "But wait! Isn't it possible that you could find an even shorter solution that is connected? Then you'd be right that the shortest solution is a connected one!"

Sadly, no. That theorem about the shortest connecting path implies that the shortest connected solution is the one we found. This disconnected solution is shorter. So if we find an even shorter solution than this, we know it won't be a connected one; it will have breaks in it.

Idea #3: Try A Smaller Problem. Measure Blocking Efficiency.

Since we didn't have a good way to analyze the square, we decided to try the simplest case we could think of: the equilateral triangle.

Here is the shortest solution we found for the equilateral triangle:

Once again we have the problem of how to prove this is the shortest.

Nick was hoping to use an idea similar to the last proof that didn't work. Here's the idea:

Any solution that blocks all lines will at least have to block all lines perpendicular to the three sides of the triangle.

If I have a random tiny line segment, I can measure how much of this blocking it does by measuring how long a "shadow" it would cast on each side of the triangle if I shined a light behind it (perpendicular to the wall) (and add them up).

Using these ideas, we hoped that we could show that our solution is the shortest by showing that it's not possible to have a random small piece that blocks more than a random small piece (of the same length) from our solution.

In other words, the orientation of the lines in our solution gives you the maximum amount of blocking possible. That would show that it was the shortest solution for lines perpendicular to the 3 sides. Since our solution also blocks the other lines, it would be the shortest overall solution (by an argument similar to our idea #1).

Unfortunately, we found that a small piece (in isolation) blocks the most when it's parallel to one of the sides; the pieces in our solution are all perpendicular.

This gave me a new idea, however. How much blocking a solution does depends on two things: how much blocking each little piece does, and whether or not any pieces are blocking the same lines (how much redundant blocking there is).

If you want to make your solution shorter, you could either try to change the orientation of your lines so that they block more, or you could move them around so that their blocking isn't redundant.

This led us to...

Idea #5: Measure Redundant Blocking

Here was my idea...

1). Find a measure of how much total blocking needs to be done.
2). Measure the maximum amount of blocking a given tiny line segment can do
3). This will let us calculate a theoretical shortest solution solution. If we assume no redundant blocking, the shortest solution will be...

(total blocking needed) / (how much blocking a unit of solution can do) = total units of length in solution.

4). Calculate the amount of redundant blocking in our proposed shortest solution.
5). Show (somehow) that exactly that much redundancy is required for any 100% blocking solution.

The really hard part of this is step 5.

But steps 1 and 2 are also tricky because they require us to measure blocking in some way. Before we were only measure how many of certain types of lines were being blocked. I wanted a way to measure all the lines being blocked.

How can we do it? Here was our idea...

...inscribe our shape in a circle. Now, the lines you need to block can be seen as all the lines going from one arc of the circle to another.

Here's a picture of what I mean. The three arcs are in different colors. Any line starting in one arc and ending in another is a line we need to block.

This gives us a possible way to measure how much blocking a little line segment does: Imagine a light on the circle, shining onto the segment. Measure the length of the "shadow" it casts on the other side. This is a measure of how many lines it blocks from that point.

To find out how many total lines it blocks, imagine slowly rotating that flashlight around the circle and adding up all the arc lengths. When you've gone all the way around, this is the blocking measure of this segment.

Mathematically speaking, if we have a function to find the arc length, and integrate it from 0 to 360 (as the light source moves around the circle), this should allow us to measure it. We haven't made this integral yet because it seemed hard and we're hoping if we're clever enough we won't have to.

My great hope was that the total amount of blocking of a segment only depends on its length; not on its angle or location within the triangle. The reason this would be good is that a certain length of solution would directly yield a certain total length of blocking. Then, to find the shortest solution, all we have to do is find an arrangement which minimizes redundant blocking. So, instead of minimizing length of solution, we'd be minimizing redundancy of solution.

Unfortunately (for reasons I won't go into), it doesn't seem like that's going to work, though I'm not 100% convinced yet.

That's all I'm going to write for now....perhaps more later...

But first:

What's making this problem hard?

The difficulty we've been having in this problem is that we can't break it down into simple sub-problems we can solve independently.

A short solution depends on two things: the "blocking efficiency" of each little piece, and the amount of redundant blocking for the arrangement. The blocking efficiency seems to depend on the angle and location of each little piece; and the "blocking" of the pieces need to be balanced between all the directions that require blocking. The amount of blocking depends on how each piece is oriented with respect to every other piece; it's a global property of the solution. And so far we can't think of an easy way to divide all the possibilities into cases we can treat separately.

If anyone has new ideas, we'd love to hear them!