Before you die of tetanus
File under: geometry, numerical optimization, multiobjective optimization
Inspired by: This post at Notional Slurry
You are at the summer cottage. Alas, the weather is gray and chill and blustery, and there is nothing to do. The cottage, you will recall, is devoid of civilized amenities such as computers and televisions, having been created solely for the infuriation of young persons.
Grandmama points out, however, that there is the Rainy Day Cupboard. What is in it, you ask? Several dried husks of decorative indian corn, nibbled by mice; a number of desiccated stingray egg cases, stinking of distant seas and Clorox; an edition of Scrabble missing twelve letter tiles; five jigsaw puzzles; a television antenna (what?); and a mysterious frame.
When you encounter this frame, you initially mistake it for a picture frame: it is of sturdy wood, and rectangular and open like a picture frame. But unlike most such mundane objects this one is fashioned from a dark and glistening wood, and has many ornately fashioned little sharp nails or pins sticking out of it, which have apparently collected lint and dust and rust through the years -- ouch!
After Grandmama nurses your finger with a magic Band-Aid, you ask her about the frame, which possesses a strange allure for you now that it has tasted of your very life's blood. Grandmama tells you that many, many years ago, a thing called string art was very popular, before being suppressed by right-thinking people. What you have found in the Rainy Day Cupboard is, in fact, a partially-completed String Art project. Would you like to finish it, she asks?
How would you do that?
Well, she says, one supposes one would tie string between the nails. Ahh, of course. String art! You warily approach the apparatus, and your well-trained little eye notes that there are 100 of the pins sticking up from one of the members of the frame, and 100 pins sticking up from the opposite edge. It is an amazing piece of folk craftsmanship you realize, because the pins are placed with absolute precision at equal distance along the frame. Whoever this long-dead master pin-setter was, he must surely have been a leader among string artisans!
(As noted, you have an eye for these things. You have watched Find many times with Mummy. It is fun to try to identify the Keno Brothers. One, you have learned, is actually a rather well-designed CGI program....)
As Grandmama hands you some of her sewing thread to play with, she notes with a sudden intake of breath the increasingly painful swelling afflicting your Band-Aided finger. A look of concern passes over her face, and she pats you on the head and tells you to play nice -- but carefully -- while she goes and makes a call on the telephone to Mummy. Mummy is digging for old bones in Uzbekistan, you know, so she will be very cross at being awakened.
Outside, the gray day appears to be getting rather stormy, and whitecaps are crashing on the strand outside the cottage window....
So, you think: Let us label the 100 pins on the left member of this mysterious frame, starting at the top, as L1 through L100. Similarly, we shall label the pins on the right member as R1 at the top, and R100 at the bottom. How cunning your fevered mind is becoming! Now. If I were to tie a string tightly to pin L1, and stretch it ever so tightly across the frame to R1 and tie it there, then... well, I'd have connected two pins. And I could continue in that ways until I had tied each of Li to Ri in turn. It would look something like a harp, I imagine. And I could strum it, tra-la!
A frown passes over your face, as the wind picks up a bit, and the lights flash briefly off and on. You absentmindedly rub your forearm, where a dull ache is encroaching.
Now, that wouldn't be very artistic would it? Grandmama said it was string art, so I shall make the lines cross! Yes! So, if I were instead to connect pin L1 to R100, and L2 to R99, and so on, then every string would cross. But... well, the master pin-setter has done such a wonderful job that there would in fact be only one crossing point, in the very center. While conceptually interesting to those who prefer a minimalist aesthetic, I would like a bit more challenge.
You frown a bit. Rain pelts the windows, and Grandmama is speaking quickly and rather loudly to somebody on the telephone now.
I have it! I shall connect the pins to one another in such a way as to maximize the number of crossings. I shall connect each of 100 strings from one bare left pin to one bare right pin, and count how many crossings there are. I shall be happiest if the number the maximum possible!
Sweat gleams upon your little brow as you set to work. Above, you hear the stormcock squawking as it pivots madly on the roof....
Questions #1: Presuming that Mummy was not so very busy that she has forgotten your booster shots, and that in any case Grandmama has reached the proper authorities before the storm has closed off the causeway, in what pattern do you tie the strings?
Here is a picture of just one way to connect the 100 pins on the left to the 100 pins on the right:
And here is a picture of where the crossings exist in that particular pattern of connections:
Question #2: Having completed the first task appointed you (appointed? By whom? No matter! The work is fascinating!), this business of tying only bare pins to one another begins to chafe. Suppose instead we were released to tie the 100 sacred strings between any pairs of pins on opposite sides. That is, some pins might be left bare, and others be tied to multiple pegs on the other side. So long as no two strings coincide (are tied to the same left and right pins), what can be done to improve the number of total crossings? There must be more crossings!
Question #3: [Programming] As the infection advances -- for it is no normal tetanus, but rather the very Curse of the Penultimate String Artist creeping towards your heart -- you undertake many, many different arrangements of 100 lengths of string. You notice that for arbitrary tying patterns the majority of crossings tend to cluster in the middle of the frame.
Unlike minimalism, this inspires your growing mystical sensibility, and you decide that you would like to add an missing aspect of balance to your work: You still want to try to maximize the overall number of crossings of the strings (you are not allowed to do otherwise by HIM), but at the same time must minimize the difference between the number of crossings at any horizontal point across the frame.
What you will do is this: once a particular arrangement of strings has been tied, you will use a circular beer mat (which is 1/21 the width of the frame) to determine how many crossings are anywhere from the top to the bottom of the frame in the span measured out by the width of the mat. In effect you'll "scan" across a 1/21 portion of the frame's width, and count how many crossings lie in that fraction. You are full of pep and curse, now, so can be very accurate in your measurements so that you may find a pleasantly balanced arrangement of strings before Grandmama's shrieking makes you raise your little glowing eyes from your Great Work.
Here, for example, is what it looks like when you count the number of crossings that lie in every possible beer-mat's-width of the previous example. There are anywhere between about 55 and 165 crossings in the various windows -- far too much variation to please HIM, surely!
Now you have two goals: try to ensure that there is no arrangement that (a) has more crossings and (b) has less variation in the number of crossings across the frame. You may have fewer crossings than what you found in the previous ritual, if the new arrangement is simultaneously better on both goals than all others. How are the strings best arranged?
Question #4: [Programming] Grandmama's crumpled form lies in the corner, the lights are off and lightning flashes all around the cottage... but that is no matter to you. You no longer need to see with mortal eyes in order to complete the Final Gateway Opening Arrangement. The beer mat will still prove useful, regardless of the noisome stains which have splashed it: Again you must maximize the number of crossings. But now you must simultaneously minimize the difference in the number of crossings strictly covered by the circular beer mat! It is 1/21 of the width, and 1/13 of the height of the frame. Now that Grandmama is watching you blandly with her cold eyes, you will have time to take the requisite 31,213 samples of random discs from the (rectangular) frame. If the strings are arranged correctly... THEY will be able to come and play with you! Hurrah! Iä!
Here is what it might look like after you have thrown the beer mat randomly a number of times onto the framework. The green circles indicate the part of the pattern that is covered by the mat on each throw:
Bonus question #1: Suppose that the pin-setter had not been so masterful. How many more crossings (if any) could be achieved if the 100 pins on the right-hand member were located wherever you wanted them to be?
Bonus question #2: Suppose that the frame was a circle, and that the 200 pins were arranged equidistant along the circumference. How many crossings are possible with only one string tied to each pin? With more than one string allowed at a pin?
Bonus question #3: Again, suppose that randomly throwing the circular beer mat (1/21 of the diameter of the circular frame) is the method used to sample the number of crossings covered by 31,213 discs, in order to simultaneously maximize the number of crossings, and even out the spatial distribution of the crossings. What is the best arrangement of the 100 strings?
Bonus question #4: In every case so far where you have been trying to be "even," as well as maximizing the number of crossings, one suspects that there is some arrangement of strings that is maximally even (but not trivially; there have to be some crossings) -- even though this might not maximize the number of crossings. What are the arrangements for the rectangle and the circle, for both single-tied and multi-tied pins, that are the most spatially balanced in two dimensions, which contain one or more crossings? If you can discover this, you may save the world.
Inspired by: This post at Notional Slurry
You are at the summer cottage. Alas, the weather is gray and chill and blustery, and there is nothing to do. The cottage, you will recall, is devoid of civilized amenities such as computers and televisions, having been created solely for the infuriation of young persons.
Grandmama points out, however, that there is the Rainy Day Cupboard. What is in it, you ask? Several dried husks of decorative indian corn, nibbled by mice; a number of desiccated stingray egg cases, stinking of distant seas and Clorox; an edition of Scrabble missing twelve letter tiles; five jigsaw puzzles; a television antenna (what?); and a mysterious frame.
When you encounter this frame, you initially mistake it for a picture frame: it is of sturdy wood, and rectangular and open like a picture frame. But unlike most such mundane objects this one is fashioned from a dark and glistening wood, and has many ornately fashioned little sharp nails or pins sticking out of it, which have apparently collected lint and dust and rust through the years -- ouch!
After Grandmama nurses your finger with a magic Band-Aid, you ask her about the frame, which possesses a strange allure for you now that it has tasted of your very life's blood. Grandmama tells you that many, many years ago, a thing called string art was very popular, before being suppressed by right-thinking people. What you have found in the Rainy Day Cupboard is, in fact, a partially-completed String Art project. Would you like to finish it, she asks?
How would you do that?
Well, she says, one supposes one would tie string between the nails. Ahh, of course. String art! You warily approach the apparatus, and your well-trained little eye notes that there are 100 of the pins sticking up from one of the members of the frame, and 100 pins sticking up from the opposite edge. It is an amazing piece of folk craftsmanship you realize, because the pins are placed with absolute precision at equal distance along the frame. Whoever this long-dead master pin-setter was, he must surely have been a leader among string artisans!
(As noted, you have an eye for these things. You have watched Find many times with Mummy. It is fun to try to identify the Keno Brothers. One, you have learned, is actually a rather well-designed CGI program....)
As Grandmama hands you some of her sewing thread to play with, she notes with a sudden intake of breath the increasingly painful swelling afflicting your Band-Aided finger. A look of concern passes over her face, and she pats you on the head and tells you to play nice -- but carefully -- while she goes and makes a call on the telephone to Mummy. Mummy is digging for old bones in Uzbekistan, you know, so she will be very cross at being awakened.
Outside, the gray day appears to be getting rather stormy, and whitecaps are crashing on the strand outside the cottage window....
So, you think: Let us label the 100 pins on the left member of this mysterious frame, starting at the top, as L1 through L100. Similarly, we shall label the pins on the right member as R1 at the top, and R100 at the bottom. How cunning your fevered mind is becoming! Now. If I were to tie a string tightly to pin L1, and stretch it ever so tightly across the frame to R1 and tie it there, then... well, I'd have connected two pins. And I could continue in that ways until I had tied each of Li to Ri in turn. It would look something like a harp, I imagine. And I could strum it, tra-la!
A frown passes over your face, as the wind picks up a bit, and the lights flash briefly off and on. You absentmindedly rub your forearm, where a dull ache is encroaching.
Now, that wouldn't be very artistic would it? Grandmama said it was string art, so I shall make the lines cross! Yes! So, if I were instead to connect pin L1 to R100, and L2 to R99, and so on, then every string would cross. But... well, the master pin-setter has done such a wonderful job that there would in fact be only one crossing point, in the very center. While conceptually interesting to those who prefer a minimalist aesthetic, I would like a bit more challenge.
You frown a bit. Rain pelts the windows, and Grandmama is speaking quickly and rather loudly to somebody on the telephone now.
I have it! I shall connect the pins to one another in such a way as to maximize the number of crossings. I shall connect each of 100 strings from one bare left pin to one bare right pin, and count how many crossings there are. I shall be happiest if the number the maximum possible!
Sweat gleams upon your little brow as you set to work. Above, you hear the stormcock squawking as it pivots madly on the roof....
Questions #1: Presuming that Mummy was not so very busy that she has forgotten your booster shots, and that in any case Grandmama has reached the proper authorities before the storm has closed off the causeway, in what pattern do you tie the strings?
Here is a picture of just one way to connect the 100 pins on the left to the 100 pins on the right:
And here is a picture of where the crossings exist in that particular pattern of connections:
Question #2: Having completed the first task appointed you (appointed? By whom? No matter! The work is fascinating!), this business of tying only bare pins to one another begins to chafe. Suppose instead we were released to tie the 100 sacred strings between any pairs of pins on opposite sides. That is, some pins might be left bare, and others be tied to multiple pegs on the other side. So long as no two strings coincide (are tied to the same left and right pins), what can be done to improve the number of total crossings? There must be more crossings!
Question #3: [Programming] As the infection advances -- for it is no normal tetanus, but rather the very Curse of the Penultimate String Artist creeping towards your heart -- you undertake many, many different arrangements of 100 lengths of string. You notice that for arbitrary tying patterns the majority of crossings tend to cluster in the middle of the frame.
Unlike minimalism, this inspires your growing mystical sensibility, and you decide that you would like to add an missing aspect of balance to your work: You still want to try to maximize the overall number of crossings of the strings (you are not allowed to do otherwise by HIM), but at the same time must minimize the difference between the number of crossings at any horizontal point across the frame.
What you will do is this: once a particular arrangement of strings has been tied, you will use a circular beer mat (which is 1/21 the width of the frame) to determine how many crossings are anywhere from the top to the bottom of the frame in the span measured out by the width of the mat. In effect you'll "scan" across a 1/21 portion of the frame's width, and count how many crossings lie in that fraction. You are full of pep and curse, now, so can be very accurate in your measurements so that you may find a pleasantly balanced arrangement of strings before Grandmama's shrieking makes you raise your little glowing eyes from your Great Work.
Here, for example, is what it looks like when you count the number of crossings that lie in every possible beer-mat's-width of the previous example. There are anywhere between about 55 and 165 crossings in the various windows -- far too much variation to please HIM, surely!
Now you have two goals: try to ensure that there is no arrangement that (a) has more crossings and (b) has less variation in the number of crossings across the frame. You may have fewer crossings than what you found in the previous ritual, if the new arrangement is simultaneously better on both goals than all others. How are the strings best arranged?
Question #4: [Programming] Grandmama's crumpled form lies in the corner, the lights are off and lightning flashes all around the cottage... but that is no matter to you. You no longer need to see with mortal eyes in order to complete the Final Gateway Opening Arrangement. The beer mat will still prove useful, regardless of the noisome stains which have splashed it: Again you must maximize the number of crossings. But now you must simultaneously minimize the difference in the number of crossings strictly covered by the circular beer mat! It is 1/21 of the width, and 1/13 of the height of the frame. Now that Grandmama is watching you blandly with her cold eyes, you will have time to take the requisite 31,213 samples of random discs from the (rectangular) frame. If the strings are arranged correctly... THEY will be able to come and play with you! Hurrah! Iä!
Here is what it might look like after you have thrown the beer mat randomly a number of times onto the framework. The green circles indicate the part of the pattern that is covered by the mat on each throw:
Bonus question #1: Suppose that the pin-setter had not been so masterful. How many more crossings (if any) could be achieved if the 100 pins on the right-hand member were located wherever you wanted them to be?
Bonus question #2: Suppose that the frame was a circle, and that the 200 pins were arranged equidistant along the circumference. How many crossings are possible with only one string tied to each pin? With more than one string allowed at a pin?
Bonus question #3: Again, suppose that randomly throwing the circular beer mat (1/21 of the diameter of the circular frame) is the method used to sample the number of crossings covered by 31,213 discs, in order to simultaneously maximize the number of crossings, and even out the spatial distribution of the crossings. What is the best arrangement of the 100 strings?
Bonus question #4: In every case so far where you have been trying to be "even," as well as maximizing the number of crossings, one suspects that there is some arrangement of strings that is maximally even (but not trivially; there have to be some crossings) -- even though this might not maximize the number of crossings. What are the arrangements for the rectangle and the circle, for both single-tied and multi-tied pins, that are the most spatially balanced in two dimensions, which contain one or more crossings? If you can discover this, you may save the world.
posted by Vaguery | 8:40:00 PM
<< Home