發新話題
打印

台大資工甄選入學指定項目考試

題意即: 有多少個正整數 k,使不定方程  17u + 22v = k 不存在正整數解 (u, v) ?

解: 對於不定方程 17u + 22v = k 的所有整數解 (u, v),取其中最小的正整數 u (則 1 ≤ u ≤ 22),再考慮有幾個 v 取值,可以得到符合題意的 k。

當 u =22,v =0, -1, -2, ..., -16,共 [17*22 /22] = 17 個 ( [...] 為高斯符號)

而對每個 1 ≤ u ≤ 21,v 皆有 [17u /22] +1 個取值

故所求

= [17*22 /22] + [17*21 /22] + [17*20 /22]  +...+ [17*1 /22] +21

= [17*22 /22] + [17*11 /22] + 16*10 +21 (註)

= 206

註: 注意到 u =11 時,[...] 內為 8.5。利用對稱性,與 11 "等距" 的兩個 u 值,其 [...] 之和 = 16。


TOP

以下純屬個人直觀想法。

(1) 0  (因為每個置入袋中的球,都會在下課前被取出)

(2) 1  (因為第一次置入袋中的 10 顆球,有 9 顆會留在袋中直至下課)

請問有答案嗎?

TOP

發新話題