Painting a cube
Jonathan G. Dushoff
three colors?
How many can you make if cubes which are mirror images of each other are
considered to be the same?
What about if you have n colors, instead of three?
Jonathan Dushoff
Michael
Nick Wedd
<jdus...@yuma.Princeton.EDU> writes
>How many distinguishable cubes can you make by painting each face one of
>three colors?
57
>How many can you make if cubes which are mirror images of each other are
>considered to be the same?
56
>What about if you have n colors, instead of three?
27*Cn,2 + 30*Cn,3 + 80*Cn,4 + 60*Cn,5 + 30*Cn,6
or, if mirror images are considered the same,
27*Cn,2 + 29*Cn,3 + 52*Cn,4 + 30*Cn,5 + 15*Cn,6
Nick
--
Nick Wedd ni...@maproom.co.uk
Michael
hoeflin power test. a definite no-no.
Jonathan G. Dushoff
: i should have warned that thie first one was a problem appearing
: on the hoeflin power test.
Yes. I also received this information by email from Andreas Gunnarsson.
I am not personally impressed with the idea of the test as an
intelligence test, or the idea of sitting down to do the whole thing and
get a score, but it definitely has some nice puzzles. It is at
http://www.eskimo.com/~miyaguch/power.html. Since I am pointing r.p.
to it, I suppose I have a responsibility to request that people respect
the suggested limitations on discussion of these problems.
: a definite no-no.
This presumably implies that I cribbed the puzzle from Hoeflin, which
would be insulting, silly (given the simplicity of Hoeflin's puzzle, and
the fact that mine has the non-obvious extension to mirror images), and
- for the record - false.
Nick Wedd wrote:
: [Spoilers without spoiler space]
How come?
Jonathan Dushoff
Nick Wedd
<jdus...@fez.Princeton.EDU> writes
>Nick Wedd wrote:
>
>: [Spoilers without spoiler space]
>
>How come?
Are you saying that my answers are wrong (which is quite possible), or
asking me how I obtained them?
uncle monty
: In article <9s1bpf$rgp$1...@cnn.Princeton.EDU>, Jonathan G. Dushoff
: <jdus...@fez.Princeton.EDU> writes
:>Nick Wedd wrote:
:>
:>: [Spoilers without spoiler space]
:>
:>How come?
: Are you saying that my answers are wrong (which is quite possible), or
: asking me how I obtained them?
I would guess he's asking you why you didn't leave any spoiler space,
since that's the only feature of your post he brought attention to.
--Monty
Jonathan G. Dushoff
>Nick Wedd wrote:
>
>: [Spoilers without spoiler space]
>
>How come?
Nick Wedd <ni...@maproom.co.uk> wrote:
: Are you saying that my answers are wrong (which is quite possible),
: or asking me how I obtained them?
I thought I was fairly clear: I am asking how come you posted spoilers
without spoiler space. Although I am also curious why there was no
explanation: were the problems that boring?
Jonathan Dushoff
Nick Wedd
>: Are you saying that my answers are wrong (which is quite possible),
>: or asking me how I obtained them?
>
>I thought I was fairly clear: I am asking how come you posted spoilers
>without spoiler space. Although I am also curious why there was no
>explanation: were the problems that boring?
I should have used spoiler space. I usually use spoiler space, and on
this occasion I forgot. I apologise for this.
I thought the problems were good ones, and will post the reasoning
behind my replies, if there is any more evidence of demand for it.
uncle monty
: I thought the problems were good ones, and will post the reasoning
: behind my replies, if there is any more evidence of demand for it.
Yes please, I've been trying to whittle my solutions down to 56 but I
can't catch all the symmetries.
Michael
perfectly reasonable
to imagine that someone could dream hoeflin's puzzles up. and I DO
believe you.
'Compromise' has been a term applied to Hoeflin's 4 so-called 'Power
Tests' for a long time.
They were originally designed as take home tests with no tme limit and no
help from any source
other than books - except for the Power which allows only the mighty
pen. It was hoped that they
would measure high IQ's unmeasurable by other traditional tests. The
answers began leaking however,
and by 1995, the Mega was pretty much trashed. The main reason for the
spread of these answers is news groups where one can do vast searches and
even turn up the answers to specific problems. Usual
people wanting a solution could pose a 'tough' problem to a pack of
bloodthirsty puzzlists and receive the credit, while the answer remained
in the archives waiting for other vultures. the problem was eventually
recognized once the tests were online at Darryl's site there. so people
could call these cheaters wanting a solution to: how many pieces can you
cut a cube of butter into using 5 planar strokes? so the cheaters got
better and started doing 3 things: 1) trivially modifying the puzzle
while superficially making it appear different 2) making it harder. for
example: how many pieces can you cut a cube of butter into with N planar
knife strokes. now post it at sci.math and it looks like a tricky
university problem that has stumped some poor kid. 3) camoflage it within
a bunch of other problems.
I guess my alarm bell went off for number 3. sorry.
Nick Wedd
<uncle...@babyfishmouth.org> writes
Ok, I'll try.
Spoiler follows ...
Notation.
3-2-1 means three faces of one colour, two of another, one of another.
'op' means two opposite faces.
'ad' means two adjacent faces.
6-0-0 3 colours to choose, so 3 ways.
5-1-0 3*2 colours to choose, so 6 ways
4-2-0 3*2 colours to choose, the 2 may be op or ad, so 12 ways
3-3-0 3*2/2 colours to choose, the 3 may be in a clump or not, 6 ways
4-1-1 3 colours to choose, the 1-1 may be op or ad, so 6 ways
3-2-1 3*2 colours to choose
if the 2 are op, 6 ways
if the 2 are ad, 2 ways to put the 1, so 12 ways
total 18
2-2-2 op-op-op is 1 way
op-ad-ad, 3 ways to choose the op colour, is 3 ways
ad-ad-ad, 2 ways related by mirror symmetry, is 1 or 2 ways
total 5 or 6
So overall total is 56 or 57
Dan Hoey
[a very nice case analysis of painting a cube with three colors].
But earlier, you wrote:
> >What about if you have n colors, instead of three?
>
> 27*Cn,2 + 30*Cn,3 + 80*Cn,4 + 60*Cn,5 + 30*Cn,6
> or, if mirror images are considered the same,
> 27*Cn,2 + 29*Cn,3 + 52*Cn,4 + 30*Cn,5 + 15*Cn,6
That doesn't even agree with the three-color case, though
maybe you meant 9Cn,2. But that's still wrong, and there
are 3 other errors.
I'll give you my analysis (with no gratutitous whitespace*).
The answer as a polynomial is almost immediate from the
Cauchy-Frobenius aka Polya-(not)Burnside theorem. For
each of the 24 rotations of the cube (or the 48 rotations
and reflections) each cycle of faces must be monochrome,
so it contributes n^c/|G| where n is the number of colors,
c is the number of cycles, and |G| is the size of the group (24 or 48).
So we add up
representative number of contribution contribution
rotation/ equivalents counting including
reflection (conjugates) rotations reflections
(B)(F)(T)(D)(L)(R) 1 n^6/24 n^6/48
(B,F)(T,D)(L)(R) 3 3 n^4/24 3 n^4/48
(B,T,L)(F,D,R) 8 8 n^2/24 8 n^2/48
(B,F)(T,L)(D,R) 6 6 n^3/24 6 n^3/48
(B,T,F,D)(L)(R) 6 6 n^3/24 6 n^3/48
(B,F)(T,D)(L,R) 1 n^3/48
(B,F)(T)(D)(L)(R) 3 3 n^5/48
(B,T,L,F,D,R) 8 8 n /48
(B,T)(F,D)(L)(R) 6 6 n^4/48
(B,T,F,D)(L)(R) 6 6 n^6/48
so there are (n^6 + 3n^4 + 12n^3 + 8n^2)/24 paintings up to
rotation, or (n^6 + 3n^5 + 9n^4 + 13n^3 + 14n^2 + 8n)/48 up
to rotations and reflections.
Converting to binomial coefficents may be done by dividing
out by their polynomial representations
Cn,1 = n
Cn,2 = (n^2 - n)/2
Cn,3 = (n^3 - 3n^2 + 2n)/6
Cn,4 = (n^4 - 6n^3 + 11n^2 - 6n)/24
Cn,5 = (n^5 - 10n^4 + 35n^3 - 50n^2 + 24n)/120
Cn,6 = (n^6 - 15n^5 + 85n^4 - 225n^3 + 274n^2 - 120n)/720
to get
30Cn,6 + 75Cn,5 + 68Cn,4 + 30Cn,3 + 8Cn,2 + Cn,1
counting only rotations, or
15Cn,6 + 45Cn,5 + 52Cn,4 + 29Cn,3 + 8Cn,2 + Cn,1
including reflection.
Alternatively, we can generalize your case analysis:
Color counts subcase arrangements (rot or rot+ref)
6 Cn,1
5 1 2Cn,2
4 2 ad 2Cn,2
4 2 op 2Cn,2
3 3 clump Cn,2
3 3 strip Cn,2
4 1 1 ad 3Cn,3
4 1 1 op 3Cn,3
3 2 1 clump 6Cn,3
3 2 1 1 midstrip 6Cn,3
3 2 1 1 end strip 6Cn,3
2 2 2 op op op Cn,3
2 2 2 op ad ad 3Cn,3
2 2 2 ad ad ad 2Cn,3 or Cn,3
3 1 1 1 clump 8Cn,4 or 4Cn,4
3 1 1 1 strip 12Cn,4
2 2 1 1 op op op 6Cn,4
2 2 1 1 op ad ad 12Cn,4
2 2 1 1 ad ad op 6Cn,4
2 2 1 1 ad ad ad 24Cn,4 or 12Cn,4
2 1 1 1 1 op 15Cn,5
2 1 1 1 1 ad 60Cn,5 or 30Cn,5
1 1 1 1 1 1 30Cn,6 or 15Cn,6
which yields the same result.
Dan Hoey Posted and -emailed
hao...@aol.com * Why? Because I think it's silly.