Cho $a,b,n$ là các số nguyên dương thoả mãn :

$$7ab+a\mid a^3+(7b+1)^3+7^na$$

Chứng minh $a$ là lập phương của một số nguyên dương.

Từ đề bài có thể suy ra $a|(7b+1)^3$, do đó với $p$ nguyên tố bất kì mà $p|a \Rightarrow p|7b+1 \Rightarrow p \ne 7$ nên $(p,7^n)=1$

Vì $a|(7b+1)^3$ nên $v_p((7b+1)^3) \ge v_p(a)=v_p(7^na)$ Dễ thấy $v_p(a(7b+1))>v_p(a),v_p(a^3)>v_p(a) \Rightarrow v_p(a)=v_p((7b+1)^3) \vdots 3$

Đây là đpcm.

Bài toán: Cho tập $S=\{a_1, a_2, ..., a_n\}\subset \mathbb{N^*}$ và $P(x)\in\mathbb{Z}[x]$. Giả sử rằng với mọi $k\in\mathbb{Z^+}$ đều tồn tại chỉ số $i$ sao cho $a_i\;|\;P(k)$. CMR: tồn tại một chỉ số $i_o$ sao cho $a_{i_0}\;|\;P(k), k\in\mathbb{Z}$$

Trước tiên đặt $a$ là BCNN của tất cả các phần tử thuộc $S$.

Với mọi số $r \in Z$ thì luôn tồn tại số $k$ để $r+ka \in Z^+$, khi đó thì $P(r) \equiv P(r+ka)$ (mod $a$), mặt khác tồn tại $a_i$ để $a_i|P(r+ka)$ và $a_i|a$ ta suy ra $a_i|P(r)$.

Tìm nghiệm nguyên của phương trình:

(x+y²)(x²+y)=(y-x)²

Trước tiên đặt $d>0$ là UCLN của $x$ và $y$ trong đó $x=da,y=db \Rightarrow (a,b)=1$ như vậy pt trên tương đương với:

$$(a+db^2)(b+da^2)=(a-b)^2 (*)$$

Không mất tính tổng quát ta giả sử $|a| \ge |b|$, từ biểu thức trên ta suy ra:

$$4a^2 \ge (a-b)^2 \ge da^2+b \ge 0 \Rightarrow d \le 5$$

Nếu mà $d=5$ thì những đẳng thức trên xảy ra đồng thời và ta có $a=-b$

Khi đó thay vào $(*)$ ta được:

$$(5b-1)(5b+1)=4 \Rightarrow 5b^2=1$$

loại nghiệm này.

Vậy $1 \le d \le 4$

Ngoài ra ta biến đổi biểu thức ban đầu theo một cách khác:

$(x+y^2)(y+x^2)=(y-x)^2 \Leftrightarrow xy(xy+2)=(1-x-y)(x^2-xy+y^2) \Leftrightarrow ab(d^2ab+2)=(1-da-db)(a^2-ab+b^2)$

Vì $a,b$ nguyên tố cùng nhau nên biểu thức $a^2-ab+b^2$ luôn là số lẻ. Do đó nếu $d$ chẵn thì bên trái chia hết cho 2 mà bên phải thì không. Vậy $d$ phải lẻ.

Ngoài ra cũng từ biến đổi cuối cùng ở trên ta suy ra được $(a^2-ab+b^2)|d^2ab+2$.

Nếu $d=1$ thì ta suy ra $ab+2 \ge a^2-ab+b^2 \Rightarrow 2 \ge (a-b)^2$

Mà $a$ không thể bằng $b$ nên ta suy ra $|a-b|=1$

Đến đây thay vào giải khá đơn giản ra $a=1,b=0$ và ngược lại.

Bây giờ nếu $d=3$ cũng từ biểu thức trên ta suy ra $ab|(1-da-db) \Rightarrow a|1-3b$

Đặt $|1-3b|=k|a|$ thì ta chặn được $1 \le k \le 2$

Đến đây thì còn vài trường hợp thay vào và giải ra đáp án, mình không rõ là có cách nào để loại bớt trường hợp nữa không nhưng đến đây chắc khả thi rồi.

Cho dãy số: $\qquad u_n=\sum_{k=0}^{2n} \frac{1}{n^2+k}\qquad (n=1,2,...)$

 

Tính tổng: $ \quad S_n=\sum_{k=1}^n \left\lfloor\frac{2}{u_k}\right\rfloor $

Bài toán mới nhìn vào có vẻ hơi đáng sợ nhưng bình tĩnh một chút đánh giá khách quan thì kiểu toán này chỉ có cách chặn 2 đầu thôi.

Ta có:

$$ \sum_{k=0}^{2n}\frac{1}{n^2}>u_n=\sum_{k=0}^{2n} \frac{1}{n^2+k}>\sum_{k=0}^{2n}\frac{1}{(n+1)^2} \Rightarrow \frac{2n+1}{n^2}>u_n>\frac{2n+1}{(n+1)^2}$$

Tuy nhiên đến đây mà chia 2 lật ngược lại thì chưa đạt được điều ta mong muốn, bây giờ ta cần một điều chặt hơn một chút là

$$ \frac{2n}{n^2}>u_n>\frac{2n+2}{(n+1)^2}$$

Tức là ta cần một tổng $i+1$ số hạng trong sigma biểu diễn $u_n$ có tổng bé hơn $\frac{i}{n^2}$ tức là $i+1$ số này đều không nhỏ hơn $\frac{i+1}{i}.n^2$, tự nhiên ta thử với $i=n$ thì đúng luôn chọn các số từ $n(n+1)$ đến $n(n+2)$. Như vậy ta viết lại $u_n$

$$ u_n=\sum_{k=0}^{n-1}\frac{1}{n^2+k}+\sum_{k=n}^{2n}\frac{1}{n^2+k}<n.\frac{1}{n^2}+(n+1).\frac{1}{n(n+1)}=\frac{2}{n}$$

$$ u_n=\sum_{k=0}^{n-1}\frac{1}{n^2+k}+\sum_{k=n}^{2n}\frac{1}{n^2+k}>n.\frac{1}{n(n+1)}+(n+1).\frac{1}{(n+1)^2}=\frac{2}{n+1}$$

