※ 引述《ilovecurl (ilovecurl)》之銘言：
: The set A={1,2,3,...,2044,2045} contains 2045 elements. A subset S of A is
: called triple-free if no element of S equals three times another element
: of S. For example, {1,2,4,5,10,2043} is triple-free, but
: {1,2,4,5,10,681,2043} is not triple-free. The triple-free subsets of A that
: contain the largest number of elements contain exactly 1535 elements.
: There are n triple-free subsets of A that contain exactly 1535 elements.
: The integer n can be written in the form p^a*q^b, where p and q are distinct
: prime numbers and a and b are positive integers. If N=p^2+q^2+a^2+b^2,
: then the last three digits of N are
: (A)202 (B)102 (C)302 (D)402 (E)502
: 學生問的題目,剩這題沒想出來,只有想到1535是怎麼算出來的,但有多少個這樣的集合
: 暫時沒有頭緒,上來請教板友看看有沒有想法,謝謝!
n 1 3 9 27 81 243 729
[2045/n] 2045 681 227 75 25 8 2
每個元素組的第一個數 a 為非3的倍數，包含所有長的像 a*3^k 的數
7元素組：2組
1, 3, 9, 27, 81, 243, 729
2, 6, 18, 54, 162, 486, 1458
6元素組：(2 + 6*(2/3)) - 2 = 4組
4, 12, 36, 108, 324, 972
5 開頭
7 開頭
8 開頭
5元素組：(1 + 24*(2/3)) - (2 + 6*(2/3)) = 11組
4元素組：75*(2/3) - (1 + 24*(2/3)) = 33組
3元素組：(2 + 225*(2/3)) - 75*(2/3) = 102組
2元素組：681*(2/3) - (2 + 225*(2/3)) = 302組
1元素組：(2 + 2043*(2/3)) - 681*(2/3) = 910組
驗算 910 + 2*302 + 3*102 + 4*33 + 5*11 + 6*4 + 7*2 = 2045
以及 910 + 302 + 2*102 + 2*33 + 3*11 + 3*4 + 4*2 = 1535
組合數嘛，1, 3, 5, 7元素組都是固定的
2元素組各選1個：2^302 種選法
4元素組各選不相鄰2個：3^33 種選法
6元素組各選不相鄰3個：4^4 = 2^8 種選法
因此選法一共有 2^310 * 3^33 種
2^2 + 310^2 + 3^2 + 33^2 = 97202
所以答案是(A)吧 ow o
--
嗯嗯ow o
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.129.66.217
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1458316379.A.668.html