|
||
|
Title: Willy's true colors Post by James Fingas on Sep 16th, 2002, 10:25am Willywutang recently took a personality test ... he failed ;) Actually, the test was set up so he couldn't fail. There were four personality "colors", and the objective was to decide which color was strongest in him. There were three test sections, and in each section, he had to rank the four colors from 1 (weakest) to 4 (strongest). At the end of the test, he summed up the rankings from each section to get his personality "profile". The minimum he could score on any color was therefore 3, and the maximum was 12. After he knew how he scored for each color, the test asked him to color in a circle (with crayons) in proportion to his color scores. Willywutang complained that he didn't have a protractor to measure out the exact angles. (I wonder what this says about his personality?) Willywutang then remarked loudly that the test makers could have divided up the circle beforehand (pie-chart style) and then he would only have to color between the lines. The natural question is, of course: What is the minimum number of divisions that must be made so that the circle can be colored to accurately represent any possible proportion of colors? How are these divisions arranged? |
||
|
Title: Re: NEW PROBLEM: Willy's true colors Post by Eric Yeh on Sep 16th, 2002, 1:21pm I am guessing that the colorings must be contiguous, and that furthermore all divisions are meant to be radial? With this definition, I can get it down to 18 divisions, but that is only with five or ten minutes of thinking. I am sure there is something better. Eric |
||
|
Title: Re: NEW PROBLEM: Willy's true colors Post by James Fingas on Sep 16th, 2002, 2:09pm I think the problem is harder to conceptualize with contiguous colorings, but I ask you: do you think that it changes the solution? As for radial divisions, I again ask you: does that change the solution? |
||
|
Title: Re: NEW PROBLEM: Willy's true colors Post by Eric Yeh on Sep 16th, 2002, 2:40pm Intuitively, it seems that those two questions do matter. Certainly it is a lot easier without them! For example, it takes less than a minute to reduce the 18 to 10 in the "looser" setting, something which I wouldn't be able to see how to arrange in a contiguous-radial setting. (I guess I've been forgetting to use the min/max part of the problem though.) On the other hand, the way you ask the question suggests that it is irrelevant. |
||
|
Title: Re: NEW PROBLEM: Willy's true colors Post by James Fingas on Sep 17th, 2002, 12:58pm I have considered both the contiguous and non-contiguous cases. I won't tell you if the answers I have are different, but I haven't been able to prove whether or not they should be in the general case. As for the radial vs. non-radial question, this may affect the contiguous-case solution, leading to an interesting mix of packing and topology in the final answer. For the time being, you can consider the radial case, since this is probably what Willywutang was thinking of (or he would have asked for a protractor, a ruler, and a calculator). Really, we have three cases: - non-contiguous - contiguous non-radial - contiguous radial Some of these are probably equivalent. Later on, I'll ask you to generalize for non-radial divisions... |
||
|
Title: Re: Willy's true colors Post by tohuvabohu on Jul 28th, 2003, 8:01pm Reopening a dead file after Icarus mentioned it, I think I have a partial answer. In the non-contiguous case, you can do it in 9 sections of [hide] 8,6,5,3,2,2,2,1,1 [/hide]. The same will work for the contiguous, non-radial case. The contiguous radial case, I'm not at all sure about, but I think I got it down to 13 sections of [hide]8,1,6,1,1,1,1,2,1,1,4,1,2 [/hide]. |
||
|
Title: Re: Willy's true colors Post by James Fingas on Jul 30th, 2003, 1:44pm tohuvabohu, I think your contiguous radial solution matches mine, but I seem to recall being able to shave one more division off of the contiguous non-radial case (I'm not sure because I've thrown out my solution!). There is a definite possibility of improving the radial case, but I was able to show that my non-radial solution was optimal (by trying all the combinations with fewer divisions). |
||
|
Title: Re: Willy's true colors Post by Icarus on Aug 4th, 2003, 7:17pm I have been playing with this the hard way (by spreadsheet and a little ingenuity). Here is what I have discovered so far: There are 37 possible values for the 4 colors (w/o regard to order). They are (expressed as hexadecimals): 369C 36AB 378C 379B 37AA 388B 389A 3999 459C 45AB 468C 469B 46AA 477C 478B 479A 488A 4899 558C 559B 55AA 567C 568B 569A 577B 578A 5799 5889 666C 667B 668A 6699 677A 6789 6888 7779 7788 The 6888 and 7788 arrangements mean that the largest single region can have a size of 8 (that is, 8/30 of the area of the circle). For the contiguous cases, the 6888, and 6699 arrangements also require that any region of size 7 or 8 must be adjacent to a region of size 1. Since the sum of the 4 color values is always 30, any division of the circle into smaller regions represents a partition of 30 (a set of smaller positive numbers whose sum is 30). I have restricted my attention to integer partitions only (though I have not justified doing so). An exhausting, if not exhaustive, search shows that no partitions with 7 or fewer members can be grouped to match all the values listed above, but 11 partitions of 8 members can: 11234568, 12334458, 11334567, 12234567, 12333567, 12334557, 12334566, 12344556, 22334556, 13344456, 23334456 (For example, 477C comes from 123344556 by (4) (3+4) (2+5) (1+5+6).) Any of the 11 partitions solves the non-contiguous puzzle. I haven't made much progress on the contiguous puzzles, because my current methods are too cumbersome. |
||
|
Title: Re: Willy's true colors Post by James Fingas on Aug 5th, 2003, 11:35am Icarus, Very good! I had seven of those, and had incorrectly tossed the eighth. Yes, it is an exhausting puzzle... I have a pretty interesting spreadsheet (just one sheet!) which allows me to simulate the contiguous case (it took way too long to try out solutions the old way). There are a large number of 12-division solutions that work, and it seems like an 11-division solution should be possible, but it remains just out of my grasp... If you're interested, here's how I've layed out my spreadsheet to accomplish this amazing feat: RAAAAA BBBBB BBBBB C DDDDD EFFFFF G C DDDDD EFFFFF G C DDDDD EFFFFF G Section A is a zero-and-one encoding of a possible solution (e.g. 100110111000001100100000101100 would be used to encode 312116136213). Section B lists all rotations of that solution. Section C contains is four columns wide and contains all the required colourings and their permutations (colourings are hand-generated, permutations aren't). Section D expands those into zero-and-one encoding. Section E calculates the inner product of the rows of D with row A. Section F calculates all inner products of rows D with rows B. Section G calculates, from the inner products, whether each colouring is satisfied by the possible solution. Section R (for "results") aggregates these results to tell you whether the possible solution works. I also display some intermediate results that I use to test other possibilities near a solution. So far I've found 9 working 12-division solutions, and some near-solutions with 11 divisions. |
||
|
Title: Re: Willy's true colors Post by SWF on Aug 5th, 2003, 9:47pm Well done, Icaraus. I also verified that those are the only solutions using only 8 integers and that 7 is not possible. Even with the list of possible solutions, finding a map with 8 regions that can always be colored with like colors contiguous proved to be much more challenging than expected:
|
||
|
Title: Re: Willy's true colors Post by James Fingas on Aug 6th, 2003, 9:50am SWF, Looks nice and simple. There are arrangements for 2 3 3 3 4 4 5 6 and 1 1 2 3 4 5 6 8 that I've found (the latter was a real bugger!). It's very likely that all divisions have arrangements that allow the colours to remain contiguous, but I don't think I'll try to find them... |
||
|
Title: Re: Willy's true colors Post by SWF on Aug 6th, 2003, 8:31pm For like color regions to be contiguous with all regions formed from radial cuts on a circle, computer search shows it is not possible to do with 10 or fewer regions, but here is a way to do it with 11: [hide]1 2 4 1 4 3 3 5 1 4 2[/hide] Although this is the last one of the three problems solved (non-contiguous, contiguous, contiguous-radial) this one turned out to be the easiest since mindless computer search can check the possiblities fairly easily. The constraint that values be joined only with those adjacent on the list reduces the number of cases to be searched. |
||
|
Title: Re: Willy's true colors Post by James Fingas on Aug 7th, 2003, 9:12am SWF, Very nice. There are a few simplifications that can reduce the search. Notice that for colourings like 6 8 8 8, there is only one permutation that is different up to rotation. Coupling that with the other similar colourings (6 6 6 12, 7 7 7 9, 9 9 9 3) should allow a fairly efficient search. To try these together in all rotations should use up at least 8 or 9 of your 11 divisions, while only requiring 303 = 27000 combinations. Too many to do by hand, but ridiculously easy for a computer program. But perhaps that's what you did... |
||
|
Title: Re: Willy's true colors Post by Icarus on Aug 8th, 2003, 4:07pm I've been looking into finding all partitions of 30 which solve the non-contiguous problem. I've found a result that makes the task considerably smaller: First some definitions. (I can't help it. I'm a mathematician. This is the way we think!) A partition of N is a collection of positive integers <= N whose some is N. The integers do not need to be distinct. The order of a partition is the cardinality of the collection. A partition P is a refinement of a partition Q if P is the union of partitions of each of the elements of Q. Thus the problem is to find all partitions of 30 which are refinements of all of the 37 order 4 partitions given. The result is this: Lemma: [forall] N, k [in] [bbn], a partition P is a refinement of ALL partitions of N of order k if it satisfies: Proof: Suppose the lemma is false. Then there must be a partition Q of order k that P does not refine. Consider the elements of Q to be k containers to be filled. A refinement of Q by P consists of distributing the elements of P amongst the k containers so that they are all exactly filled. Since P does not refine Q, any such attempt is doomed to fail. There will always be a leftover x' in P that does not fit in the remaining room of the k containers. Of all the leftover x' from all attempted refinements, let x be the smallest, and consider the attemped refinement it came from. There is room in the containers adding up to at least x (since the sum of the container sizes is N, as is the sum of P). Remove all the elements of P smaller than x from the containers. By the condition, the sum of these elements is greater than (k-1)x - k, which brings the total open spots up to more than (k-1)x - k + x = kx-k = k(x-1). At least one of the k containers must therefore have an opening of size at least x. Placing x in that container and refilling as possible with the removed elements provides an attempted refinement of Q by P with a smaller leftover than x, which is absurd. [QED] Using this rule, and the restriction that all partitions of 30 refining the 37 listed order 4 partitions must have a highest element of 8 or less, you can reduce the 5604 partitions of 30 down into 3 groups: Those with highest element >8, which will not work. Those meeting the condition, which work for not only the 37 listed partitions, but all other order 4 partitions as well (the smallest of these has 10 elements). And the third group, which needs closer examination. This third group has a much more managable 1372 entries. The group meeting the condition has a little over 1000 entries. |
||
|
Title: Re: Willy's true colors Post by Icarus on Aug 14th, 2003, 7:56pm Even though it is now solved (I'll get around to updating my list sometime), I've still been playing with this one, just to see what works and what doesn't. I've found that there are exactly 1406 solutions to the non-contiguous puzzle. Which of these can be turned into solutions of the two contiguous cases is another matter. The partitions are shown as hexadecimal numbers. The K's digit of the number gives the # of occurences of K in the partition. For instance, A00 represents the partition 3+3+3+3+3+3+3+3+3+3 (10 threes, 0 twos, 0 ones - and 0 everything else), while 1810 represents 4+3+3+3+3+3+3+3+3+2 (1 four, 3 threes, 1 two, and 0 ones). Of the partitions that did not work, all but 184 of them failed to meet at least one of these five properties of all working partitions: 1) The maximum element is 8 or less. 2) There is at most 1 element >6 3) There are at most 2 elements >5 4) There are at most 3 elements >4 5) There are at least 4 odd elements. These clearly follow from the requirement to refine the size 4 partitions 6668 (for 1 & 2), 459C (for 3 & 4), and 7779 (for 5) (The size 4 partitions are expressed in the same format as in the post I listed them in above). The 184 partitions meeting these requirements, but still failing to work are: 10111201, 10110221, 10010510, 114003, 1100340, 30403, 1000370, 10022101, 10021121, 1100510, 33003, 1011240, 6103, 8301112101, 1022021, 10002410, 10100412, 31140, 10000612, 6006, 1023001, 10101311, 1011410, 1004112, 10001430, 1000702, 903, 10110310, 10020311, 201410, 24012, 1010430, 101602, 10021210, 1102211, 120410, 10010502, 200430, 20602, 1111210, 1013111, 1003310, 1100502, 1002330, 1020061, 1022110, 33011, 31310, 10002402, 30330, 31051, 10101400, 10100501, 23210, 201402, 10000620, 10000531, 10020400, 10011401, 10001600, 120402, 1001520, 100711, 1110400, 1101401, 1010600, 1003302, 110520, 10801, 10012300, 1020401, 200600, 31302, 1000710, 2701, 1102300, 210401, 1002500, 15102, 101610, 1010260, 1021300, 10003301, 111500, 10020141, 20610, 30160, 211300, 1012301, 30500, 1021041, 4410, 10000450, 1013200, 202301, 103400, 10100331, 100800, 1001350, 122200, 121301, 22400, 32031, 11700, 1000540, 33100, 1004201, 14300, 10010421, 3600, 100630, 10112003, 32201, 10103004, 10001511, 10013005, 10720, 10022012, 24101, 10022004, 200511, 1103005, 1810, 1112012, 10020230, 1112004, 1002411, 212005, A00, 10110302, 1110230, 10013013, 30411, 10004014, 10004006, 10102202, 1021130, 1103013, 10000701, 203014, 203006, 10021202, 10100420, 212013, 1001601, 10100404, 15005, 10013102, 10011320, 10101303, 110601, 1004104, 6014, 1103102, 1101320, 10020303, 102501, 105004, 10000604, 1022102, 1020320, 10004103, 21501, 24004, 100703, 212102, 210320, 1013103, 5301, 15013, 1802, 1014002, 1012220, 203103, 1020150, 10001503, 30071, 123002, 32120, 1005003, 10010340, 200503, 911 Most of these fail because they are unable to refine these size 4 partitions: 666C, 7779, 6888, 3999. Of the working partitions, they break down by size: Size # of partitions |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |