Larry Guth’s “No Rectangles” problem

[note: sorry for the rushed write up – I wanted to get this written up before 9:00 this morning because of a work project that’s going to have me tied up for most of the rest of the day]

Yesterday I was lucky to attend a lecture that Larry Guth gave at MIT:

Larry Guth’s “No Rectangles” problem

It was sort of doubly lucky because I’d already set up a meeting in Cambridge and a little bit of juggling with some times allowed me to have the meeting and attend the lecture. The problem that Guth discussed has the wonderful property of being simultaneously accessible to kids and interesting to research mathematicians. His talk began with a discussion about a simple 3×3 grid and ended with a discussion of intersecting lines in the field Z mod p! Today I used some of the basic ideas in Guth’s talk as the basis for a fun little project with the boys.

I really loved talking through Guth’s problem with them. As often happens in our projects, we ended up going in a slightly different direction than I’d anticipated – but the discussion we had as a result was also much better than I’d anticipated!

We started with a quick introduction to Guth’s “no rectangles” problem and the boys tried to work through the 3×3 case:

 

The first part of the project ended with the boys finding a way to place 6 snap cubes on a 3×3 square without forming a rectangle. Now we try to see if 6 is the maximum number or is there a way to place 7?

They approached this question in a way that surprised me a little. The first thing they wanted to do was count the total number of rectangles in the grid (which has one subtle point). This approach turned out to be a pretty interesting way to look at the original problem. It is also a pretty interesting counting problem for kids all by itself:

 

So, having counted 9 rectangles in the 3×3 grid, the boys then tried to see if they could eliminate all 9 of these rectangles by taking away just two of the snap cubes. The conversation here was super fun – lots of great opportunities for the kids to talk about patterns and explore different ideas. For example, my younger son noticed that you are forced to take away one of the cubes on a corner of the 3×3 grid.

In the 2nd half of this video I show them a different way to see that you can’t have 7 cubes on the grid without forming a rectangle. This approach – which is the way Guth explained it in his talk – involves the pigeonhole principle.

 

For the next part of the project I thought it would be fun for the kids to try to figure out the total number of different ways to place snap cubes onto an NxN grid. Thinking through this problem helps you understand that trying to work through the “no rectangles” problem by brute force with a computer is going to take a long, long time.

Just like the rectangle counting problem the boys came up with in the earlier part of the project, this problem is a nice counting problem for kids all by itself.

 

Now that we’ve found that the total number of ways to put the snap cubes onto an NxN square is 2^{n^2}, we try to understand the size of some of these large powers of 2. We start by finding an approximation for 2^{25} – the number of ways to put snap cubes on a 5×5 grid – and then try to see if a computer could handle a number this large.

What about a 10×10 grid, though? This problem ends up bringing to the surface a little problem understanding the exponential notation, but that’s one of the great things about this project – you have a nice opportunity to talk about / review exponents while talking about a really interesting problem:

 

For the last part of the project we try to understand how long 10^{21} seconds is. It is actually so long that there’s probably no way for kids to have an intuitive understand of that many seconds. However, we can try to convert it to other units of time, and years seemed like a pretty natural choice. We found that if you can check 1 billion squares per second, searching through all of the possible ways to put snap cubes on a 10×10 grid would take about 300 trillion years!!

Since that’s more time than we’d probably want to spend on that problem, you need to look for a different approach. One really cool thing about Guth’s problem is that there’s a surprising (to me!) connection to geometry and number theory hiding beneath the surface. Guth ended his talk by explaining how to solve the problem using those ideas. That approach, by the way, is truly marvelous but there wasn’t enough room in the margin of my white board to explain it . . . . 🙂

 

I love being able to share projects like this one with the boys. There aren’t too many problems that are both interesting to research mathematicians and accessible to kids. The kids were able to understand the problem right way and had lots of interesting ideas about the 3×3 case. Exploring the 4×4 case would probably be lots of fun for kids, too. It always amazes me how much fun you can have and how far math conversations with kids can go when the problems keep them engaged. It really was a great bit of luck to have had the opportunity to attend Guth’s lecture yesterday.

Advertisements

Comments

2 Comments so far. Leave a comment below.
  1. Kevin,

    Hi Mike,
    What a fun problem! I have used it with a bunch of math classes. Have your boys worked further on the problem and investigated the 4×4, 5×5 or 6×6 cases? I’m wondering if you know of the maximum solutions for those cases?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: