MachineGun

Bài 2:

Đánh dấu số phòng từ 1 đến 19. Xét tổng S bằng số người trong phòng nhân với số thứ tự trên phòng.

Không khó để thấy tổng này không thay đổi khi có 2 người chuyển phòng sang 2 phòng bên cạnh và theo hướng ngược nhau nên tổng S này luôn là 190

Nếu không có ai ở phòng chẵn thì 19 người đều ở phòng lẻ thì tổng S sẽ là số lẻ => Vô lý nên trường hợp a không xảy ra

Nếu có 10 người ở phòng 19 thì tổng S chắc chắn lớn hơn 190 => vô lý nên trường hợp b không xảy ra

Bài 3:

Vì chỉ có 2018 điểm nên số các nối là hữu hạn, trong số cách nối đó ta chọn ra cách nối sao tổng độ dài các đoạn nối là nhỏ nhất.

Ta sẽ chứng minh cách nối đó không có 2 đoạn cắt nhau.

Giả sử có 2 đoạn cắt nhau là AB và CD tại E và A, C là đầu đỏ, B, D là đầu xanh thì ta sẽ nối lại A với D, B với C thì theo bất đẳng thức tam giác ta có AE+DE>AD và BE+CE>BC => ngược lại với điều giả thiết cách nối có tổng độ dài nhỏ nhất =>Vô lý

Vậy có cách nối thỏa đề

Bài này có 2 cách hiểu đề: cách đầu tiền là 2 số ở 2 biên thỏa điều kiện, cách thứ hai là 2 biên không cần thỏa điều kiện

Mình sẽ tổng quát hóa lên n số

Với cách hiểu đầu tiên đáp án là 1 dãy số duy nhất là 1, 2, 3, 4,..., n

Giải thích:

Đầu tiên ta sẽ chứng minh n luôn đứng cuối dãy, giả sử n không đứng cuối dãy, ta xét số cuối cùng của dãy là a thì ta thấy a không thể nhỏ hơn tất cả số đứng trước nó vì không có số nào đứng trước nó, nhưng a cũng không lớn hơn tất cả số đứng trước nó vì a<n => Vô lý.

Vậy n đứng ở cuối dãy, tương tự t chứng minh n-1 đứng vị trí thứ n-1 trong dãy và tiếp tục như vậy ta có đpcm

Cách hiểu thứ 2:

Đặt S(n) là số các số dãy thỏa đề có độ dài  n, A(n) là số các số dãy thỏa đề có độ dài n và n là số đứng cuối, B(n) là số các số dãy thỏa đề và n không đứng cuối dãy

Dễ thấy ta có $S(n)=A(n)+B(n)$

Đầu tiên ta tính A(n)

Dễ dàng thấy số n đứng cuối không ảnh hưởng đến dãy vì tất cả mọi số đều bé hơn nó nên $A(n)=S(n-1)$ 

Tiếp theo ta tính B(n)

Xét 2 trường hợp, nếu n-1 đứng cuối dãy và n-1 không đứng cuối dãy

Ở trường hợp 1, nếu ta bỏ số n-1 đi và thay n bằng n-1 thì dãy B(n) không khác gì dãy S(n-1)

Ở trường hợp 2, ta sẽ chứng minh n-1 đứng ngay trước n

Giả sử ngược lại nếu n-1 không đứng trước n thì dễ dàng thấy số ở giữa n-1 và n không thỏa đề, vậy n-1 đứng ngay trước n

Ta gộp n-1, n thành n-1 thì dãy B(n) sẽ thành dãy B(n-1)

Vậy $B(n)=S(n-1)+B(n-1)$

Kết hợp với A(n) ta có $S(n)=2S(n-1)+B(n-1)$

Liên tục thay thế $B(n)=S(n-1)+B(n-1)$  ta sẽ có $S(n)=2S(n-1)+S(n-2)+S(n-3)+...+S(1)$