Author 
Topic: Willy's true colors (Read 4205 times) 

James Fingas
Uberpuzzler
Gender:
Posts: 949


Willy's true colors
« on: Sep 16^{th}, 2002, 10:25am » 
Quote Modify

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 (piechart 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?

« Last Edit: Nov 7^{th}, 2002, 11:30am by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Willy's true colors
« Reply #1 on: Sep 16^{th}, 2002, 1:21pm » 
Quote Modify

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


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: NEW PROBLEM: Willy's true colors
« Reply #2 on: Sep 16^{th}, 2002, 2:09pm » 
Quote Modify

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?


IP Logged 
Doc, I'm addicted to advice! What should I do?



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Willy's true colors
« Reply #3 on: Sep 16^{th}, 2002, 2:40pm » 
Quote Modify

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 contiguousradial 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.

« Last Edit: Sep 16^{th}, 2002, 2:41pm by Eric Yeh » 
IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: NEW PROBLEM: Willy's true colors
« Reply #4 on: Sep 17^{th}, 2002, 12:58pm » 
Quote Modify

I have considered both the contiguous and noncontiguous 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. nonradial question, this may affect the contiguouscase 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:  noncontiguous  contiguous nonradial  contiguous radial Some of these are probably equivalent. Later on, I'll ask you to generalize for nonradial divisions...

« Last Edit: Sep 17^{th}, 2002, 1:57pm by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



tohuvabohu
Junior Member
Gender:
Posts: 102


Re: Willy's true colors
« Reply #5 on: Jul 28^{th}, 2003, 8:01pm » 
Quote Modify

Reopening a dead file after Icarus mentioned it, I think I have a partial answer. In the noncontiguous case, you can do it in 9 sections of 8,6,5,3,2,2,2,1,1 . The same will work for the contiguous, nonradial case. The contiguous radial case, I'm not at all sure about, but I think I got it down to 13 sections of 8,1,6,1,1,1,1,2,1,1,4,1,2 .


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Willy's true colors
« Reply #6 on: Jul 30^{th}, 2003, 1:44pm » 
Quote Modify

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 nonradial 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 nonradial solution was optimal (by trying all the combinations with fewer divisions).


IP Logged 
Doc, I'm addicted to advice! What should I do?



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Willy's true colors
« Reply #7 on: Aug 4^{th}, 2003, 7:17pm » 
Quote Modify

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 noncontiguous puzzle. I haven't made much progress on the contiguous puzzles, because my current methods are too cumbersome.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Willy's true colors
« Reply #8 on: Aug 5^{th}, 2003, 11:35am » 
Quote Modify

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 12division solutions that work, and it seems like an 11division 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 zeroandone 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 handgenerated, permutations aren't). Section D expands those into zeroandone 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 12division solutions, and some nearsolutions with 11 divisions.


IP Logged 
Doc, I'm addicted to advice! What should I do?



SWF
Uberpuzzler
Posts: 879


Re: Willy's true colors
« Reply #9 on: Aug 5^{th}, 2003, 9:47pm » 
Quote Modify

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: ++ .........3......... ++++... ............... .......5..3.... ....2.......... ......+... .5.............. ............. .........6...... ....2........... ................ +++ ................... .........4......... ................... ++


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Willy's true colors
« Reply #10 on: Aug 6^{th}, 2003, 9:50am » 
Quote Modify

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...


IP Logged 
Doc, I'm addicted to advice! What should I do?



SWF
Uberpuzzler
Posts: 879


Re: Willy's true colors
« Reply #11 on: Aug 6^{th}, 2003, 8:31pm » 
Quote Modify

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: 1 2 4 1 4 3 3 5 1 4 2 Although this is the last one of the three problems solved (noncontiguous, contiguous, contiguousradial) 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.


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Willy's true colors
« Reply #12 on: Aug 7^{th}, 2003, 9:12am » 
Quote Modify

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 30^{3} = 27000 combinations. Too many to do by hand, but ridiculously easy for a computer program. But perhaps that's what you did...


IP Logged 
Doc, I'm addicted to advice! What should I do?



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Willy's true colors
« Reply #13 on: Aug 8^{th}, 2003, 4:07pm » 
Quote Modify

I've been looking into finding all partitions of 30 which solve the noncontiguous 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: [forall] x [in] P, ([sum]_{y [epsilon] P, y<x} y ) > (k  1)x  k. 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 (k1)x  k, which brings the total open spots up to more than (k1)x  k + x = kxk = k(x1). 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.

« Last Edit: Aug 16^{th}, 2003, 9:34am by Icarus » 
IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Willy's true colors
« Reply #14 on: Aug 14^{th}, 2003, 7:56pm » 
Quote Modify

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 noncontiguous 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 8 11 9 68 10 133 11 168 12 175 13 162 14 143 15 121 16 100 17 80 18 64 19 49 20 38 21 28 22 21 23 15 24 11 25 7 26 5 27 3 28 2 29 1 30 1

« Last Edit: Aug 14^{th}, 2003, 9:04pm by Icarus » 
IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



