HoustonHokie

OP's question looks solved to me at 8. How 'bout a corollary? How many squares can you paint initially with Bona's paintbrush and still not cover the entire board? I know you can paint at least 24 and not cover it. Can someone do better? edit:Never mind-that's dumb, too. All you have to do is look at the solutions that didn't work to see that its at least 56.

One of the interesting differences between your first three problems and the last two is that you can actually see the limit approaching 0 in the last two as the number of attempts increases. For example, if you've only got one pull at the random number generator, #4 is 0.9 and #5 is 0.1. With a second pull, #4 is 0.9*0.9=0.81 and #5 is 0.1*0.1=0.01, and so on. While both are, in the end, infinitesimals, #5 approaches 0 much more quickly than #4. Because the first three are single shot events, the only way to visualize the limit approaching 0 is to imagine the actual number of possible random integers or decimals increasing towards infinity. From that standpoint, you can then see that #2 approaches 0 slightly more quickly than #1 which is the point the OP was trying to make. Similarly, the third part of #3 is twice as likely as the first or second parts, whatever that really means. An interesting question then forms in my mind: Can we rank the different scenarios as to which is most likely, relative to each other? My guess is that #4 is the most likely event, but what about the others?

I design roads for a living - its a natural guess. Still took me a while because I couldn't find a sign or marking with "TC" except some obscure ones about ditches. Cherry did a good job to cut that O in half - I guess he must have been driving in the backwoods.

Hoki Hoki Hoki Hi

dawh you beat me to it...

Can you post the coordinate output for n=7 in a text file or something? I'm having trouble coming up with all 75 geometrically, and want to figure out where I'm wrong. Glad to know you're still thinking about this - I know I'm having a hard time letting it go.

Nice... I use CADD a lot, so having the coordinates from your program will make it easy for me to get a visual check on your output. I won't be able to work on it until Monday (at the earliest), so maybe the code will be a little more refined by then.

The promised picture:

I think you're right. I can envision a solution for n=7 consisting of 3 third-unit rectangles and 4 fourth-unit rectangles. That wouldn't be accounted for in my function, because it contains no unit or half-unit rectangles and I didn't introduce third-unit rectangles until n=9. Any guesses on an elegant description of this? I'm about mathed-out right now - my brain hurts!

That paragraph made no sense to me, even when I was writing it! This is what I mean: Every time that n=k^2, we add another set of possible solutions, which is why we need another term in the equation. The reason is that the first term describes all solutions that have at least one unit rectangle, but there are solutions which do not have any unit rectangles. For n = 4, the four-square solution is a good example. For n = 5, a solution with 2 half-unit rectangles and 3 third-unit rectangles is another example. There are no unit rectangles in either. The solutions we're looking for then correspond to the cases where there are k k-th unit rectangles (or k-1 [k-1]th unit rectangles, etc.) on one side of a line drawn across the square with all possible subdivisions of a rectangle into n-k equal area rectangles on the other side. These solutions do all exist in the set, but there are a good number of duplicates because many of them contain unit rectangles (or [k-1]th unit rectangles, etc.), which have already been counted. It turns out that square(n) is all of the unique solutions to rect(n) in one orientation (horizontal or vertical). One orientation will give a solution with a unit rectangle and the other will not, and the solution without the unit rectangle is the one you need for the k-th unit rectangle solutions. A picture of this can be seen where it occurs the first time, at n=4. The unit rectangle solutions for n=4 include a unit rectangle of dimension L x L/4 with all the possible subdivisions of the remaining L x 3L/4 rectangle into 3 equal area rectangles. Looking for half-unit rectangles, we see that there are two of them, but one has a unit rectangle already and the other does not. The solution without the unit rectangle is unique, and corresponds graphically to the unique solution of rect(2), which is square(2), so there are only square(2) = 1 additional unique solutions with half-unit rectangles. See the picture for the real graphical explanation. After understanding the first solution, the extrapolation to higher values of n and k becomes more obvious. Hopefully this is a better explanation!

Well, since no one's told me any different, I think I'm going to continue my line of reasoning and present a comprehensive solution for the rational portion of this problem. I propose that the best way to find the number of methods for subdividing a square into equal area rectangles, all of whose sides have lengths which can be expressed rationally, is to take the sum of all solutions including a unit rectangle (L x L/n) and all unique solutions including two half-unit rectangles (L/2 x 2L/n), three third-unit rectangles (L/3 x 3L/n), four fourth-unit rectangles (L/4 x 4L/n), etc. In order to do so, I define two functions: square(n) and rect(n), where: square(n) is the number of methods for subdividing a square into equal area rectangles, all of whose sides have lengths which can be expressed rationally (the target function) rect(n) is the number of methods for subdividing a rectangle into equal area rectangles, all of whose sides have lengths which can be expressed rationally. In general, rect(n) = 2*square(n), except for values of n which can be defined as k^2, where k is a non-negative integer. For values of n=k^2, rect(n) = 2*square(n) - 1. Further, I will define square(2) = rect(1) = 1. Then, it follows that: for n<=k^2, square(n) = rect(n-1) + [square(n-(2^2-2))+square(n-(3^2-2))+...+square(n-((k-1)^2-2))] Working out the problem: square(2) = 1 (by definition) square(3) = rect(2) = 2*square(2) = 2*1 = 2 square(4) = rect(3) + square(2) = 2*2 + 1 = 5 square(5) = rect(4) + square(3) = 2*5-1 + 2 = 11 square(6) = rect(5) + square(4) = 2*11 + 5 = 27 square(7) = rect(6) + square(5) = 2*27 + 11 = 65 square(8) = rect(7) + square(6) = 2*65 + 27 = 157 square(9) = rect(8) + square(7) + square(2) = 157*2 + 65 + 1 = 380 square(10) = rect(9) + square(8) + square(3) = 380*2 + 157 + 2 = 918 When the next term is added at square(16), there are 183,755 ways to divide the square square(25) = 520,157,803 square(36) = 8.612 E+12 Needless to say, we won't be drawing out the higher solutions to confirm! Here's the geometry behind my solution: For the unit rectangle portion of the function, what you're really doing is making a square by adding a unit rectangle to all possible subdivisions of another rectangle into n-1 equal area rectangles. For every other portion of the solution (half-unit rectangles, third-unit rectangles, etc.), the same is true that a portion of the overall solution is, for example, 2 half-unit rectangles with every possible subdivision of another rectangle into n-2 equal area rectangles. The problem is that this double-counts all the solutions which already have at least one unit rectangle. The way to avoid double-counting is by using square(n-2) instead of rect(n-2) [or square(n-7) instead of rect(n-7), and so on]. Graphically, I can illustrate that the unique solutions for rect(n) look like two sets of the unique solutions for square(n) - one oriented vertically, and the other oriented horizontally. (I'll work on that picture later and upload so you can see what I mean). For values of n where n=k^2, the horizontal and vertical orientations generate the same picture, and that is why rect(n) in these cases = 2*square(n)-1 instead of 2*square(n). Every time that n=k^2, we add another set of possible solutions, which is why we need another term in the equation. I have difficulty explaining in words why this is (maybe I'll edit the post later if I can come up with the right words), but it has to do with being able to get unique solutions by dividing the square in half, thirds, fourths, etc. and putting all the lower level rectangles into each of the half-squares, third-squares, fourth-squares, etc. Like I said, the words are not working for me right now! Taking a guess at the irrational solution, which is next (I guess), I think all that's necessary is to add another term to the equation for all n>4. That term would be square(n-4). I think this is because the central square contains all possible subdivisions of a square into n-4 equal area rectangles, and outside the central square are 4 other rectangles. I may have to make sure that works at n=8 and that we don't need to have another term that gets added when n=k*4. Okay, I'm done. Tear holes!

Agreed. At least for now - maybe we'll tackle the central square stuff later. For right now, the rational solutions are difficult enough. That being said, I might have found a pattern that holds for at least n<=6. I tried counting the number of solutions that contained at least one unit rectangle (ignoring irrational solutions) and got the following: f(n) = # with unit rect + # w/o unit rect f(2) = 1 + 0 = 1 f(3) = 2 + 0 = 2 f(4) = 4 + 1 = 5 f(5) = 9 + 2 = 11 f(6) = 22 + 5 = 27 At first, I was puzzled because an earlier post had stipulated that the number of solutions with at least one unit rectangle was 2*f(n-1), but that didn't hold true for f(5). Then I realized I was back to rectangles . The number of solutions with at least one unit rectangle is rect(n-1). I'm having a hard time defining rect(n) mathematically, but I can show graphically that rect(n) = 2*sq(n), except for n=4, where it's 9 instead of 10. I know it has something to do with the fact that 4 is a square number itself, but I can't get it out mathematically. I think that there is a geometric explanation for this first term being rect(n-1), but I'm having difficulty being eloquent about it. Basically, it's that every unit rectangle solution for n includes the unit rectangle and another rectangle which has been divided into n-1 parts. I don't have a good geometric reason for the second term, but it is starting to have a very familiar pattern: sq(n-2). I think that might have to do with the fact that the remaining solutions all have a pair of rectangles of dimension L/2 x 2L/n. But I'm not sure how to justify it. I'm not sure if a third term would be needed for n=9 where the next square number is encountered to handle the fact that I think will exist unique solutions with three rectangles of dimension L/3 x 3L/n. Carrying out my guesses to n=8, I get: f(7) = 54 + 11 = 65 f(8) = 130 + 22 = 152 Of course, I'm not sure these are right, and I'm not going to even try to go any further before I let somebody else tear this apart.

Whoops - you're right. Complexity increases at multiples of 4, not square numbers.

my last irrational post for a while Actually, the form of the irrational solutions begins at n>=k^2 for k>1 instead of n>=k^2 + 1. It just so happens that root 4 is not irrational. The level of complexity increases again at n=9=3^2 not at n=10=3^2+1. See below for n=9: I think the four-square solution to f(4) and the nine-square solution to f(9) are examples of irrational solutions that migrate from the irrational pattern to the rational one and will not fit the general rational solution we are looking for. Maybe we should try to develop a function that ignores those solutions (and their children for higher values of n) and come back to them later. So: f(2) = 1 f(3) = 2 f(4) = 4 f(5) = 10 f(6) = 24 Does that make sense to anyone? Or am I just being irrational?

graphic to go with my last post showing central square solutions for n=6,7,8 - I think this confirms the exclusion of irrational solutions for now. rhapsodize, I think this confirms that these type of solutions occur for all n>=k^2 + 1 for values of k>1, or simply for n>=5. The problem simply becomes more complex each time k increases.

oh boy. That brings a whole new level of complexity to this problem. If we call this the central square solution, I think we'll eventually find that there is a whole subset of central square solutions available for every n>=5. And the configuration of the central square is based on the available solutions for n-4 -- that is, the central square for n=5 is the same is the solution for n=1, but for n=6, you'll have all the solutions for n=2 contained in a central square with exterior dimensions sqrt(2/6). That adds two solutions to f(6) - one for the 12th f(5) solution with a unit rectangle and one for the f(6) solution with the central square, because f(2)=1. But when you look at f(7), you'll be adding even more, because the configuration of the central square is based on f(3)=2. And for f(8), the central square contains all the solutions for f(4)=5, and so on... And it may even be possible to have the central square be a rectangle instead (still working on the geometry here), which would add a whole other dimension to the problem, because the solutions would expand by rect(n) instead of square(n). [i insert here that I have now convinced myself that rect(n) does not equal 2*square(n) as I originally postulated - the four-square (or four-rectangle) solution to rect(4) throws a monkey wrench into that idea.] In some ways, this confirms a suspicion that I've had for a while. I've been wondering about what happens when we reach the next square number (9), because the four-square solution for n=4 caught me by surprise. Every other f(4) solution is repeated twice in f(5) except that four-square solution, because it's 90-degree rotation is a duplicate of itself. The same will happen for the nine-square solution in f(9) and I wonder if we're prepared to adequately count these square solutions as n increases. I'm beginning to think we have a post-graduate geometry problem on our hands here - I know that there is a significant body of work on efficient equal area divisions, but those tend to focus on finding the equal area subdivision while minimizing the cutting perimeter. Apparently there are industrial applications where they need to cut equal area shapes out of a larger shape, and these papers are trying to figure out how to do that with the least amount of cutting. See, for example, http://citeseer.ist.psu.edu/cache/papers/c...se98cutting.pdf.

I would love to see it done - problem is we don't have a mathematical means to filter out duplicates yet, so I'm not sure how the program would work. If that's the case, then we're wrong on n=6 as well, because all the n=5 cases are used in the n=6 drawings. We'd have to add at least one more solution to n=6 to account for the new n=5 solution you see. If it's unique, can you post an image? My thoughts on combinations have come to a screeching halt - I keep running into the same duplicate filter issues we've been dealing with. What a good puzzle - I just hope it actually has an elegant solution.

I think essentially what we are seeing is a combination, or a sum of combinations, which might be the mathematical means to express the solution. Working on it...

What you're missing is that you have to stop recursing when you hit 2*square(n/2) (or for odd numbers, 2*square(n/2+0.5)). I included that qualifier in my previously unsuccessful formula, but failed to restate it last time. The reason is you stop recursing, I think, is that you begin double counting because, for example, rectangles of 5 and 2 are the same as rectangles of 2 and 5. So: square(7) = 2*square(6) + 2*square(5) + 2*square(4) - 27 = 2(27+11+5) - 27 = 59. I'm still not sure that 59 is correct though - no one's drawn it out. For now, I'm thinking about other means to this same end - I've been looking at the possible side lengths and at whether I can recurse all the way down to square(1) in some logical fashion. Nothing so far... I'm hoping the recursion will work, though, because it might aid my drawing process when I go to prove that it works for square(7) or higher.

Substituting in the corrected value of square(6)=27, I've got another possible solution: square(n)=rect(n-1)+rect(n-2)+...+rect(n/2)-3^(n-4) where rect(n) = 2*square(n) That would give square(7)=59, which is the solution The Giant Panda came up with. Of course, the last term still gives me the heebie-jeebies. The problem is that it is so difficult to validate any solution without drawing it out for the next few values of n - just discovering patterns (which is a large part of what I've been doing) doesn't necessarily work more than a few iterations out. I wish I could come up with the geometric proof. It's out there somewhere...