Miscellaneous Math problems - Tổ hợp

2021/03/19 16:21

#tổ hợp #miscellanea

Post tập hợp linh tinh một số bài toán Tổ hợp.

– Con Heo’s solution –

Bài toán 1

(Nguồn: Câu lạc bộ toán Tổ hợp)

Cho các số nguyên dương mm, nn. Hai bạn AA, BB chơi trò chơi sau: Bạn AA phân hoạch các số 11, 22, 2m\cdots 2m thành mm cặp, sau đó bạn BB chọn ra mỗi số từ mỗi cặp đó, và tính tổng của chúng. Nếu tổng đó bằng nn thì BB thắng, ngược lại thì AA thắng. CMR với mọi số nguyên dương nn, AA luôn có cách phân hoạch để AA luôn thắng trong trò chơi này.

Lời giải.

  • Nếu n<m2n < m^2 hoặc n>m(m+1)n >m(m+1).

AA chỉ cần phân hoạch {1,2,2m}\left \{ 1,2, \cdots 2m \right \} thành {(1,2),(3,4),(2m1,2m)}\left \{ (1,2),(3,4), \cdots (2m-1,2m) \right \}.

Khi đó, tổng nhỏ nhất mà BB có thể tạo ra được là 1+3+2m1=m21+3+\cdots 2m-1 = m^2

và tổng lớn nhất mà BB có thể tạo ra được là 2+4+2m=m(m+1)2+4+\cdots 2m = m(m+1).

Như vậy, AA chắc chắn sẽ thắng.

  • Nếu m2nm(m+1)m^2 \leq n \leq m(m+1).
  1. Trường hợp mm lẻ.
  • Nếu m∤nm \not | n thì AA sẽ phân hoạch {1,2,2m}\left \{ 1,2, \cdots 2m \right \} thành {(1,m+1),(2,m+2),(m,2m)}\left \{ (1,m+1),(2,m+2), \cdots (m,2m) \right \}.

Khi đó, bất kể BB chọn như thế nào thì tổng nhận được cũng sẽ chia hết cho mm. Rõ ràng AA sẽ thắng.

  • Nếu mnm | n thì n=m2n=m^2 hoặc n=m(m+1)n=m(m+1).
  1. Trường hợp mm chẵn.
  • Nếu m2∤n\frac{m}{2} \not | n thì AA sẽ phân hoạch {1,2,2m}\left \{ 1,2, \cdots 2m \right \} thành {(1,m+1),(2,m+2),(m,2m)}\left \{ (1,m+1),(2,m+2), \cdots (m,2m) \right \}.

Khi đó, bất kể BB chọn như thế nào thì tổng nhận được cũng sẽ chia hết cho m2\frac{m}{2}. Rõ ràng AA sẽ thắng.

  • Nếu m2n\frac{m}{2} | n thì n=m2n=m^2 hoặc n=m(m+1)n=m(m+1) hoặc n=m(2m+1)2n=\frac{m(2m+1)}{2}.

Quay trở về Blog