dinhthanhhung

Có $2018$ viên kẹo. Hai người thay phiên nhau bốc kẹo, biết rằng mỗi lần chỉ được bốc $3$,$4$ hoặc $7$ viên kẹo; nếu còn lại $1$ hoặc $2$ viên thì được bốc hết. Người bốc viên kẹo cuối cùng là người chiến thẳng. Hỏi ai là người có chiến thuật thắng, người đi trước hay người đi sau?

Cách làm không hay nhưng hiệu quả

Ta xem xét trường hợp nhỏ để tìm quy luật . n=1,2,3,4 người một thắng . n=5,6,7 người hai thắng . n=8,9,10,11,12,13,14 người một thắng . n=15,16,17 người hai thắng . Từ đây thấy sau 3 trường hợp người một thua và trường hợp thua ở cuối ngay sau 7 trường hợp thắng thì người một thắng tiếp 7 trường hợp sau ( giải thích : , trường hợp đầu bốc 3 , trong 3 trường hợp tiếp chọn 4 viên , 3 trường hợp sau chọn 7 viên thì sẽ đưa về 3 trường hợp mà người đầu bốc thua , hay người hai sẽ thua ) . Và ta cũng thấy sau 7 trường hợp người một thắng thì có 3 trường hợp người hai thắng , do người một bốc như thế nào cũng đưa về trường hợp người đầu thắng hay người hai thắng . 

Đến đây mọi chuyện đã sáng tỏ . Ta có điều sau : với n=0,1,2,3,4,8,9 mod 10 thì người một thắng , trường hợp còn lại người hai thắng .

2018=8 mod 10 vậy người một thắng .

 

Bài 39: Đặt $21$ điểm trên đường tròn. Chứng minh rằng: có ít nhất $100$ cặp điểm tạo ra cung nhỏ hơn hoặc bằng $120^0$

Xét graph đỉnh là $21$ điểm trên, $2$ đỉnh nối với nhau nếu cung tạo bởi chúng lớn hơn $120^0$ .

Dễ thấy đây là graph 3-free nên số cạnh tối đa là $\left \lfloor \frac{21^2}{4} \right \rfloor=110$

Do đó số cặp đỉnh tạo cung nhỏ hơn hoặc bằng $120^0$ là $C_{21}^{2}-110=100$

Tìm số nguyên dương $k$ nhỏ nhất sao cho trong $k$ phần từ tùy ý của tập ${1;2;...;49;50}$ luôn chứa $3$ số là độ dài $3$ cạnh của $1$ tam giác vuông 

Lời giải:

Xét tập A={1,2,3,5,8,13,21,34} gồm 8 phần tử và không có 3 số nào là độ dài 3 cạnh tam giác .

Do đó k>8 .

Ta chứng minh k=9 thỏa mãn .

Phản chứng có 1 tập 9 phần tử không thỏa mãn là B={a_1,...,a_9}

Dễ chứng minh 50>=2F_8+F_7>=55 (MT)

Do đó có dpcm

* Nhận xét : bài trên là một trong những áp dụng của dãy Fibonacci .

Bài này đề đúng là thực hiện các bước a,b so le nhau . Nếu không thì sẽ rất lộn xộn (!)

Lời giải :

Ta thấy sau khi nhân đôi một hàng nào đó , rồi trừ một cột nào đó thì trên bảng sẽ có ít nhất một số lẻ .

Do vậy bước cuối cùng là bước nhân đôi các số trong một hàng .

Mặt khác sau khi nhân , ta được bảng toàn số 0 , vậy bước đó không thay đổi gì cả .

Điều này đưa ta tới kết luận là bảng ban đầu phải có số 0 , điều này vô lí với giả thiết .

Vậy không tồn tại hữu hạn buớc .

Xin lỗi vì đã chém đề =)) Hôm nay nghĩ lại thì với điều kiện như bạn đã cho , ta có lời giải như sau :

Xét một cột và các ô chứa số 1 nằm trên hàng đó ta nhân hai các hàng tương ứng sau đó trừ 1 cột đó đi ( đến khi xuất hiện số 1 thì thôi ) , nếu không có số 1 nào thì ta trừ 1 . Dễ thấy tổng của tất cả các số sẽ giảm sau các biến đổi , đồng thời các biến đổi đảm bảo không có số nào thành số 0 . Do đó đến một lúc nào đấy cột đó sẽ toàn số 1 và lúc này trừ 1 đi ta được toàn số 0.

Thực hiện lần lượt trên các cột , có được bảng toàn số 0.

Cho m viên bi đựng trong n cái hộp (m, n>4), có thể có hộp không có bị và số bị trong hộp không nhất thiết bằng nhau. Ta thực hiện một trò chơi như sau: Mỗi lần lấy ra 2 viên bi ở hai hộp nào đó và bỏ vào hộp thứ 3. CMR: Sau một số bước có thể bỏ hết các viên bi vào một hộp.

Bài này chắc quy nạp là hướng nghĩ dễ nhất rồi .

Lời giải :

Ta kí hiệu (a,b,c,d) là 4 hộp mà hộp 1 có a kẹo , hộp 2 có b kẹo , ...

*m=4 thì có tối đa 4 hộp đựng kẹo là (1,1,1,1),(1,1,2,0),(1,3,0,0),(2,2,0,0)

Ta biến đổi như sau : (1,1,1,1)->(3,1,0,0)->(2,0,2,0)->(2,1,0,1)->(4,0,0,0)

Do đó m=4 là OK .

*Giả sử số kẹo là m thì OK , ta xét trường hợp m+1 kẹo .

Đánh dấu 1 viên kẹo . Theo giả thiết quy nạp thì chuyển được m kẹo còn lại vào 1 hộp .

Nếu hộp đó chứa viên đánh dấu thì xong luôn , ta xét nó không chứa viên đó .

Biến đổi như sau : (1,m,0,0)->(0,m-1,2,0)->(0,m-2,1,2)->(2,m-3,0,2)->(1,m-1,0,1)->(0,m+1,0,0) 

*Kết luận: ...

p/s :

Ừ =))! Mình không đọc kỹ .