<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>

<b>Logic, phương pháp chứng minh, đại số Bool</b>

<b>1.</b> Tìm giá trị của các biến mệnh đề x, y, z, u, v để biểu thức sau nhận giá trị sai
(y  (x  z))  (x  u)  (y  v)

<b>Giải</b>

(y  (x  z))  (x  u)  (y  v) = F  y  (x  z) = F & x  u = F & y  v = F
 y = T & x  z = F & (x = F  u = F) & (y = F  v = F)

 y = T & x = T & z = F & (x = F  u = F) & (y = F  v = F)
 y = T & x = T & z = F & u = T & v = F

<b>2.</b> Sử dụng biến đổi đồng nhất chứng minh ¬xy  ¬yz  ¬zx tương đương ¬yx  ¬xz  ¬zy
Giải

xyyzzx

 xy(zz)yz(xx)zx(yy)

 xyz xyz yzx yz xzxyzxy
 yx(zz)  xz(yy)  zy(xx)

 yx  xz  zy

<b>3.</b> Bằng phương pháp Karnaugh, Consensus, Quine-Mc Cluskey, tìm cơng thức tối tiểu dạng
đa thức của hàm

<i>f</i>=xyz<i>∨x</i>yz<i>∨x y z∨xyz∨x y z</i>

f = 1001 1010 1101 1011

<b>4.</b> Bằng phương pháp quy nạp, chứng minh rằng với mọi n  8 phương trình 3x + 5y = n có
nghiệm ngun khơng âm

Giải

Với n = 8 phương trình có dạng 3x + 5y = 8 và có nghiệm ngun khơng âm (x=1, y=1)
Giả sử với n=k ≥ 8 phương trình 3x + 5y = k có nghiệm ngun khơng âm (x0, y0)

3x0 + 5y0 = k (*)

Ta phải chứng minh với n=k+1, phương trình 3x + 5y = k+1 (**) cũng có nghiệm ngun khơng
âm

Thật vậy, từ (*) suy ra 3x0 + 5y0 + 1 = k+1

Nếu y0 = 0  x0 ≥ 3 khi đó 3x0 + 5y0 + 1 = k+1  3(x0 – 3) + 5.2 = k+1: phương trình (**) có
nghiệm ngun khơng âm (x0 – 3, 2)

Nếu y0 ≥ 1, 3x0 + 5y0 = k+1  3(x0 + 2) + 5(y0 – 1) = k+1: phương trình (**) có nghiệm ngun
khơng âm (x0 + 2, y0 – 1)

<b>5.</b> Bằng phương pháp quy nạp, chứng minh rằng với mọi n  7 phương trình 2x + 5y = n có
nghiệm ngun khơng âm

Giải

Với n = 7 phương trình có dạng 2x + 5y = 7 và có nghiệm ngun khơng âm (x=1, y=1)
Giả sử với n=k ≥ 7 phương trình 2x + 5y = k có nghiệm ngun khơng âm (x0, y0)

2x0 + 5y0 = k (*)

Ta phải chứng minh với n=k+1, phương trình 2x + 5y = k+1 (**) cũng có nghiệm nguyên không
âm

Thật vậy, từ (*) suy ra 2x0 + 5y0 + 1 = k+1

Nếu y0 = 0  x0 ≥ 4 khi đó 2x0 + 5y0 + 1 = k+1  2(x0 – 2) + 5.1 = k+1: phương trình (**) có
nghiệm ngun khơng âm (x0 – 2, 1)

Nếu y0 ≥ 1, 2x0 + 5y0 +1 = k+1  2(x0 + 3) + 5(y0 – 1) = k+1: phương trình (**) có nghiệm
ngun khơng âm (x0 + 3, y0 – 1)

</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>

a. Có bao nhiêu cách sắp xếp

b. Có bao nhiêu cách sắp xếp với yêu cầu các cậu bé ngồi kề nhau và các cơ bé ngồi
kề nhau

c. Có bao nhiêu cách với yêu cầu các cậu bé và cô bé ngồi đan xen nhau

d. Cùng các câu hỏi với 3 cậu bé và 3 cô bé

<b>7.</b> Cũng với các câu hỏi trên nhưng sắp xếp các cô bé và cậu bé thành vòng tròn
<b>8.</b> Một từ là một chuỗi các chữ cái trong bảng 26 chữ cái (tiếng anh)

a. Có bao nhiêu từ độ dài  6

b. Có bao nhiêu từ độ dài 6 bắt đầu bởi một nguyên âm/phụ âm

