趣题：棋盘着色 IBM Research Ponder This October 2013

显示全部楼层 · 2012-5-21 10:19:41

本帖最后由〇〇于 2013-10-28 10:31 编辑
IBM Research
Ponder This

October 2013
>

--------------------------------------------------------------------------------

Ponder This Challenge:

Color the squares of an 8x8 check-board in two colors (black and white) and calculate the percentage of black squares in every one of the 8 rows, 8 columns and 30 diagonals.
Our challenge this month is to find such coloring which gives the same percentage for every row; different one for every column and as many different numbers in the diagonals as possible.
Supply your answer as 8 lines of 8 B/W characters.
For example, the following is a solution for a 2x2 case of the problem:
BW
BW
The column percentage is 0%, 100%; all rows are 50% and the diagonals has 0%,50% and 100% (each appears twice).

千问 · 2012-5-21 10:19:41

用黑白给一个8*8棋盘的格子着色，并计算每行、每列和30个对角线中的每个线上的黑色百分比。
要求找到一种着色方法，使得每行百分比相同、每列百分比不同、并且对角线百分比不同个数尽量多。
输出格式：
8行，每行用BW表示黑白
例如2*2的答案是
BW
BW
列百分比是0%、100%，行百分比都是50%，对角线有0%、50%和100%（每个出现2次）
出处
http://domino.research.ibm.com/C ... es/October2013.html

千问 · 2012-5-21 10:19:41

穷举不行，有2^64种可能

千问 · 2012-5-21 10:19:41

从列百分比不同，8列分别0-8个黑

千问 · 2012-5-21 10:19:41

〇〇发表于 2013-10-27 17:48
从列百分比不同，8列分别0-8个黑
各行百分比都相同，可得各行黑格相同，总黑格数是8的倍数
要使每列各不相同，各列黑格分别是0-8，如果取0-7，总黑格数=7*8/2=28，如果取1-8，总黑格数=9*8/2=36，中间满足8倍数的只有32，所以各列黑格必须是0 1 2 3 5 6 7 8
此外，行与行交换、列与列交换不影响行列黑百分比，只影响对角线，
可以从任意一个开始穷举
BBBBWWWW
BBBBWWWW
BBBBWWWW
BBBBWWWW
BBBBWWWW
BWWWWBBB
BWWBWWBB
BWBBWWWB

千问 · 2012-5-21 10:19:41

答案已公布
11月题
Ponder This Challenge:

Three dimensional cube has 8 vertices; 12 edges; and 6 faces. We may call them 0-D; 1-D; and 2-D faces respectively.
Denote f(d,k) as the number of k-dimensional faces of an d-dimensional hyper cube; so f(3,1)=12.
Find three cubes (with different dimensions d1, d2,d3) such that the number of k1, k2, k3 dimension faces are the same.
I.e. f(d1,k1) = f(d2,k2) = f(d3,k3).
We are looking for non-trivial solutions, so k1 should be less then d1.
Bonus: find more than three.
http://domino.research.ibm.com/C ... s/November2013.html

千问 · 2012-5-21 10:19:41

本帖最后由〇〇于 2013-11-7 06:11 编辑
10月官方解答
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/October2013.html

The number of black squares in the columns are eight distinct numbers in the range between 0 and 8.
The total number of black squares on the board should be divisible by 8, so clearly the missing number is 4.
There are 21 different possible percentages that can be realized on the diagonals:
0,1/8,1/7,1/6,1/5,1/4,2/7,1/3,2/5,3/7,3/8,1/2,5/8,4/7,3/5,2/3,5/7,3/4,4/5,5/6,6/7,7/8.
Since there are only two 8-long diagonals, we cannot get the four possibilities (1/8, 3/8, 5/8 and 7/8), so the maximum is 19.
One can get it quite easily by playing a little with row and column permutations.
We chose to show Mark Pervovskiy's solution since it was the nicest looking one:
WWWWBBBB
WWWWBBBB
WWWWBBBB
WWWWBBBB
WWWWBBBB
WWBWBWBB
WBBWBWWB
BBBWBWWW
Thanks to Motty Porat for sending us ten wonderful solutions:
PP P PO O OON NNNDDD D E E E ERRRR
PPPP OOO ONNNN D DDDEEEE RRRR
PPPP O0O O NN NN DDDDEEE E RR RR
P PPPOO OO NN NN DDDDEE EE RRRR
PPPP OOO O NNN N D DD D EEEE RR R
PPPP OOO O N NNN D DD D EEEERR RR
PPPP OOO O NN NN D DD DEEE E RRR R
PPPPO OOO NNN ND D DDE E E E RRRR

TT TTHHH HIIII S SSS
TTTTHHHH III ISSSS
TTTT HH HH II IISSSS
TTTT HH HH I III SSSS
TTTTHHHH I III SSS S
TT TT HHHH I IIISSSS
TTT T HHHH I IIISS SS
T TTTH HHHIIIISSS S