Các câu hỏi phỏng vấn [23]
Ngô Quang Hưng | 23 tháng 12, 2006 | 
Bản để in
- Có một mớ bánh ngọt với tổng cân nặng không hơn 2kg. Mỗi cái bánh nặng ít hơn 1kg. Chứng minh rằng ta có thể chia mớ bánh này ra thành nhiều nhất là 4 phần, mỗi phần có tổng cân nặng nhiều nhất là 1kg. (Không được cắt bánh ra.) Có thể nào luôn chia được thành nhiều nhất 3 phần thỏa điều kiện trên không?
- Cho n số nguyên dương đặt trên một đường tròn. Thay mỗi số bằng trị tuyệt đối của số đi sau trừ đi chính nó, theo chiều kim đồng hồ. Dừng lại khi tất cả các số bằng 0. Chứng minh rằng với n=5 thì ta có thể không dừng được. Với n=4 thì ta luôn dừng.
- Gọi S là một tập 10 số khác nhau giữa 1 và 100. Chứng minh rằng S có hai tập con không giao nhau với tổng bằng nhau.
67. Ta có thể chia thành 3 phần như sau:
- Đánh số cân một số bánh là a_1, a_2,…, a_n sao cho sum(a_i) là lớn nhất và không quá 1.
- Với các bánh còn lại, cũng đánh số b_1,…,b_m sao cho sum(b_j) là lớn nhất và không quá 1. (*)
- Các bánh còn lại nặng không quá 1kg.
Giả sử không phải vậy thì sum(a_i)+sum(b_j) mâu thuẫn (*). Còn nếu không có bánh nào nặng hơn 0.5 thì ta có thể đánh số bánh này là b_(m+1) -> cũng mâu thuẫn (*).
69. Co 2^10 tap con tat ca. Moi tap con co tong khong qua 1000 => phai co 2 tap con co tong giong nhau.
Dear Dongta: 69 - còn điều kiện 2 tập con không giao nhau nữa.
Nếu A & B là 2 tập con có tổng bằng nhau thì A\B & B\A sẽ là 2 tập con không giao nhau có tổng bằng nhau.
Còn câu 68 thì em chỉ có thể giải mechanically
@dongta: Cách giải câu 67 của anh hay quá. Nhưng lập luận của anh đâu cần câu cuối cùng.
Em nhận thấy cách giải có thể cải tiến 1 chút:
Chọn ra một số mẩu bánh (nhóm A) sao cho tổng khổi lượng của chúng lớn nhất và không vượt quá 1.
Số bánh còn lại chia làm 2 nhóm bất kì B và C.
Khi đó 2 nhóm B và C đều có khối lượng 1kg, giả sử B > 1kg; do A + B + C
rilwis: please read this to fix the missing text problem
Vâng anh, em chỉnh lại thế này (không hiểu sao em chỉnh 1 lần rồi nhưng gửi không được nên dùng lời vậy):
Chọn một số mẩu bánh (nhóm A) sao cho tổng khổi lượng của chúng lớn nhất và không vượt quá 1.
Số bánh còn lại chia làm 2 nhóm bất kì B và C.
Khi đó 2 nhóm B và C đều có khối lượng không quá 1kg. Thật vậy nếu 1 trong 2 nhóm có khối lượng vượt quá 1kg, giả sử là B; do tổng khối lượng của A + B + C không quá 2 kg nên tổng khối lượng của A và C nhỏ hơn 2kg, vi phạm cách chọn nhóm A.
Vậy luôn chia được thành 3 nhóm thỏa mãn yêu cầu.
Chết, em ghi nhầm, sửa lại thành:
Chọn một số mẩu bánh (nhóm A) sao cho tổng khổi lượng của chúng lớn nhất và không vượt quá 1kg.
Số bánh còn lại chia làm 2 nhóm bất kì B và C.
Khi đó 2 nhóm B và C đều có khối lượng không quá 1kg.
Thật vậy nếu 1 trong 2 nhóm có khối lượng vượt quá 1kg, giả sử là B; do tổng khối lượng của A + B + C không quá 2 kg nên tổng khối lượng của A và C nhỏ hơn 1kg, vi phạm cách chọn nhóm A.
Vậy luôn chia được thành 3 nhóm thỏa mãn yêu cầu.
Cho em hỏi có thể chỉnh sửa trực tiếp bài mình đã gửi rồi không?
Xin lỗi rilwis, tôi không có account của user thường nên không kiểm tra ngay cho bạn được xem có edit được comment của mình không. Bạn xem xem dưới comment có option “edit this” không? Nếu không có thì là không được.
68. Truong hop n=5, nhan thay sau buoc 1, so cac so le tren vong se luon la chan (0, 2 hoac 4 so le). Neu ta bat dau bang 2 hoac 4 so le thi se ko bao gio ta co the dat duoc 0 so le ca. Vi cach duy nhat de dat duoc 0 so le la phai co 0 hoac 5 so le.
Truong hop n=4, co the nhan thay rang sau mot vai buoc, cac so tren vong se bien thanh so chan. Neu ta chia doi cac gia tri do va thi ta van duoc mot bai toan tuong duong nhung gia tri lon nhat trong vong da bi giam di (it nhat) 1 nua. Do gia tri lon nhat la huu han nen se den luc tat ca la 0.