c. Có bao nhiêu từ độ dài 6 bắt đầu bởi một phụ âm và kết thúc bởi một nguyên âm

<b>9.</b> Sắp xếp n quả bóng vào m hộp (n  m)

a. Giả sử các quả bóng giống nhau. Có bao nhiêu cách sắp xếp

b. Giả sử các quả bóng giống nhau. Có bao nhiêu cách sắp xếp với yêu cầu mỗi hộp
chứa ít nhất một quả bóng

c. Giả sử các quả bóng giống nhau. Có bao nhiêu cách sắp xếp với yêu cầu hộp thứ i
chứa mi quả bóng (mi  1 và mi = n)

d. Giả sử mỗi quả bóng mang một màu. Có bao nhiêu cách sắp xếp với yêu cầu mỗi
hộp chứa ít nhất một quả bóng

<b>10.</b> Phân hoạch tập hợp: chia một tập hợp n phần tử thành các tập con rời nhau. Gọi số cách
phân hoạch là B(n)

a. Tìm một cơng thức tính B(n)

b. Chứng minh cơng thức <i>B</i>(<i>n</i>+1)=

∑

<i>i=</i>0

<i>n</i>

(

<i>ni</i>

)

<i>B</i>(<i>n− i</i>) trong đó B(0) được định
nghĩa là 1

<b>11.</b> Có bao nhiêu đồ thị đơn n đỉnh

<b>12.</b> Sắp xếp các số 1, 2, 3, ..., 11, 12 ngẫu nhiên trên một đường trịn, chứng minh có thể chọn

được 3 số kề nhau tổng của chúng ≥ 20

Giải

Số bộ ba số kề nhau = 12

Giả sử tổng của mỗi bộ ba đều < 20  mỗi tổng ≤ 19  Tổng của tất cả các bộ ba ≤ 228
Tổng của tất cả các bộ ba = 3(1 + 2 + ... + 12) = 3.12.13/2 = 234 mâu thuẫn

<b>13.</b> Các số 1, 2, ..., n được sắp xếp ngẫu nhiên trên một đường trịn, chứng minh rằng có thể
chọn được hai bộ ba số, tổng của các số trong hai bộ ba này bằng nhau

<b>14.</b> Có bao nhiêu cách chia (chia hết) 10 phần quà (giống nhau) cho 6 đứa trẻ sao cho mỗi đứa
trẻ được chia ít nhất một phần quà

Giải

Có n phần quà chia hết cho m đứa trẻ mỗi đứa được ít nhất một phần quà (m ≤ n)

Đứa trẻ thứ nhất được chia k phần quà (1 ≤ k ≤ n - m+1), n – k phần quà còn lại được chia cho
m – 1 đứa trẻ còn lại. Gọi số cách chia n phần quà cho m đứa trẻ mỗi đứa được ít nhất một phần
quà là D(n, m), ta có cơng thức:

D(n, m) = D(n-1, m-1) + D(n-2, m-1) + … + D(m-1, m-1) = D(n-1, m-1) + D(n-1, m)
D(k, k) = 1; D(k, 1) = 1

Ta có bảng tính D(n, m):
m

</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>

1 1

2 1 1

3 1 2 1

4 1 3 3 1

5 1 4 6 4 1

6 1 5 10 10 5 1

7 1 6 15 20 15 6

8 1 7 21 35 35 21

9 1 8 28 56 70 56

10 1 9 36 84 126 <b>126</b>

D(n, m) =

(

<i>n −_m</i>1

)

<b>15.</b> Rút một số trong tập các số có <b>ba chữ số</b> được tạo thành từ các chữ số 0, 1, 2, 3, 4, 5. Tính
xác suất để rút được số chia hết cho 3

<b>16.</b> Trong mặt phẳng, n đưởng thẳng đôi một cắt nhau, khơng có ba đường thẳng nào đồng quy
chia mặt phẳng thành bao nhiêu miền?

Giải

Một đường thẳng chia mặt phẳng thành 2 miền: D(1) = 1 + 1 = 1 + 1.(1+1)/2

Hai đường thẳng chia mặt phẳng thành 4 miền: D(2) = 1 + 3 = 1 + 2(2+3)/2
…

N đường thẳng chia mặt phẳng thành D(n) = 1 + n(n+1)/2
CM: bằng quy nạp

<b>17.</b> Có bao nhiêu chuỗi n bít chứa k bít 0 và (n-k) bít 1
Giải

Số chuỗi n bít chứa k bit 0 (n-k) bit 1 = số cách chọn k vị trí trong n vị trí cho bit 0 =

(

<i>n_k</i>

)

