Danh sach lop

My Class

Họ	&	T ên	Số điện thoại	Ngày sinh	Chú thích
Nguyễn	Văn	Đại	0977918119 – 01682010095	27/9/1976
Hoàng	Thanh	Đoan	0955465039 – 0955465040	2/6/1990
Võ	Ngọc	Hạp	01665488661	16/6/1988
Huỳnh	Nguyên	Khiêm	01664117645	23/1/1988
Ktla		Y Nhiên	0979690024 – 01689331995	4/2/1990
Nguyễn	Thanh	Sang	01698455065	20/1/1984
Lê	Minh	Thuận	0985131032 – 01694344288	26/10/1990
Nguyễn	Đức	Tính	01695689928	22/8/1989
Nguyễn	Thành	Trung	0979335146 – 01677880575	10/12/1990
Vũ	Hồng An	Tuyên		10/12/1983
Đào	Duy	Đa

Homework

Bài tập toán rời rạc 2

Bài toán đếm

1. Có bao nhiêu số hoặc là số lẻ hoặc là số chính phương trong các số tự nhiên từ 1 đến 1000?
2. Có bao nhiêu xâu nhị phân độ dài 8 không chứa 6 số 0 liền nhau?
3. Có bao nhiêu số có 10 chữ số lập từ các chữ số 1, 2, 3 mà trong đó mỗi chữ số 1, 2, 3 đều có mặt ít nhất 1 lần?
4. Có bao nhiêu số nguyên dương nhỏ hơn 10000 có tính chất: chia hết cho 7 nhưng hoặc không chia hết cho 5 hoặc không chia hết cho 2?
5. Có bao nhiêu hoán vị của các số tự nhiên 1, 2, …, 10 mà trong đó các số 1, 2, 3 không đứng cạnh nhau theo thứ tự tăng dần?
6. Gọi S_n là số cách chia một hình chữ nhật kích thước 2 x n ra thành các hình chữ nhật con có các cạnh song song với cạnh của hình chữ nhật đã cho có kích thước là 1×2. Lập công thức truy hồi cho S_n.
7. Gọi T_n là số cách chia một hình chữ nhật kích thước 2 x n ra thành các hình chữ nhật con có các cạnh song song với cạnh của hình chữ nhật đã cho và có thể có các kích thước là 1×2, 2×1, 2×2. Lập công thức truy hồi cho T_n.
8. * Gọi F_n là số xâu nhị phân độ dài n không chứa 3 số 0 liên tiếp. Lập công thức truy hồi cho F_n. Từ đó tính F₁₀.
9. * Giả sử a là một xâu nhị phân, ký hiệu C(a) là số lớn nhất các bit 0 liên tiếp trong a. (Ví dụ: C(10010)=2, C(00110001)=3.) Gọi S_n là số xâu n-bit a với C(a) <= 2. Tìm một công thức truy hồi cho S_n.

10. * Xét lưới ô vuông n x n. Một đường đi từ góc trái dưới đến góc phải trên của lưới ô vuông này thỏa mãn điều kiện: chỉ di chuyển theo hướng từ trái qua phải hoặc từ dưới lên và không vượt qua (có thể đi qua các đỉnh của đường chéo chính) đường chéo chính của lưới đươcj gọi là một đường đi hợp lệ. Gọi C_n là số đường đi hợp lệ trên lưới n x n. Chứng minh rằng C_n thỏa mãn hệ thức sau:

Bài tập toán rời rạc 3

Bài toán Liệt kê