Do vậy $n<\frac{2}{u_n}<n+1$

Suy ra $S_n=\frac{n(n+1)}{2}$

Ta sẽ chứng minh là không phải luôn luôn sắp được như vậy. Ta thiết kế một mối quan hệ giữa các đứa trẻ chỉ ra nó không thỏa mãn. Đầu tiên xét một đồ thị hình cây với đỉnh là một đứa trẻ (bậc 0). Đứa trẻ này có 3 người quen (bậc 1), 3 đứa này mỗi đứa lại quen 3 đứa khác nữa (bậc 2),.... cứ vậy mỗi đứa trẻ xuất hiện trong đồ thị lại quen với 3 đứa trẻ khác. Ta thành lập được một cây tam phân $n$ bậc, ta có thể cho $n=2010$ cũng được.

Giả sử tồn tại cách sắp xếp để thỏa mãn đk đề bài với những đứa trẻ thuộc cái cây này.

Xét vị trí của đứa trẻ ở đỉnh bậc 0 là $a$. Lấy vị trí của mỗi đứa trẻ trừ cho $a$, ta xem như vị trí của đứa trẻ ở bậc 0 là 0. Khi đó ta có thể chứng minh quy nạp theo $k$ là nếu một đứa trẻ thuộc cây tam phân ở bậc không vượt quá $k$ thì trị tuyệt đối vị trí của nó không vượt quá $2011k$.

Tuy nhiên tổng số đứa trẻ thuộc cây tam phân mà có bậc không vượt quá $k$ là $\frac{3^{k+1}+1}{2}$.

Ta chọn được $k$ đủ lớn mà bé hơn $2010$ để $\frac{3^{k+1}+1}{2}>2.2011k+1$.

Điều này chứng tỏ phải có 2 em trùng vị trí, vô lí.

Có thể tối ưu số em bé là $\frac{3^{k+1}+1}{2}$ với $k$ thỏa mãn bđt trên.

Trên đường tròn cho n điểm, từ các điểm nói trên hiển nhiên ta có ${C_n}^2$ đoạn thẳng và tổng số các đa giác là

$({C_n}^3 + {C_n}^4 + {C_n}^5 + ... + {C_n}^n)$ .Hãy tìm số cách bỏ bi các đoạn thẳng sao cho không còn đa giác nào , biết rằng mỗi cách bỏ đi các đoạn thẳng như vậy thì mỗi điểm nói trên , vẫn tồn tại ít nhất một đoạn thẳng nhận nó làm đầu mút ?

Yêu cầu bài này phải phát biểu lại là với một cấu hình xóa đi các đoạn thẳng thỏa mãn 2 điều kiện nêu ra thì cấu hình này có nhiều nhất bao nhiêu đoạn thẳng.

Có nhiều nhất là $n-1$ đoạn thẳng (vd $1$ điểm nối với $n-1$ điểm còn lại chẳng hạn). Cái này liên quan đến định nghĩa cây ( đồ thị liên thông, không có chu trình) trong lý thuyết đồ thị.

Mình sẽ chỉ ra một cách chứng mình mình nghĩ ra (tham khảo sách về tính chất của cây với $n$ điểm có thể bạn sẽ tìm thấy chứng minh hay hơn).

- Hai điểm gọi là liên thông nếu có một đường đi tạo bởi ít nhất 2 đoạn thẳng nối hai điểm đó.

- Nếu một cấu hình thỏa mãn 2 điều kiện bài toán mà có hai điểm không liên thông, ta có thể nối chúng lại với nhau để có một cấu hình mới thỏa mãn yêu cầu mà có số đoạn thẳng lớn hơn. Do đó cần tìm max số đoạn thẳng trong trường hợp 2 điểm bất kì trong $n$ điểm liên thông với nhau.

- Xét một cấu hình thỏa mãn : không có đa giác, mỗi điểm trong $n$ điểm là mút của ít nhất một đoạn thẳng, cấu hình này có nhiều đoạn thẳng nhất và 2 điểm bất kì (khác 2 mút một đoạn thẳng) trong $n$ điểm liên thông với nhau. Xét tập $S$ chứa một điểm bất kì trong $n$ điểm.

- Mỗi bước ta xóa đi một đoạn thẳng thỏa mãn : đoạn thẳng này có một mút là một điểm thuộc $S$ và một điểm không thuộc $S$ và sau đó thêm cái điểm nằm ngoài $S$ của đoạn thẳng vừa xóa vào $S$.

- Rõ ràng khi tập $S$ chưa lấp đầy bởi $n$ phần tử thì luôn tìm được ít nhất một đoạn thẳng thỏa mãn để xóa. Nếu không các điểm trong $S$ không liên thông với điểm nào ngoài $S$.

- Khi đó tất cả các điểm thuộc $S$ mà không nối với nhau bởi một đoạn thẳng đã bị xóa thì liên thông với nhau.

- Khi tập $S$ đầy $n$ phần tử thì không còn đoạn thẳng nào nữa. Vì nếu tồn tại một đoạn thẳng nối 2 điểm trong $S$ mà đoạn này chưa bị xóa, khi đó tồn tại một đường đi lớn hơn 2 đoạn thẳng nối 2 điểm đó, như thế thì cấu hình ban đầu chứa một đa giác.

Vậy cấu hình ban đầu nêu ra có đúng $n-1$ đoạn thẳng.

 

-          Nhan sắc VMF (trên VMF có cô nào xinh không =]] )

 

Tình hình là tên đồng chí có xuất hiện trong list nhân sự VMEO nhưng mà chưa đóng góp được gì, đề nghị đồng chí làm tốt nhiệm vụ in đậm ở trên, thu thập thông tin lẫn fb của các em xinh tươi, đồng chí hoạt động ở box nào thì gửi thông tin về trưởng ban chọn đề box đấy để kiểm duyệt =)) có gì chúng ta sẽ trao đổi thêm về vấn đề này sau buổi offline (vừa gửi lời mời kết bạn trên fb rồi). 