<b>18.</b> Có bao nhiêu chuỗi bít độ dài n (n > 4) có hai bít đầu khác 10 đồng thời hai bit cuối khác
01

Giải

A = tập các chuỗi bít độ dài n

B = tập các chuỗi bít độ dài n có hai bit đầu là 10
C = tập các chuỗi bit độ dài n có hai bít cuối là 01

Tập các chuỗi bit độ dài n có hai bit đầu khác 10 và hai bit cuối khác 01 = A - BC
 Số các chuỗi bit độ dài n có hai bit đầu khác 10 và hai bit cuối khác 01 = |A| - |BC|
= |A| - (|B| + |C| - |BC|) = |A| + |BC| - |B| - |C| = 2n-4₍₂4_{+ 1 – 2}2_{– 2}2₎

= 9.2n-4
|A| = 2n
|B| = |C| = 2n-2
|BC| = 2n-4

<b>19.</b> Năm điểm nằm trong hình vng đơn vị (hình vng có cạnh độ dài 1). Chứng minh tồn

tại cặp điểm khoảng cách giữa chúng < 1

√

2
Giải

</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4>

cách giữa hai đỉnh này < đường chéo của hình vng con = 1

√

2

<b>20.</b> Năm điểm nằm trong tam giác đều cạnh 2. Chứng minh tồn tại hai điểm khoảng cách giữa
chúng < 1

Chia tam giác thành 4 tam giác đều con cạnh 1

5 điểm nằm trong tam giác phải có 2 điểm nằm trong cùng một tam giác con  khoảng cách giữa
hai điểm này < 1

<b>21.</b> Bảy điểm nằm trong hình lục giác đều có độ dài cạnh bằng 1. Chứng minh rằng tồn tại cặp
điểm, khoảng cách giữa chúng < 1

Giải

Chia lục giác đều thành 6 tam giác đều cạnh 1

Bảy điểm nằm trong lục giác, phải có 2 điểm nằm trong cùng một tam giác: khoảng cách giữa
hai điểm này < 1

<b>22.</b> Cho đồ thị đầy đủ 20 đỉnh, các cạnh của nó được tơ bởi ba màu xanh, đỏ và vàng. Chứng
minh rằng tồn tại ba đỉnh của đồ thị, các cạnh nối chúng có cùng màu

Giải

Có 19 cạnh xuất phát ra từ một đỉnh (A) nhận 1 trong 3 màu  phải có 7 cạnh cùng màu (giả sử
đỏ) gọi các đỉnh đầu mút 7 cạnh cùng màu này là B, C, D, E, F, G, H, nếu trong các cạnh nối các
đỉnh B, C, D, E, F, G, H có cạnh đỏ ta tìm được tam giác cạnh cùng màu (đỏ), nếu không, các
cạnh nối B với các đỉnh tương C, D, E, F, G, H chỉ mang hai màu xanh và vàng do vậy phải có 3
cạnh cùng màu (giả sử xanh) và giả sử các đầu mút tương ứng là C, D, E. Nếu các cạnh nối C, D,
E có cạnh màu xanh ta tìm được tam giác có các cạnh cùng màu (xanh), nếu khơng C, D, E là
tam giác có các cạnh cùng màu (vàng)

<b>23.</b> Chứng minh trong một đồ thị (đơn, không định hướng) hữu hạn với số đỉnh  2 có hai
đỉnh có cùng bậc

Giải

Nếu có 2 đỉnh bậc 0, ta được điều phải chứng minh, nếu không, ta xét đồ thị con G’ nhận được
từ G bỏ đi đỉnh bậc 0

Đồ thị có n đỉnh, di = bậc của đỉnh i: 1 ≤ di ≤ n – 1, i = 1, 2, …, n. do có n bậc, nhận n – 1 giá trị
nên phải có hai bậc cùng giá trị.

</div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>

Giải

i=1, 2, ..., 100: ai = 7pi + ri , 0  ri  6

100 số dư nhận 7 giá trị  tồn tại 15 số dư cùng nhận một giá trị, 15 số có số dư đó là các số
được chọn

<b>Arithmetics</b>

<b>25.</b> CM nếu n là hợp số thì 2n_{– 1 cũng là hợp số}

Giải

n=n1n2 (n1, n2 ≥ 2), 2n_{– 1 = 2}n1n2_{– 1 = (2}n1_{– 1)(2}n1(n2-1) _{+ … + 1)}

<b>26.</b> Số hoàn hảo là số mà tổng các ước số thực sự của nó bằng chính nó. CM nếu p là ngun
tố thì 2p(2p – 1) là số hồn hảo

