一個奧數問題

Solution 1:
用好systematic 的方法數哂所有可能性: (首先分幾多個連續的1, 然後再分有幾多個2)
(注: 11111212 reverse -> 21211111)

8 個1連續: 11111111 得一個
7個1連續: 11111112 or 21111111 兩個.
6個1連續: 11111122, 21111112, 22111111, 11111121, 12111111 有五個
5個1連續: 11111222 四個, (11111221, 11111212, 21111121, 11111211) + reverse 共12個
4個1連續: 11112222 五個, (11112221, 11112212, 11112122, 21111221. 21111212. 22111121) + reverse, 12111121, (11112211, 11112112, 11112121, 21111211)+reverse, (11112111) + reverse 共28個

total 1+2+5+12+28 = 48.

Solution 2:
用Set theory 的Formula:
數 1111xxxx, x1111xxx, xx1111xx, xxx1111x, xxxx1111 的數目, 再扣除重複計算的:
以上五個 case ABCDE 都有 2^4= 16 choices. (x = 1 or 2)
A跟B 重複: 即係頭5個要係1, 最後三個任擺: 2^3 = 8,
同樣(好易數的, 留意AE 永遠係得一個可能):
A跟C 重複: 4, AD: 2, AE: 1 BC: 8, BD=4, BE=2, CD=8, CE=4, DE=8
ABC: 4, ABD=2, ABE: 1, ACD: 2, ACE: 1, ADE: 1, BCD: 4, BCE:2, BDE:2, CDE: 4
ABCD: 2, ABCE: 1, ABDE: 1, ACDE: 1, BCDE: 2
ABCDE: 1

so final answer is : 16*5 - (8+4+2+1+8+4+2+8+4+8) + (4+2+1+2+1+1+4+2+2+4) - (2+1+1+1+2) + 1 = 80-49+23-7+1 = 48

11111112 7個1 有2個
11111122 6個1 有3個
.4
.5
.6
.7
1個1 有8個

2+3+4+5+6+7+8+9=44