Thể theo nguyện vọng của đồng chí supermember, lâu lâu lên diễn đàn trao đổi với đồng chí một tí, cũng hi vọng là có thể chia sẻ trao đổi chút gì đó với các bạn.

Từ một bài số học mình biết cũng khá lâu, hôm nay rỗi rãi phát biểu nó sang một bài tổ hợp. Cho một tập hợp $A$ gồm $n$ phần tử, và một dãy tập hợp con khác rỗng phân biệt của $A$ là $A_1,A_2,...,A_T$ với $T=(n-1)^2+1$. Với một dãy số nguyên dương tăng bất kì $a_1,a_2,..,a_n$ mà $a_n \le T$ thì tồn tại $i,j,1 \le i < j \le n$ và $A_{a_i}$ là một tập con của $A_{a_j}$. Chứng minh cái dãy tập hợp trên chứa A.

Thử giải xem nào đại ca supermember. Qua chủ đề này có thể mình sẽ nói 1 chút về sự liên hệ giữa các con số và tập hợp. Theo các bạn là nó có liên hệ gì không?

Chứng minh đẳng thức sau:

 

$\sum_{k=0}^n \left(\frac{-1}{2}\right)^k{n\choose k}{2k+1\choose k}= \dfrac{(-1)^n\left(\frac{2n-1-(-1)^n}{2}\right)!!}{\left(\frac{2n+1-(-1)^n}{2}\right)!!}$

 

Trong đó: $\begin{cases}(2m)!!=2^m.m!\\ (2m-1)!!=\dfrac{(2m)!}{2^m.m!}\end{cases}$

Bài này có thể sử dụng kĩ thuật tính hệ số đa thức khá hiệu quả. Tổng cần tính chính là hệ số tự do trong khai triển:

$$ \sum_{k=0}^n \left(\frac{-1}{2}\right)^k{n\choose k} \frac{(x+1)^{2k+1}}{x^k}$$

$$= (x+1) \sum_{k=0}^n {n\choose k}\frac{(-1)^k(x+1)^{2k}}{(2x)^k} = (x+1)\left( 1-\frac{(x+1)^2}{2x} \right)^n=(x+1)\frac{(-1)^n(x^2+1)^n}{2^nx^n}$$

Hệ số tự do của khai triển này chính bằng $$\frac{(-1)^n}{2^n}{n\choose \lfloor \frac{n}{2} \rfloor}$$

Có thể kiểm tra cái này bằng với vế phải, e k biết có phải thầy biến đổi từ giá trị này ra công thức tường minh theo n không có dấu giá trị tuyệt đối không? Nếu là như vậy thì em rất muốn biết thầy biến đổi ntn

E không hiểu sao nó k hiện công thức dù đã cố gắng sửa rồi, hi vọng thầy đọc và hiểu được. Em rất thích đọc những bài toán do thầy post vì trước khi post 1 bài toán thầy đều đầu tư ít nhiều vào đó!

định nghĩa một xích là $1$ dãy các tập hợp $(A_{a_1};A_{a_2};...;A_{a_t})$ thoả mãn $0<a_1<a_2<...<a_t<T+1$ và $A_{a_i}\subset A_{a_{i+1}} \forall 1\leq i\leq t-1$. Với mỗi tập $A_i$, gọi $f(A_i)$ là xích dài nhất nhận $A_i$ là tập đầu tiên trong xích. Giả sử mọi xích đều có độ dài $\leq n-1$ thì lúc đó tồn tại $n$ tập $A_{b_i} \forall i=\overline{1,n}$ thoả mãn $f(A_{b_i})=f(A_{b_j}) \forall i,j=\overline{1,n}$. Nếu tồn tại $i;j$: $1\leq i< j\leq n$ để $A_{b_i}\subset A_{b_j}$ thì $f(A_{b_i})\geq f(A_{b_j})+1$ (vô lí). Vì vậy $n$ tập trên không thoả mãn đề bài, suy ra giả sử sai. Vậy tồn tại $1$ xích độ dài $n$, nhận $A_t$ làm tập cuối cùng trong dãy. Lúc đó $\left | A_t \right |\geq n\Rightarrow A_t=A$.

Lời giải của bạn chính xác rồi, lời giải của mình hơi khác một tí nhưng chung quy vẫn là nguyên lí Dirichlet, thế theo bạn bài toán này phát biểu một cách số học thì nó như thế nào?

Không biết ngoài mấy nghiệm thầy nêu có một cách nào để moi ra thêm nghiệm của nó không nhỉ?

Ta thử biến đổi một chút phần $A(n,m)$. Ta có $P(n+1,m)=P(n,m)+A(n+1,m-1)=\frac{1}{2(m+2)}(A(n+1,m)+A(n,m)+A(1,m))$

Như vậy suy ra $P(n+1,m)-P(n,m)=A(n+1,m-1)=\frac{1}{2(m+2)}(A(n+1,m)-A(n-1,m))$

Lại đặt $B(n,m)=\frac{A(n,m)}{2^m.(m+2)!}$

Ta có thể suy ra $B(n+1,m-1)=B(n+1,m)-B(n-1,m)$

Với dãy truy hồi 2 biến thế này không biết có làm được bằng hàm sinh không? Kiểu giống như công thức Pascal.

Cho $l\leq k\leq n$ là các số thỏa mãn:

$\Im$ là họ các tập L-phần tử của X={1,2,...,n} nào đó  

thỏa mãn:với mọi tập con A có K-phần tử của X đều chứa ít nhất 1 tập B thuộc $\Im$

C/m:$\left | \Im \right |\geq \frac{\begin{pmatrix} n\\ l \end{pmatrix}}{\begin{pmatrix} 2\\ k \end{pmatrix}}$

Tại sao lại là $\begin{pmatrix} 2\\ k \end{pmatrix}$? Vậy chỉ xét trường hợp $k \le 2$ thôi sao?

Thực ra không khó để chứng minh giá trị nhỏ nhất của $\left | \Im \right |$ là $\begin{pmatrix} n\\ l \end{pmatrix} - \begin{pmatrix} k\\ l \end{pmatrix}+1$. 

Viết hẳn hoi ra đi bạn

chứ cứ úp mở thế ai pít đc

