Author |
Topic: Willy's true colors (Read 4332 times) |
|
James Fingas
Uberpuzzler
Gender: 
Posts: 949
|
 |
Willy's true colors
« on: Sep 16th, 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 (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?
|
| « Last Edit: Nov 7th, 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 16th, 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 16th, 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 16th, 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 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.
|
| « Last Edit: Sep 16th, 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 17th, 2002, 12:58pm » |
Quote Modify
|
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...
|
| « Last Edit: Sep 17th, 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 28th, 2003, 8:01pm » |
Quote Modify
|
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 8,6,5,3,2,2,2,1,1 .
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 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 30th, 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 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).
|
|
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 4th, 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 non-contiguous 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 5th, 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 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.
|
|
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 5th, 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 6th, 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 6th, 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 (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.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Willy's true colors
« Reply #12 on: Aug 7th, 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 303 = 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 8th, 2003, 4:07pm » |
Quote Modify
|
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:
[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 (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.
|
| « Last Edit: Aug 16th, 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 14th, 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 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
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 14th, 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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print