1. Hai đội bóng chuyền A, B thi đấu với nhau. Đội thắng trong trận đấu sẽ là đội giành được 3 hiệp thắng trước. Liệt kê tất cả các khả năng có thể của trận đấu giữa hai đội.
2. Liệt kê các xâu nhị phân độ dài 5 không chứa hai số 0 liên tiếp. Tổng quát: Liệt kê tất cả các xâu n-bit không chứa hai bit 0 liên tiếp.
3. Liệt kê tất cả các chỉnh hợp có lặp chập 4 từ 3 chữ cái A, B, C mà không chứa hai chữ A hoặc hai chữ B.
4. Cho n là số nguyên dương. Một cách phân chia số n là biểu diễn n thành tổng các số tự nhiên không lớn hơn n. Chẳng hạn 8 = 2 + 3 + 2. Hai cách chia được gọi là đồng nhất nếu chúng có cùng các số hạng và chỉ khác nhau về thứ tự sắp xếp. Bài toán được đặt ra là, cho số tự nhiên n, hãy liệt kê mọi cách phân chia số n.
   1. Liệt kê tất cả các xâu nhị phân độ dài n có tổng các bít 1 đúng bằng k≤n.
   2. *Tìm dãy con dài nhất có thứ tự tăng dần (giảm dần). Cho dãy số a1, a2,…, an. Hãy tìm dãy con dài nhất được sắp xếp theo thứ tự tăng (hoặc giảm) dần.

Dữ liệu vào cho bởi file tapcon.in, dòng đầu tiên ghi lại số tự nhiên n (n≤100), dòng kế tiếp ghi lại n số, mỗi số được phân biệt với nhau bởi một hoặc vài ký tự rỗng. Kết quả ghi lại trong file tapcon.out.

Ví dụ sau sẽ minh họa cho file tapcon.in và tapcon.out.

tapcon.in tapcon.out

5 5

7 1 3 8 9 6 12 1 3 8 9 12

1. *Tam giác thần bí. Cho một lưới ô vuông gồm n x n ô và số nguyên dương k. Tìm cách điền các số tự nhiên từ 1 đến 3n-3 vào các ô ở cột đầu tiên, dòng cuối cùng và đường chéo chính sao cho tổng các số điền trong cột đầu tiên, dòng cuối cùng và đường chéo chính của lưới đều bằng k. Ví dụ n = 5, k = 35 ta có cách điền sau:

11
10	3
9		2
1			7
4	5	6	8	12

Phát triển thuật toán dựa trên thuật toán quay lui để chỉ ra với giá trị của n, k cho trước bài toán có lời giải hay không. Nếu có câu trả lời chỉ cần đưa ra một lời giải.

Phần Chỉnh hợp, Hoán vị, Tổ hợp

1. Có bao nhiêu hoán vị của các chữ cái trong xâu ABCDEF mà trong đó có chứa xâu con DEF?
2. Có bao nhiêu hoán vị của các chữ cái trong xâu ABCDEF mà trong đó có chứa ba chữ cái D, E, F đứng cạnh nhau?
3. Có bao nhiêu cách xếp 6 người vào ngồi quanh một cái bàn tròn (hai cách xếp không coi là khác nhau nếu chúng có thể thu được từ nhau bởi phép quay bàn tròn)?
4. Có bao nhiêu cách xếp 7 học sinh nam và 5 học sinh nữ ra thành một hàng ngang sao cho không có hai nữ sinh nào đứng cạnh nhau?
5. Có bao nhiêu xâu nhị phân độ dài 32 mà trong đó có đúng sáu số 1?
6. Có bao nhiêu xâu ký tự khác nhau có thể tạo được từ các chữ cái MISSISSIPI?
7. Có 8 cuốn sách khác nhau. Hỏi có bao nhiêu cách phân chia các cuốn sách này cho 3 sinh viên Mơ, Mai, Mận sao cho Mơ nhận được 4 cuốn còn Mai và Mận mỗi người nhận 2 cuốn?
8. Giả sử X là tập t phần tử. Ta nói tổ hợp lặp chập k từ t phần tử của X là một bộ không có thứ tự gồm k thành phần lấy từ các phần tử của X.

Ví dụ X = {a, b, c}.

Các tổ hợp lặp chập 2 từ các phần tử của X là: (a,a), (a,b), (a,c), (b,b), (b,c), (c,c).