Bởi vì lâu rồi mình k dùng diễn đàn nên quên cách đánh công thức ngại viết.

Xin lỗi trong lúc suy nghĩ mình hơi nhầm lẫn khái niệm 1 tí, cái mình nói là số nhỏ nhất để với mọi tập có từng đó phần tử sẽ luôn thỏa đề bài.

Còn tập thỏa đề bài có số phần tử nhỏ nhất có vẻ sẽ khó hơn nhưng có thể chứng minh số này không nhỏ hơn $C_n^l/C_k^l = C_n^k/C_{n-l}^{k-l}$

nên có thể thay $C_2^k$ của bạn bằng $C_k^l$.

Chứng minh thì mỗi tập thuộc $J$ có $C_{n-l}^{k-l}$ tập gồm $k$ phần tử là con $X$ và chứa tập này. Như vậy $|J|.C_{n-l}^{k-l}$ không bé hơn số tập con có $k$ phần tử của $X$.

Với mỗi số nguyên dương $n,m$ Xét tổng:

$$P(n,m)=\sum_{k=1}^n \prod_{r=0}^m(k+2r)$$

________________

$1)\quad$ Chứng minh rằng $P(n,m)$ là một đa thức bậc $m+2$ của $n$

$2)\quad$ Chứng minh rằng $P(0,m)=P(-1,m)=0$

Nói cách khác

$\qquad$ Trong phân tích nhân tử đa thức có chứa $n(n+1)$

$\qquad$ và $P(-2m,m)=P(-2m-1,m)=0$ nếu $m$ chẵn.

Nói cách khác

$\qquad$ (Trong phân tích nhân tử đa thức có chứa $(n+2m)(n+2m+1)$ nếu $m$ chẵn.

$3)\quad$ Biết rằng: $2(m+2) P(n,m)=\prod_{k=0}^m (2k+1)+A(n,m)+A(n-1,m)$

$\qquad$ Tìm $A(n,m)$.

Nói cách khác

$\qquad$ Tìm cách tính tổng $P(n,m)$

Đặt $A(k,m)= \prod_{r=0}^{m+1}(k+2r)$, như vậy $P(n,m)=\sum_{k=1}^nA(k,m-1)$, khi đó ta có:

$$P(n,m+1)=\sum_{k=1}^nA(k,m)=\sum_{k=1}^nA(k,m-1)(k+2m+2)$$

Mặt khác ta lại có $A(k-2,m)=(k-2)A(k,m-1)$ với $k \ge 3$. Do đó ta có thể viết lại $P(n,m+1)=\sum_{k=3}^n(k-2)A(k,m-1)+A(n-1,m)+A(n,m)$

Ta suy ra:

$$\sum_{k=1}^nA(k,m-1)(k+2m+2)=\sum_{k=3}^n(k-2)A(k,m-1)+A(n-1,m)+A(n,m)$$

$$ \Rightarrow (2m+4)\sum_{k=1}^nA(k,m-1)=A(n-1,m)+A(n,m)+A(1,m-1)$$

$$ \Rightarrow (2m+4)P(n,m)=A(n-1,m)+A(n,m)+A(1,m-1)$$

Đến đây nếu $n$ chẵn thì có thể rút gọn $A(n,m)$ được còn nếu $n$ lẻ thì em thử mà chưa làm được.

Thực ra 2 bài này em lấy trong 1 quyển sách , cả 2 đều được đánh dấu * và chỉ có phần gợi ý rất ngắn nên em có đăng lên để mọi người thảo luận , giờ thì em đã  lời giải 2 bài này rồi nhưng tại không ai hỏi nữa nên em thôi luôn @@ . Sáng mai em sẽ post ý tưởng 

Anh vẫn có hướng giải hai bài này, anh nghĩ là em post lên vì chưa giải được vì vậy anh chỉ muốn nói là nếu chưa giải được em hãy post lên ý tưởng của em, mọi người cùng thảo luận thì nhìn ra tại sao mình không giải được, sẽ thấy được ưu nhược điểm trong cách tiếp cận của mình và hơn nữa như vậy mới dễ có bạn vào tham gia thảo luận với em, biết đâu tìm được những ý tưởng khác hay hơn. Anh sẽ nói sơ ý tưởng của anh trong 2 bài này, chỉ là một chút ý tưởng anh cho là khả thi, cũng chưa thử cụ thể là có làm được hay không.

Bài đầu thì để ý một chút tính chất là nếu đổi vị trí các cột với nhau và đổi vị trí các hàng với nhau thì chẳng ảnh hưởng gì đến bài toán nên nếu như ta tìm được một cặp khác màu đặt 2 con xe lên đó, dùng phép đổi cột và đổi hàng ta có thể đưa 2 ô vừa đặt quân nằm trên hv 2x2 của góc bàn cờ, đến đây dùng một chút lập luận về số màu để đưa về hv $(n-2)$x$(n-2)$. Đặt $n=2k$ chứng minh bài toán đúng với $k=2$ sau đó có thể quy nạp theo $k$.

Bài 2 thì chú ý là một hàng có nhiều nhất $2$ ô được chọn và một cột cũng thế và dùng tính chất một hàng mà chứa 2 ô được chọn thì 2 ô đó chiếm 2 cột chứa 1 ô, ngược lại một cột chứa ô được chọn thì 2 ô đó chiếm 2 hàng chứa 1 ô, kết quả sẽ là $4n$.

Có 2 ý tưởng để đếm bài này, đầu tiên dễ thấy là truy hồi. Gọi $S_n$ là tập hợp các tập con thỏa mãn với $n$ thì một tập mà thuộc $S_{n+1}$ nó sẽ là một tập trong $S_n$ còn nếu không thì nó chứa $n+1$ suy ra các phần tử của nó bé hơn hoặc bằng $n-2$ mà thỏa mãn đk bài toán. Vậy $|S_{n+1}|=|S_{n-2}|+|S_n|$.