<b>27.</b> Tìm tất cả các số nguyên tố p sao cho p-2 và p+2 cũng là nguyên tố
Giải

p, p – 2 là nguyên tố  p – 2 ≥ 3 đặt p – 2 = 3 + 2k  p = 3 +2(k+1), p + 2 = 3 + 2(k + 2)

nếu k > 0 trong 3 số nguyên dương k, k+1, k+2 có số chia hết cho 3  một trong ba số p –

2, p, p + 2 chia hết cho 3 vậy k=0, ta được p=5 (p – 2 = 3, p + 2 = 7)

<b>28.</b> CM nếu n là số tự nhiên thì

√

<i>n</i> hoặc là số ngun hoặc là số vơ tỷ

<b>29.</b> Tìm tất cả các số nguyên dương n sao cho n2_{+ 2n – 3 là số nguyên tố}

Giải

n2_{+ 2n – 3 = (n – 1)(n + 3)}

Nếu n – 1 > 1, n2_{+ 2n – 3 là hợp số}

 n – 1 = 1  n = 2

Với n = 2, n2_{+ 2n – 3 = 5}

<b>30.</b> CM nếu p, q là các số ngun tố phân biệt thì logp q là số vơ tỷ
<b>31.</b> tìm tất cả các nghiệm nguyên dương của phương trình xy = z2

Giải

Đặt d = (x, z)  x=dx’, z=dz’, (x’, z’) = 1 phương trình trở thành x’y = dz’2 , vì (x’, z’) = 1 

(x’, z’2_{) = 1 do vậy x’\d}__{d = tx’}__x=tx’2_{, z=tx’z’ và y = tz’}2_{, (x’, z’) =1}

Ngược lại với x=tx’2_{, z=tx’z’ và y = tz’}2_{, (x’, z’) =1 x, y, z là nghiệm của phương trình}

Vậy nghiệm của phương trình là: x=tx’2_{, y= tz’}2_{, z=tx’z’ với (x’, z’) = 1}

<b>32.</b> Chứng minh rằng dư của phép chia một số nguyên tố cho 30 hoặc là 1 hoặc là một số
nguyên tố

Giải

Xét p = 30q + r (1≤ r ≤ 29), r không chia hết cho 2, 3, 5 vậy r chỉ có thể nhận một trong các giá
trị: 1, 7, 11, 13, 17, 19, 23, 29

<b>33.</b> Chứng minh phương trình 4x3_{+ 2y}3_{= z}3_{khơng có nghiệm ngun dương}

Giải

Giả sử phương trình có nghiệm ngun dương, gọi (x0, y0, z0) là nghiệm nguyên dương với x0

nhỏ nhất: 4x03 + 2y03 = z03 (*)

Ta có 2\ z03, 2 là nguyên tố  2\z0: z0 = 2z’ thế vào (*) ta được: 2x03 + y03 = 4z’3 (**)  2\y03 , 2

nguyên tố  2\y0 : y0 = 2y’ thế vào (**) ta được: x03 + 4y’3 = 2z’3 (***)  2\x03 , 2 nguyên tố 

2\x0 : x0 = 2x’ (x’ nhỏ hơn x0) thế vào (***) ta được 4x’3 + 2y’3 = z’3 như vậy (x’, y’, z’) là

nghiệm của phương trình với x’ < x0 (mâu thuẫn với tính nhỏ nhất của x0)
<b>34.</b> Tìm tất cả các nghiệm ngun khơng âm của phương trình: x + y + z = xyz

Giải

</div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6>

Nếu x ≥ 1, đặt x = 1 + x’, y = 1 + y’, z = 1 + z’ (0 ≤ x’ ≤ y’ ≤ z’) thế vào phương trình ta được:
3 + x’ + y’ + z’ = 1 + x’ + y’ + z’ + x’y’ + y’z’ + z’x’ + x’y’z’  2 = x’y’ + y’z’ + z’x’ + x’y’z’

Nếu x’ ≥ 1 vế phải ≥ 4 vậy thì x’ = 0 khi đó phương trình là 2 = y’z’  y’ = 1, z’ = 2

Ta tìm được nghiệm x=1, y=2, z=3

Thay đổi vai trị của x, y, z ta tìm được tất cả các nghiệm của phương trình:
(0, 0, 0), (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)

<b>35.</b> Tìm tất cả các nghiệm nguyên khơng âm của phương trình: x + y + z + 9 = xyz
Giải

Vai trò của x, y, z như nhau trong phương trình, ta giả sử x  y  z > 0  x  y  z 

