Thursday, September 15, 2016

Points In A Circle Problem: Update on N = 3

For the configuration of obstacle points shown below, nobody has yet found a valid triangle with area greater than about 0.829. Recall that a triangle is valid as long as it doesn't strictly contain any of the obstacle points.

The obstacle points shown above are equally spaced around a circle of radius 0.32096.... Given these obstacle points, the greatest area I can find for a valid triangle is 0.82863..., attained by the two triangles shown below.

(Reader Matt found these as well.) 

I call the first triangle "the edge triangle," and I call the second triangle "the spotlight triangle."

The reason I placed the obstacle points a distance 0.32096... from the center is that doing so gives the edge triangle and the spotlight triangle equal areas. If the obstacle points were to move closer to the center, the area of the edge triangle would increase and the area of the spotlight triangle would decrease; if the obstacle points were to move further from the center, the area of the spotlight triangle would increase and the area of the edge triangle would decrease. The greater of the two areas is minimized when the obstacle points are as shown. It is on the strength of that circumstance that I guessed these obstacles as minimizing the maximum area over valid triangles.

Anyhow, recently I had a bit of downtime, so I wrote a quick program to look randomly for valid triangles with area greater than 0.82863.... To do that, I first generated 1,000 points distributed randomly over the disk:

These thousand points determine 166,167,000 triangles. I went through those triangles, discarding any of them with area less than 0.815. What remained was a list of about 1.6 million large triangles. I checked this list to see if any of the large triangles were valid. However, none of them were. 

So, this particular attempt at beating the record 0.82863... failed. 

Here are some of the large triangles that were closest to being valid:

It looks as if these triangles are "trying" to be like the spotlight triangle, with one case of an edge triangle. (I think edge triangles are less well represented because they have fewer ways to avoid the obstacles without losing area rapidly by sacrificing altitude.)

Anyway, this exercise increases my confidence somewhat that the edge triangle and the spotlight triangle are indeed maximizers for the obstacle points shown, and that up to symmetry these two triangles are the only maximizers.

Of course, none of this is a proof of anything.

Some notes on the program: 

  • Calculating area is much faster than checking validity. That's why I calculated 166,167,000 triangle areas first, and then checked only the largest triangles for validity. It would have been impractically slow to work in the reverse order (checking 166,167,000 triangles for validity and then calculating the areas for the subset found to be valid). Calculating 166,167,000 triangle areas took about 12 hours. (If I do this again, I'll see if I can optimize the area calculation.)  
  • In the validity test, I'm using barycentric coordinates to determine whether a given point is contained by a given triangle. I'm not sure the barycentric test is faster than one based on same-side-of-line considerations, but so far I haven't needed to worry about speed in this phase of things. (Also, barycentric coordinates make it easy to be quantitative in various ways, for example identifying triangles that are close to valid, as shown in the animation above.)
  • 166,167,000 triangles is a lot of triangles, so the program never holds all of them in memory. Instead of generating all those triangles ahead of time, I put the area test inside a threefold-nested loop over the thousand randomly selected points. Triples of points passing the area test were added to a steadily growing list of large triangles. 

Sunday, September 11, 2016

Woohoo! Saturday School Is Back!

We took a break from Saturday School over the summer, doing math from time to time but not on a schedule. Now that regular school has started, we're getting back into the swing of things. This weekend my younger began learning the standard addition algorithm, and my elder started working toward multi-digit multiplication.

I thought people might like to have the latter set of worksheets, so I'm posting them here (PDF).

  • The first page is a skills brush-up.
  • She then filled out the second page, while I co-piloted as necessary.
  • Finally she completed page 3, which summarizes the conceptual work of page 2.

The last question on page 3 is an unrelated question about perfect numbers. At dinner the night before, I had remarked that 6 is called "perfect," because if you add up the factors of 6 not counting 6 itself, you get 1 + 2 + 3 = 6. Perfect numbers are fun (here is some cool background on them) but my underlying purpose in asking about them was actually to provide a bit of brush-up with multiplication facts.

Getting back to the worksheets, you'll see on page 2 that I use a visual model to make the distributive property concrete. However, there are some differences between page 2 and what one often sees in math textbooks. One difference is that I'm not referring anywhere to area. This isn't facially an area model. Instead, we are counting things. It's true that the things being counted are squares, so that if we conceive of the squares as area units, then we are also finding the total area of the strip. And as we get closer to the time of multiplying fractions, I'll be casting the squares as area units. But right now, I'm not introducing that language or activating those concepts in the student's mind. I'm staying close to the elementary meaning of multiplication, which is to count things arrayed in groups. (I did choose squares with an eye toward area models and fraction operations later on; thus, the diagram isn't baskets of flowers or the like.)

The second difference is that the diagrams on page 2 are numerically accurate. I didn't merely gesture at the ideas by drawing rectangular fields of color with arbitrary dimensions. In these diagrams, you can actually count all of the squares, and if you do then you will get the right answer.

I think that in the early stages of this kind of learning, textbooks often assume too much about what students do and don't understand about the visual representations the textbook uses. The author understands the elasticity of the representation scheme, but I doubt that all of the students do. To motivate multiplication as a better alternative to counting, let's be sure that multiplying and counting give the same answer! And in a case like this worksheet, where I'm using the distributive property to structure the multiplication into easy steps, I want each of those steps to give the right answer too. I'm suspicious of representations that ask beginners to think metaphorically.

Finally, in page 3 I'm making sure to summarize the visual/concrete work symbolically. Symbolic calculations like those on page 3 are going to generalize not only to fractions, but also to variables, expressions, area integrals, quantum-mechanical expectation values, you name it.

What's next? For the younger, we'll start practicing easy right-to-left vertical additions (no regrouping, or regrouping in one place). And I want to make sure there are no cobwebs about place value, by using the excellent place-value mini-assessment on For the elder, we'll begin building fluency with multiplying a multi-digit whole number by a one-digit whole number. As that takes hold, we can begin stacking those calculations per the standard multiplication algorithm.