Ý tưởng thứ hai là lập một song ánh để cố phá cái điều kiện hơn kém ít nhất 3 đơn vị đi. Bây giờ giả sử một tập hợp thỏa mãn đề bài mà có $i$ phần tử là $a_1<a_2<...<a_i$ khi đấy nếu ta chuyển sang cái tập này ${b_j=2(i-j)+a_j, 1 \le j \le i}$ thì đây là một tập con bình thường của tập $S$ mà trong đó các phần tử của nó đều không nhỏ hơn $2i-1$. Ngược lại từ một tập con của $n$ có $i$ phần tử thỏa mãn $b_1<b_2<..<b_i$ và $b_1 \ge 2i-1$ khi đó lật lại ta có tập ${a_j=b_j-2(i-j), 1 \le j \le i}$ đây là một tập con thỏa mãn đề bài, vậy số tập con có $i$ phần tử thỏa mãn đề bài là ${n-2i+2\choose i}$. Cho $i$ chạy từ $0$ đến $n$ tính ra kết quả.

Kể ra ta thu được một đẳng thức tổ hợp bằng 2 cách đếm.

Hungari 81 : Các ô vuông của bàn cờ kích thước $n\times n$ ( trong đó $n$ là số chẵn lớn hơn 2 ) , được tô bằng $\frac{n^{2}}{2}$ màu sao cho mỗi màu tô đúng 2 ô . Chứng minh rằng trên bàn cờ có thể đặt $n$ con xe sao cho chúng đứng trên các ô vuông có màu khác nhau và chúng không "ăn" được nhau   

Nam Tư 75 : Số lớn nhất các con xe có thể đặt trên bàn có kích thước $3n\times 3n$ có thể là bao nhiêu , để sao cho mỗi con xe chỉ bị "ăn" không nhiều hơn 1 con khác trong số các con xe còn lại

Khi post 2 bài này em đã suy nghĩ chưa, nếu chưa giải ra thì em đã có ý tưởng hướng đi nào mà chưa ra được kq chưa, cùng đưa lên mọi người sẽ thảo luận với em.

Em cứ nghĩ là sẽ tính được để cho thêm thầy Thanh một đẳng thức vào bộ sưu tập chứ

Với $n,m$ là các số nguyên dương, chứng minh đẳng thức sau:

$$\Large \sum_{k=0}^n (-1)^k{m-1\choose k}{m\choose n-k}=(-1)^{\left\lfloor\frac{n}{2}\right\rfloor} {m-1\choose \left\lfloor\frac{n}{2}\right\rfloor}$$

Haha hôm qua em thấy topic của thầy rồi nhưng định bụng để đấy chưa làm để các bạn khác tham gia giải xem nhưng mà thấy thầy nhắc trên stt thôi thì vào hầu chuyện với thầy.

Vốn dĩ về mảng này em chỉ rành có một chiêu, gặp một cao thủ chuyên kĩ thuật biến đổi như thầy Thanh thì dẫu sao dùng một chiêu mà biến hóa đối đáp với thầy vài bài toán kể ra cũng là thành tựu rồi hehe.

Bây giờ ta xét đến vế trái là hệ số tự do của biểu thức:

$$\Large \sum_{k=0}^n (-1)^k{m-1\choose k}\frac{(1+x)^m}{x^{n-k}}$$

Chỗ này hơi khúc mắc là sigma chỉ chạy đến $n$ nó chả ăn nhập gì với cái chỉnh hợp cả, nếu thay $n$ bằng $m-1$ thì đẹp. Chú ý là nếu $k>m-1$ hoặc $k>n$ thì hệ số tự do của ${m-1\choose k}\frac{(1+x)^m}{x^{n-k}}$ dĩ nhiên bằng $0$. Điều này có nghĩa là hoàn toàn thay được $n$ bởi $m-1$ trong dấu sigma kia. Voilà, chìa khóa đây rồi!

Vế trái biểu thức ban đầu bằng hệ số tự do của khai triển:

$$\Large \sum_{k=0}^{m-1} (-1)^k{m-1\choose k}\frac{(1+x)^m}{x^{n-k}}=\frac{(1+x)^m}{x^n}\Large \sum_{k=0}^n (-1)^k{m-1\choose k}x^k=\frac{(1+x)^m(1-x)^{m-1}}{x^n}=\frac{(1+x)(1-x^2)^{m-1}}{x^n}$$

hệ số tự do trong biểu thức này chính là VP.

(Cách khác)

Lời giải :

Ta chọn $n$ như sau :

$$n=2^{p-1}p_2p_3...p_k$$

Trong đó $p$ là số nguyên tố, và $p_2,p_3,...,p_k$ là $k$ số nguyên tố phân biệt lớn hơn $3$.

Hiển nhiên có vô số số $n$ như vậy, và hiển nhiên rằng $\omega (n)=k$.

Ta sẽ chứng minh với cách này thì với mọi cặp $(a,b)$ nguyên dương có tổng bằng $n$ thì ta đều có $d(n)\nmid d(a^2+b^2)$.

Thật vậy, giả sử tồn tại một cặp số nguyên dương $(a,b)$ thoả $a+b=n$ và $d(n)\mid d(a^2+b^2)$.

Dễ thấy $d(n)=2^{k-1}.p$. Suy ra :

$$p\mid d(a^2+b^2)\Rightarrow q^{p-1}\mid a^2+b^2$$

với $q$ là một ước nguyên tố nào đó của $a^2+b^2$. Thế thì :

$$q^{p-1}\leq a^2+b^2< (a+b)^2=4^{p}p_2^2p_3^2...p_k^2$$

Rõ ràng nếu $q<4$ thì với $p$ đủ lớn ta sẽ có $q^{p-1}>4^{p-1}p_2^2p_3^2...p_k^2$. Như vậy $q=2,3$.

Nếu $q=3$ thì suy ra $3\mid a^2+b^2$, suy ra $3\mid a,b$. Kéo theo $3\mid n$.

Dễ thấy điều này mâu thuẫn với cách chọn $n$ như trên.

Vậy phải có $q=2$. Dẫn tới :

$$2^{p-1}\mid a^2+b^2$$

Rõ ràng $a,b$ cùng tính chẵn lẻ, nhưng chúng không thể cùng lẻ vì khi đó $a^2+b^2\equiv 2\pmod 4$, vậy phải có $a,b$ cùng chẵn.