1. Đặt x = 1 + x1, y = 1 + y1, z = 1 + z1 (x1 y1 z1 0)

ta được : 11 = x1y1 + y1z1 + z1x1 + x1y1z1

° z1 = 0 : x1y1 = 11  x1 = 11, y1 = 1 (x = 12, y = 2, z = 1)

° z1 1 :

z1 > 1  vế phải > 11  z1 = 1, phương trình trở thành : 11 = 2x1y1 + x1 + y1 ; nếu

y1 > 1 :vế phải > 11  y1 = 1  10 = 3x1 (không có nghiệm ngun)

Vậy các nghiệm của phương trình là : (1, 2, 12), (1, 12, 2), (2, 1, 12), (2, 12, 1), (12, 1, 2),
(12, 2, 1)

<b>36.</b> Chứng minh 20122013_{+ 2015}2014_{chia hết cho 7}

Giải
2013 = 3*671

2012 = 287*7 + 3 = 3 (mod 7)  20123 = 33 (mod 7) = -1 (mod 7)  20123*671 = (-1)671 (mod 7)

= -1 (mod 7)

2015 = 288*7 - 1 = -1 (mod 7)  20152014 = (-1)2014 (mod 7) = 1 (mod 7)
 20122013 + 20152014 chia hết cho 7

<b>Graph</b>

<b>37.</b> Xét đồ thị được cho bởi ma trận trọng số sau:

A B C D E F G H K

A 1 1 1

B 9 2 8

C 6 2

D 1 5 4 3

E 2

F 9 3

G 9

H 7

K

<b>a.</b> Dùng giải thuật Kruskal, Prime tìm cây khung có trọng lượng nhỏ nhất

</div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>

<b>38.</b> Chứng minh rằng một đồ thị đơn liên thơng có n đỉnh, m cạnh và m  n có chu trình
<b>39.</b> Cho một đồ thị đơn liên thông, bậc của mỗi đỉnh  2. Chứng minh rằng tồn tại hai đỉnh sao

cho có một đường dẫn (path) nối chúng chứa tất cả các đỉnh của đồ thị

<b>40.</b> Cho một đồ thị đơn liên thông, bậc của mỗi đỉnh đều bằng 2. Chứng minh rằng đồ thị có
chu trình chứa tất cả các đỉnh của đồ thị

<b>41.</b> Chứng minh rằng số mặt có số đỉnh là lẻ của một khối đa diện là một số chẵn

<b>42.</b> Xét cây T với tập đỉnh V, ký hiệu d(v) là bậc của đỉnh v  V.

a. CM

∑

<i>v∈V</i>

(2<i>− d</i>(<i>v</i>))=2
Giải

Chứng minh quy nạp theo số nút của cây

với cây chỉ có một nút, điều phải chứng minh hiển nhiên đúng
Giả sử điều phải chứng minh đúng với mọi cây có số nút  n

Ta chứng minh với cây với số nút n+1 điều phải chứng minh cũng đúng

Gọi r là nút gốc của cây , d(r) = k, k cây với gốc là k con của gốc, mỗi một có số nút  n, theo

giả thiết quy nạp ta có:

∑

<i>v∈Vc</i>

(2<i>− d</i>(<i>v</i>))+1=2⇔

∑

<i>v∈Vc</i>

(2<i>−d</i>(<i>v</i>))=1 _{với c = 1, 2, ..., k}



∑

<i>v∈V</i>

(2− d(<i>v</i>))=2<i>−d</i>(<i>r</i>)+

∑

<i>c=</i>1

<i>k</i>

∑

<i>v∈Vc</i>

(2<i>− d</i>(<i>v</i>))=2− k+

∑

<i>c=</i>1

<i>k</i>

1=2<i>− k</i>+<i>k</i>=2
b. CM nếu T có đỉnh bậc m  2 thì T có ít nhất m đỉnh bậc 1

<b>43.</b> Chứng minh rằng đồ thị (đơn, khơng có khun) có 2n đỉnh, bậc của mỗi đỉnh không nhỏ

hơn n là một đồ thị liên thông
Giải

Giả sử đồ thị không liên thơng, nó được phân tích thành ít nhất hai thành phần liên thông, do
tổng số các đỉnh của các thành phần liên thơng = 2n nên phải có thành phần có số đỉnh ≤ n, bậc
của các đỉnh của thành phần liên thông này không vượt quá n – 1 mâu thuẫn

<b>44.</b> Tìm luồng cực đại trong mạng

x2 x3

s=x1 t=x6

x4 x5

12

5
14

4
10

16
10

</div>

<!--links-->