Chứng minh rằng số tổ hợp lặp chập k từ t là C(k+t-1,t-1) = C(k+1-t,k)

1. Có 3 giỏ đựng các quả cầu xanh, đỏ, tím. Mỗi giỏ chỉ chứa các quả cầu cùng màu và mỗi giỏ chứa không ít hơn 8 quả cầu.
   1. Có bao nhiêu cách chọn ra 8 quả cầu?
   2. Có bao nhiêu cách chọn ra 8 quả cầu mà trong đó có đủ cả 3 màu?

10. Xét phương trình: x₁+x₂+x₃+x₄ = 29

1. Phương trình trên có bao nhiêu nghiệm nguyên dương?
2. Phương trình trên có bao nhiêu nghiệm nguyên không âm

(một nghiệm của phương trình là một bộ (a,b,c,d) sao cho a+b+c+d = 29).

Bài toán Tồn tại

1. Trên mặt phẳng cho n >= 6 điểm, khoảng cách giữa các cặp điểm là khác nhau từng đôi một. Mỗi điểm được nối với điểm gần nó nhất. Chứng minh rằng mỗi điểm được nối với không quá 5 điểm.
2. Một trung tâm máy tính có 151 máy tính. Các máy của trung tâm được đặt tên bởi các số nguyên dương trong khoảng từ 1 đến 300 sao cho không có hai máy nào được đặt tên trùng nhau. Chứng minh rằng luôn tìm được 2 máy có tên là hai số nguyên liên tiếp.
3. Các học sinh của một lớp học gồm 45 nam và 35 nữ được xếp thành một hàng ngang. Chứng minh rằng trong hàng đó luôn tìm được 2 học sinh nam mà ở giữa họ có 8 người đứng xen vào.
4. * Viết các số nguyên từ 1 đến 12 quanh vòng tròn theo thứ tự tùy ý. Chứng minh rằng luôn tìm được 3 số liền nhau có tổng lớn hơn hoặc bằng 26.
5. Chứng minh rằng trong 10 số tự nhiên bất kỳ bao giờ cũng tìm được hoặc là hai số có tổng chia hết cho 16 hoặc là hai số có hiệu chia hết cho 16.
6. Có 3 chủ đề và có 17 người viết thư trao đổi với nhau về 3 chủ đề đó, mỗi cặp chỉ trao đổi với nhau về 1 chủ đề. Chứng minh rằng luôn tìm được 3 người đôi một trao đổi với nhau về cùng một chủ đề.

Phát biểu bài toán dạng Hình học: Có 17 điểm trên mặt phẳng, nối từng cặp điểm với nhau. Dùng 3 màu (Xanh, Đỏ, Vàng) tô màu các đoạn thẳng nối từng cặp điểm, mỗi đoạn chỉ tô bằng 1 màu. Chứng minh rằng luôn tìm được một tam giác có 3 cạnh cùng màu.

1. Trong không gian cho 9 điểm có tọa độ nguyên. Chứng minh rằng trong 9 điểm này luôn tìm được 2 điểm sao cho đoạn thẳng nối chúng đi qua điểm có tọa độ nguyên.
2. Một tay đô vật tham gia thi đấu giành chức vô địch trong 75 giờ. Mỗi giờ anh ta có ít nhất một trận đấu, nhưng toàn bộ anh ta có không quá 125 trận. Chứng tỏ rằng có những giờ liên tiếp anh ta đã đấu đúng 24 trận.
3. Cho n là số nguyên dương bất kỳ. Chứng minh rằng luôn lấy ra được từ n số đã cho một số số hạng thích hợp sao cho tổng của chúng chia hết cho n.

10. Trong một cuộc lấy ý kiến về 7 vấn đề, người được hỏi ghi vào một phiếu trả lời sẵn bằng cách để nguyên hoặc phủ định các câu trả lời tương ứng với 7 vấn đề đã nêu. Chứng minh rằng với 1153 người được hỏi luôn tìm được 10 người trả lời giống hệt nhau.