正方体涂色问题

Posted by Codeboy on November 15, 2015

前些日子室友说了一道15年秋招的笔试题,题目如下:

用三种颜色给立方体的六个面着色,颜色可以使用一种或多种,旋转后可以相同的涂色记为一种涂色方式,问一共有多少种涂色方式?

当时一心想直接罗列出来,但是涂色的种类比较的多,而且立方体的旋转也有很多种,有按照面中心点连线,棱中心连线,顶点连线三种方式。人为的去列举很容易出现错误。下面讲一下使用Polya计数定理来进行计算,有关Polya定理的说明可以在网上查询或者从以下地址简单查看http://cs.tju.edu.cn/faculty/zhangkl/teaching/comb/lec12.pdf.

这里假设读者对Polya与Burnside引理都有了解,仅仅列举出对应的做题步骤与具体过程。

① 获取置换群
② 写出对应的多项式公式
③ 计算结果

获取/找出置换群

按照立方体的旋转方式,大概分为以下几种(记立方体顶点为1-6):

  • 不旋转

    (1,2,3,4,5,6) 1组

  • 沿面中心线旋转90°或者270°

    (1,2,3,4)(5) (6) 6组

  • 沿面中心线旋转180°

    (1,3)(2,4)(5)(6) 3组

  • 沿棱中心线旋转180°

    (1,2)(3,4)(5,6) 6组

  • 沿对角顶点连线旋转120°或者240°

    (1,2,3)(4,5,6) 8组

写出对应的多项式公式

sum = (w1^6 + 6 * w1^2 * W4^1 + 3 * w1^2 * w2^2 + 6 * w2^3 + 8 * w3^2) / 24

计算结果

将所有的w替换为3即可得出3中颜色的涂色种类,即

sum=(3^6+6*3^2*3+3*3^2*3^2+6*3^3+8*3^2)/24 = 57

如有任何知识产权、版权问题或理论错误,还请指正。

转载请注明原作者及以上信息。