Đặt $a=2^A.x,b=2^B.y$ ($x,y$ lẻ), không giảm tổng quát có thể giả sử $A\geq B$.

Ta có :

$$2^{p-1}\mid 2^{2A}x^2+2^{2B}y^2=2^{2B}(2^{2A-2B}x^2+y^2)$$

Chú ý rằng $2^{2A-2B}x^2+y^2\equiv 1,2,3\pmod 4$. Do đó suy ra :

$$2B+1\geq p-1\Rightarrow A\geq B\geq \dfrac{p-1}{2}$$

Suy ra rằng $2^{(p-1)/2}\mid a,b$

Như vậy ta có thể có được biểu diễn sau :

$$a^2+b^2=2^{p-1}(a_1^2+b_1^2)$$

Do $d(n)$ là hàm nhân tính nên :

$$p\mid d(a^2+b^2)=d(2^{p-1}.(a_1^2+b_1^2))=p+d(a_1^2+b_1^2)\Rightarrow p\mid d(a_1^2+b_1^2)$$

Tương tự trên ta được :

$$2^{\frac{p-1}{2}}\mid a_1,b_1$$

Tiếp tục quá trình này, ta sẽ suy ra :

$$2^{\frac{p-1}{2}.N}\mid a,b$$

Với số nguyên dương $N$ tuỳ ý, rõ ràng điều này là vô lí.

Ta có điều cần chứng minh.

Sorry anh hiểu nhầm là $d(a^2+b^2)|d(n)$ thay vì $d(n)|d(a^2+b^2)$, có thể xử lí đoạn sau phần $2^{p-1}|a^2+b^2$ như thế này:

Nếu $v_2(a)>v_2(b) \Rightarrow p-1=v_2(n)=v_2(a+b)=v_2(b) \Rightarrow v_2(a^2+b^2)=2v_2(b)=2p-2 \Rightarrow p \nmid d(a^2+b^2)$

Nếu $v_2(a)=v_2(b)$ thì có thể thấy $v_2(a+b) \ge v_2(a)+1 \Rightarrow v_2(a) \le p-2$. Ngoài ra dĩ nhiên ta có $v_2(a^2+b^2)=2v_2+1<2p-1$ như vậy để $p|d(a^2+b^2$ ta phải có $2v_2(a)+1=p-1$ điều này mâu thuẫn vì một bên chẵn, một bên lẻ.

Thử xem nếu bài toán này mà thay điều kiện $d(n) \nmid d(a^2+b^2)$ thành $d(n) \nmid d(2a^2+2b^2)$ thì phải xử lí thế nào và liệu bài toán còn đúng không?

Ta thử xem với những giá trị $k$ nào (không nhất thiết tổng quát chỉ cần những ước lượng nào đó với $k$) thì thay điều kiện thành $d(n) \nmid d(a^2+kb^2)$ bài toán vẫn đúng.

Phải nói rằng, bao nhiêu kỹ thuật phân tách, mẹo mực để sáng tạo ra được một bài toán đã bị một chiêu biến hoá kỳ ảo của em giải quyết ngon lành. Chiêu này em học được ở đâu vậy? Có thời gian mong em viết một bài hướng dẫn cách sử dụng và phạm vi ứng dụng của nó được không?

Ngày xưa có một ông anh khóa trên chỉ cho em cái chiêu này và nhất là ông này đc đi IMO về nên trong lúc ôn có nhiều bài tập tính mấy tổng tổ hợp này, trong quá trình giải thì e cũng tìm ra một số kĩ thuật mới kiểu như thay đổi cận của sigma như bài trên. Thầy và các bạn có thể tham khảo về bài viết về hàm sinh trong tài liệu này (chuyên đề tổ hợp của MS):

 http://diendantoanho...-của-mathscope/

Thực ra nó còn một kĩ thuật nữa mà trong tài liệu có đề cập là giả sử với một tổng tổ hợp có một thành phần cố định là $m$ chẳng hạn (vd như $m$ hoặc $n$ ở bài trên) thì ta gắn thêm cho biểu thức một đại lượng $x^m$ sau đó cho $m$ chạy từ $0$ đến $\infty$ sẽ được một hàm sinh, dùng chuyển dấu sigma sẽ linh hoạt trong biến đổi hơn và có một số kĩ thuật nhỏ khác trong quá trình xử lí.

Thực tế thì ngày xưa lúc đấy chỉ chăm chăm vào giải toán nên kĩ thuật mới nghĩ ra cũng chỉ nhất thời để giải quyết bài toán đang làm chứ không chiêm nghiệm, phát triển nó thêm còn giờ thì không còn đủ hăng say để tiếp tục nữa và cũng quên nhiều rồi. Hehe thầy Thanh nếu có thể thì tham khảo và nghiên cứu đưa ra cái gì mới xem, em giờ k thể miệt mài ngồi tìm tòi đc nữa  

Nhận xét một chút về tài liệu trên thì nếu bạn nào mới học hoặc cần học kĩ năng có thể đem nó ra tham khảo. Tuy nhiên khi viết một cái gì đấy thì không nên học tập mấy ông này, đại đa số là đem dịch từ tài liệu tiếng Anh sang và gần như chả có cái gì mới do công sức tìm tòi họ bỏ ra cả. Thậm chí bài viết của em trong đấy nó cũng như vậy, chỉ toàn lời giải cho bài toán và lời giải cho bài toán rất giống phong cách post bài của em từ xưa đến giờ ở diễn đàn. Nó chẳng có một chút ý nghĩa gì cả!

Tìm mọi số nguyên dương $a,b,c$ thỏa mãn : $ab-c$ ; $bc-a$ ; $ca-b$ đều là lũy thừa của 2 . 

 

NX : Mình lấy lại bài số học của IMO 2015 vừa qua để các trao đổi kĩ càng hơn về việc phân tích hướng giải , chỉ ra đâu là mấu chốt của bài  ,.... chứ không nên đùng đùng xét một loạt các TH mà không chú thích tại sao . Mong các bạn không nên dẫn link trong bài viết này để tiện theo dõi .  

Nhìn vào theo cảm nhận mang tính cá nhân của mình thì thứ làm cho nó có hữu hạn nghiệm có thể khai thác được là sự lệch bậc trong biểu thức, vì nó đối xứng nên ta ta có thể dựa vào $v_2$ của tích 2 số phải lớn hơn $v_2$ của một số, rõ ràng nếu xem 3 số là như nhau thì để tạo ra lũy thừa của một số nguyên tố, đây là một điểm ta cảm thấy bất cập, đó chính là thứ cần vin vào để lập luận. Để đảm bảo cho mục đích vừa nêu ta chọn $a$ là số có $v_2$ lớn nhất.

Khi đó ta chứng minh được nếu $v_2(a)>v_2(b)$ và $v_2(a)>v_2(c)$ là vô lí.

Thật vậy đặt $a=2^i.a_1,b=2^j.b_1,c=2^k.c_1$

Nếu $i>j,i>k$ thì từ $ab-c,ac-b$ đều là lũy thừa của $2$ ta suy ra $2^{i-k}.2^j.b_1-c_1=1$ và $2^{i-j}.2^k.c_1-b_1=1$

Suy ra $1 \ge 2.b_1-c_1$ và $1 \ge 2.c_1-b_1$. Cái này chỉ xảy ra khi $b_1=c_1=1,j=k=0,i=1$, nghiệm này không phù hợp.

Vậy trong 2 số $i,j,k$ có ít nhất 2 số bằng nhau. Ta giả sử là $i=j$ khi đó ta có:

$ca-b,cb-a$ là lũy thừa của 2.

_Nếu $c$ là số chẵn thì suy ra $ca_1-b_1=1,cb_1-a_1=1$, chú ý lúc này $v_2(c)>v_2(a_1),v_2(c)>v_2(b_1)$ nên theo trên ta suy ra nghiệm $c=2,a_1=b_1=1$

Thay vào để $ab-c$ là lũy thừa của $2$ thì suy ra $i=1$ nên $(2;2;2)$ là một nghiệm.

_Bây giờ xét $c$ là một số lẻ.

Ở đây sinh ra 2 vấn đề là nếu $a,b$ lẻ thì chưa nói được gì nhưng mà nếu $a,b$ chẵn thì ta có $ab-c=1$

+)Ta xét $a,b$ chẵn trước thì khi đó $c=2^{2i}a_1b_1-1$ (vì $i=j \ge 1$) và ta phải có $x=2^{2i}a_1^2b_1-a_1-b_1$ và $y=2^{2i}a_1b_1^2-a_1-b_1$ đều là các lũy thừa của 2. Nếu 2 số này bằng nhau thì $a_1=b_1$ thay vào có thể giải ra nghiệm $(2;2;3)$

