Uwants TV消閒生活手機討論遊戲地帶影視娛樂校園生活數碼科技寵物樂園學術文化體育世界購物廣場時事投資貼圖影片上班一族美容纖體戀愛婚姻汽車討論成人資訊博彩娛樂資源交流站務管理
發帖
註冊 登入/註冊 微博



追帖 打印

[數學,M1&M2] DSE-related Discrete Mathematics Question Review



DSE-related Discrete Mathematics Question Review

[隱藏]
1. Show that 151 is a prime number

Answer:

Consider a non-prime number x^2 - y^2 = (x+y)(x-y)
for all integers x, y including 0

This implies that x-y must be non-prime
Put y = 0, then min(x) = 2

This also implies that x^2 is the greatest non-prime formula.

Now we need to seek x^2 - y^2 <= sqrt(151)

So we plug y = 0 and x = 2,3,5,7, or 11,
and we see the equality does not hold.

So 151 must be prime.

[ 本帖最後由 doraemonserv 於 2018-6-8 06:01 AM 編輯 ]
A Good Analyzer Must Be A Good Collector.

回覆 引用 TOP

For the above solution, the methodology has an alternative proof:






A Good Analyzer Must Be A Good Collector.

回覆 引用 TOP

2. Define floor(sqrt(x)) such that m <= floor(sqrt(x)) < m+1 for any integer m.

Given m >0, prove that floor(sqrt(floor(x))) = floor (sqrt(x))

Answer:

m^2 < floor (x) < m^2 + 1 < (m + 1)^2
So m <= sqrt(x) = m+1
The equality is then hold.




A Good Analyzer Must Be A Good Collector.

回覆 引用 TOP

3. What's wrong with the proof below?

引用:
Theorem: a^n = 1 for all non-negative integer n,
where a is non-zero real number.

Proof by Mathematical Induction:

For n = 0, a^0 = 1 is true
Assume a^k is true,
a^(k+1) = (a^k)(a^k) / (a^(k-1)) = 1 x 1 / 1 = 1


Answer:
a^(k+1) = (a^k ) (a^1)

Put a = 2 then we have 2^1 = 1 which is contradiction.

[ 本帖最後由 doraemonserv 於 2018-6-8 05:51 AM 編輯 ]






A Good Analyzer Must Be A Good Collector.

回覆 引用 TOP

[隱藏]
4. What's wrong with the following proof?

引用:
Let P(n) be the proposition that all the horses in a set of n horses are the same color. Clearly P(1) is true. Now assume that P(n) is true, so that all the horses in any set of n horses are the same color.

Consider any n+1 horses; number these as horses 1, 2, 3,..., n, n_1. Now the first n of these horses all must have the same color, and the last n of these must also have the same color. Since the set of the first n horses and the set of the last n horse overlap, all n+1 must be the same color. This shows that P(n+1) is true and finishes the proof by induction.


Answer:
P(2) is false. The first half (1st) and the last half (2nd) have no overlapping.
We cannot use P(2) to compile P(3), P(4),... and P(n) then.
A Good Analyzer Must Be A Good Collector.

回覆 引用 TOP

5. Prove that 2^n > n^3 for n >=10

Answer: Use MI

Denote P(n) as the proposition.
Clearly (10) = 1024 > 1000 is true

For n = k+1, we have:

2^(k+1) = 2 x 2^k => (1 + 1/10)^3 x 2^k
=> (1 + 1/k)^3 x 2^k
=> (1 + 1/k)^3 x k^3
= (k+1)^3

This is a frequent question type in HKALE Pure Math. Even DSE M2 may not assess inequality as MI, you will still need to face it in freshman level courses.






A Good Analyzer Must Be A Good Collector.

回覆 引用 TOP

6. (a) How many factors are there for 1000?

Answer: 1000 = 2^3 x 5^3
By operating the indexes for mapping 1000 = mn,
where m, n are integers equal or greater than 2,
We have 8 numbers of mn.

6.(b) How many factors are there for 248396544?

Answer: 248396544 = 2^8 x 3^6 x 11^3
So we have (8+1)(6+1)(3+1) = 252 factors.






A Good Analyzer Must Be A Good Collector.

回覆 引用 TOP

7. How many zeros are there for the value of 400! ?

Answer
Consider 400! = 2^a x 3^b x 5^c x 7^d .....
where a, b, c, d are all positive integers

The number of zeros = min{a,c}

Since count of 2^a > count of 5^c
We need to observe the count of some 5^c

For 5^1, we have floor(400/5) = 80
For 5^2, we have floor(400/25) = 16
For 5^3, we have floor(400/125) = 3
For 5^4, we have floor(400/625) = 0

So the number of zeros, i.e. 2^a x 5^c is 80+16+3 = 99




A Good Analyzer Must Be A Good Collector.

回覆 引用 TOP

8. Denote gcd (4, 8) = 4 and gcd (2,3) = 1.
From the information above,
prove that sqrt(2) is an irrational number.

Answer:
Denote sqrt(2) = m/n where gcd(m,n) = 1
Then we have:

2 = m^2/n^2
m^2 = 2n^2

We have 2|m^2 and thus 2|m where m=2k for k being positive integer

Now

2n^2 = m^2 = (2k)^2 = 4k^2
n^2 = 2k^2

We have 2|n^2 and thus 2|n

So we we have gcd(m,n) >=2 which is a contradiction.

Now try to prove sqrt(prime number) is irrational!
A Good Analyzer Must Be A Good Collector.

回覆 引用 TOP

[隱藏]
今晚會出 Combinatorics, 敬請期待
A Good Analyzer Must Be A Good Collector.

回覆 引用 TOP

9. How many integers from 1 to 1000 do not have any repeated digits?

Answer:

For X: 9
For XX: 9 x 9
For XXX: 9 x 9 x 8

So totally 9 + 81 + 648 = 738
A Good Analyzer Must Be A Good Collector.

回覆 引用 TOP

10. How many integers in { 100 ~ 999 } have no 2 digits the same?

Answer:
Consider XXX: 5 x 9 x 8 = 360
Consider 0XX: 4 x 8 = 32

So we have 360 - 32 = 328
A Good Analyzer Must Be A Good Collector.

回覆 引用 TOP



伸延閱讀
 提示:支持鍵盤翻頁 ←左 右→ 發新話題發佈投票
請先登入
小貼士:
依家可以用“@”tag會員啦!