Nếu 2 số này khác nhau thì $v_2(x) \ne v_2(y)$ nên $v_2(x+y)=v_2(x-y)$ suy ra $v_2(a_1+b_1)+1=v_2(a_1-b_1)+2i \Rightarrow v_2(a_1+b_1)=v_2(a_1-b_1)-1+2i \ge 2i$

Nếu $v_2(a_1+b_1)>2i$ thì ta có thể chứng minh được $x,y$ đều là lũy thừa của 2 là mâu thuẫn (cái này chắc không khó, nhưng mình nhác mò chứng minh )

Từ đó suy ra $v_2(a_1+b_1)=2i$ và $v_2(a_1-b_1)=1$

Đặt tiếp $a_1+b_1=2^i.r$ với $r$ lẻ và $z=a_1^2b_1-r,t=a_1b_1^2-r$ thì $z,t$ là lũy thừa của 2 mà $v_2(z-t)=v_2(a-b)=1$ suy ra một trong 2 số $z,t$ bằng 2.

Không mất tính tổng quát giả sử là $z=2$, nếu $a_1 \ge 2$ thì $a_1^2b_1-r \ge (a_1-1)a_1b_1+a_1b_1-r>2$ chú ý là $r \le \frac{1}{4}(a_1+b_1)$ nên $a_1b_1-r>0$.

Vậy $a_1=1$ suy ra $b_1=r+2$, ta có $2^{2i}r=a_1+b_1=r+3$ mà $i \ge 1$ nên suy ra luôn $r=1$. Từ đây suy ra được giá trị của $a,b,c$ ta được bộ nghiệm $(2,6,11)$

+) Bây giờ xét $a,b,c$ cùng lẻ

Thủ thuật cũng gần tương tự như trên một chút, nhưng trước tiên ta nhận xét là 3 số này không có 2 số nào bằng nhau và không có số nào bằng 1. Ngược lại nếu tồn tại thì dễ dàng chứng minh vô lí.

Với điều kiện trên không mất tính tổng quát $a>b>c$, khi đó ta có $ab-c>ac-b$, do đó $v_2(ac-b)=v_2[(ab-c)-(ac-b)]=v_2[(ab-c)+(ac-b)] $. Suy ra $v_2(ac-b)=v_2(a+1)+v_2(b-c)=v_2(a-1)+v_2(c+b)$, ta chú ý là trong 2 số $v_2(a-1)$ và $v_2(a+1)$ có một số bằng 1. Do đó hoặc là $v_2(b-c)=v_2(ac-b)-1$ hoặc là $v_2(b+c)=v_2(ac-b)-1$. Chung quy ta đều có $2(b+c) \ge ac-b$ vì $ac-b=2^{v_2(ac-b)}$, suy ra $3b \ge (a-2)c$, mà $a,b,c$ đều lẻ lớn hơn 1 và $a>b>c$ nên $a-2 \ge b, c \ge 3$. Đẳng thức trên phải xảy ra và xảy ra khi $a=b+2,c=3$

Ta có $ab-c=b(b+2)-3=(b-1)(b+3)$ là lũy thừa của 2 suy ra $b-1$ và $b+3$ đều là lũy thừa của 2 suy ra $b=5$.

Từ đây dẫn đến bộ nghiệm $(3,5,7)$

P/s: Mình không giỏi trình bày nên khá khó nhìn. Bài này không khó, và so với một bài số 5 trong kì thi IMO thì nó được xem là dễ.

xin được phân tích và giải bài tóan số 1:

Khi nhìn số 2015, chắc nhiều bạn cũng đóan nhận được là có thể giải bài tóan trong trường hợp tổng quát. Vì vậy khi nếu chúng ta xử lý được bài tóan tổng quát thì sẽ xử lý được với bất kỳ con số nào, có thể là 2015,2016,...

Bài tóan tổng quát:

Chứng minh tồn tại vô hạn số tự nhiên của dãy FIbonacci chia hết cho $n$

Xét các cặp số dư khi chia 2 số hạng liên tiếp trong dãy Fibonacci theo modulo $n$ $(F_0,F_1);(F_1,F_2);...;$

Vì dãy Fibonacci là vô hạn mà chỉ có $n^2$ khả năng cho mỗi cặp số dư theo modulo $n$ nên tồn tại $(F_i,F_{i+1})$ sao cho $F_i\equiv F_{i+m};F_{i+1}\equiv F_{i+m+1}$ ( mod $n$ ) với $m\in \mathbb{Z^+}$

Xét $i> 1$ ta có: $F_{i-1}=F_{i+1}-F_i\equiv F_{i+m+1}-F_{i+m}=F_{i+m-1}$ ( mod $n$ )

Quá trình cứ tiếp diễn dẫn đến $F_j\equiv F_{j+m}$ ( mod $n$ ) $\forall j\geq 0$

Suy ra $0\equiv F_0\equiv F_m\equiv ...$ ( mod $n$ ), tức là có vô hạn các số $F_{km}$ thỏa mãn yêu cầu bài tóan

DPCM

Sau bài toán này em liên hệ được điều gì?

Về cơ bản là nhờ $F_0=0$ nên bài toán đúng với mọi $n$. Nhưng đâu chỉ dãy dirichlet mới có $F_0$ bằng 0. Kết hợp với đl 2 ở trên có thể suy ra nếu mà $u_0=0$ với mọi dãy số truy hồi $u_n$ thì dãy tồn tại vô số số chia hết cho $n$. Nhưng $u_0$ nó rõ ràng quá giả dụ ta cho $u_1=-2,u_2=5,u_3=4$ sau đấy thiết lập một công thức truy hồi $u_{n+3}=au_{n+2}+bu_{n+1}+cu_n$ ta thiết kế $a,b,c$ sao cho tính toán một chút được $u_5=0$ chẳng hạn, như vậy ta sẽ thu được một bài toán cho  $u_1=-2,u_2=5,u_3=4$ và $u_{n+3}=au_{n+2}+bu_{n+1}+cu_n$ cmr có vô hạn số hạng của dãy chia hết cho $n$ hoặc người ta muốn đánh lạc hướng hơn tí thì bảo là chia hết cho mọi số nguyên tố $p$. Muốn nó lắt léo hơn một chút thì thông thường chúng ta quan niệm một cách đơn thuần một dãy số $u_n$ thường bắt đầu từ $u_0$ hoặc $u_1$ rồi đi dần lên, nhưng khái niệm "tuần hoàn số dư" làm ta nghĩ đến dãy số này như một vòng tròn nó sẽ quay đêu và lặp lại, mà vòng tròn k có điểm bắt đầu, thế thì trước $u_0$ vẫn có thể có $u_{-1},u_{-2}$ chẳng sao cả. Vậy giờ ta tìm $a,b,c$ sao cho nếu mà tính ngược về $u_{-2}=0$ chẳng hạn thì lại ra một bài toán mới!

Muốn màu mè thêm một chút thì bài này ta dễ dàng thấy $u_n$ là số nguyên thì giờ thêm hệ số vào  $t.u_{n+3}=au_{n+2}+bu_{n+1}+cu_n$ thiết kế các hệ số sao cho dãy này lúc nào cũng nguyên thế là lại ra một bài toán mới!

Hoặc đặt ra giả dụ một dãy dạng $u_{n+1}=au_n+bu_{n-1}^2$ chẳng hạn thì nó có tuần hoàn số dư không?.....Chẳng bao giờ thiếu cách để đặt ra vấn đề.

Có quá nhiều cách để phát triển lên từ một ý tưởng ta cảm thấy thú vị! Vấn đề là phải đánh bật tư duy của mình ra ngoài những khuôn phép, ngoài những định kiến vốn cho là quen thuộc. Từ đây bạn có thể tạo ra một lớp các vấn đề rồi theo dạng toán này rồi! Thử bắt tay vào những ý tưởng nêu trên xem thế nào?

Tìm tất cả các hàm số $f:\mathbb{R}\rightarrow \mathbb{R}$ và thoả mãn :

$$f(y+f(x))=f(x)f(y)+f(f(x))+f(y)-xy,\;\forall x,y\in \mathbb{R}$$

Có thể dùng thêm một biến $z$ để linh hoạt hơn,

ta khai triển:

$$f(z+f(y)+f(x))=f(x)f(z+f(y))+f(f(x))+f(z+f(y))-x(z+f(y))=f(x)(f(z)f(y)+f(f(y))+f(z)-zy)+f(f(x))+f(z)f(y)+f(f(y))+f(z)-yz-xz-xf(y)$$

Viết lại thế này cho rõ ràng hơn một chút:

$$f(z+f(y)+f(x))=f(x)f(y)f(z)+(f(f(x))+f(f(y)))+f(z)(f(x)+f(y))+f(z)-z(x+y)+f(x)f(f(y))-zyf(x)-xf(y)$$

Phần đầu mình đã viết ra những hạng tử nhóm lại mà $x$ và $y$ vai trò là như nhau, đổi vai trò $x$ và $y$ ta thu được:

$$ f(x)f(f(y))-zyf(x)-xf(y) = f(y)f(f(x))-zxf(y)-yf(x)$$

Bây giờ xét đến số 0 trước, thì không khó để chứng minh được $f(x)=0$ khi và chỉ khi $x=0$

Giờ xét $x,y$ đều khác 0.

Cho $z=0 \Rightarrow \frac{f(f(x))+x}{f(x)} = const$, cho $z=1 \Rightarrow \frac{f(f(x))}{f(x)} = const$

Vậy $\frac{f(x)}{x} =k$ là hằng số.

Thay vào thì được $k=1$ hoặc $k=-1$