HeilHitler

Cho đa thức $P(x)= \prod_{i=1}^{n}( x- a_i)$ với $n \ge 5$ và các $a_i \in \mathbb{Z}$ phân biệt. Chứng minh nếu tam thức $ a x^2 + bx +1$ bất khả quy trên $\mathbb{Z[x]}$ thì đa thức $ a P(x)^2 + b P(x) +1$ cũng bất khả quy trên $\mathbb{Z[x]}$

Dập cái bổ đề này vào là ngon (cũng tương đối lắt léo về mặt lý luận):
$A(x)$ là một đa thức bậc $k$ và $n$ số nguyên $a_i$ ($k<n, n \geq 5$) thõa mãn $A(a_i)$ chỉ nhận các giá trị trong tập {$1,-1$}. Khi đó bắt buộc $A$ phải là đa thức hằng, và $A(x)=1$ hoặc $A(x)=-1$.
Dập vào:
Giả sử bài toán sai, tức là tồn tại $M,N \in Z_{[x]}$ và khác hằng để:
$aP^2(x)+bP(x)+c=M(x).N(x) \Rightarrow M(a_i)N(a_i)=1 \Rightarrow$ $M(a_i), N(a_i)$ chỉ nhận các giá trị trong tập {$1,-1$}.
Nếu một trong hai thím $M,N$ có bậc nhỏ hơn $n$ thì theo bổ đề, thím đó phải bằng hằng số (mâu thuẫn với giả thuyết khả quy). Thành thử $degM=degN=n$.
Cứ gọi hệ số cao nhất của thím $M$ là $m$ đi, xét: $M(x)=m \prod (x-a_i)+M'(x)$, rõ ràng thím $M'$ có bậc nhỏ hơn $n$ và $M'(a_i)$ chỉ nhận giá trị trong tập {$1,-1$} $\Rightarrow M(x)=m \prod (x-a_i)+1$ (hoặc $M(x)=m \prod (x-a_i)-1$, tuy nhiên trường hợp này cũng thực hiện tương tự).
Tương tự $N(x)=n \prod (x-a_i)+1$.
Suy ra: $aP^2(x)+bP(x)+c=[mP(x)+1][nP(x)+1] \Rightarrow ax^2+bx+1=(mx+1)(nx+1)$ (mâu thuẫn giả thuyết bất khả quy). Vậy bài toán được chứng minh theo nguyên lý phản chứng.

Giả sử phương trình :
$\text{P(x)} = \text{x}^{\text{n}} + \text{a}_{\text{n} - 1}\text{x}^{\text{n} - 1} + ... + \text{a}_{1}\text{x} + 1 = 0$ có $\text{n}$ nghiệm thực.
Cho biết $\text{a}^{\text{k}} \geqslant 0$ $\forall \text{k} = 1, 2, 3,..., \text{n} - 1$.
Chứng minh rằng :
$\text{P(2)} \geqslant 3^{\text{n}}$.

Do các $a_k \geq 0$ nên tất cả các nghiệm của $P(x)$ phải âm. Với mỗi nghiệm $a_i$, ta đặt $b_i=-a_i$ để chuyển thành $b_i>0$. Theo Viet $\prod b_i=1$.
Lại thấy:
$P(2)=\prod (2+b_i)=\prod (1+1+b_i) \geq \prod (3 \sqrt[3]{b_i})$
Cho nên $P(2) \geq 3^n$.

Cho $a, b, c, d \in \mathbb{R}^{+}$ và $\sum \frac{1}{1 + a} \geqslant 3$.
Chứng minh rằng :
$abcd \leqslant \frac{1}{81}$.

Từ giả thiết, ta đưa 3 phần tử sang trái và áp dụng Cosi để thu được:
$\frac{1}{a+1} \geq \frac{b}{b+1}+\frac{c}{c+1}+\frac{d}{d+1} \geq 3 \sqrt[3]{\frac{bcd}{(b+1)(c+1)(d+1)}}$
Tương tự với các cái còn lại:
$\frac{1}{b+1} \geq 3 \sqrt[3]{\frac{acd}{(a+1)(c+1)(d+1)}}$
$\frac{1}{c+1} \geq 3 \sqrt[3]{\frac{abd}{(a+1)(b+1)(d+1)}}$
$\frac{1}{d+1} \geq 3 \sqrt[3]{\frac{acb}{(a+1)(c+1)(b+1)}}$
Nhân dọc cả 4 bất đẳng thức để có điều phải chứng minh.

Tìm phần nguyên của số :
$\text{S}_{n} = \sqrt{2} + \sqrt[3]{\frac{3}{2}} + \sqrt[4]{\frac{4}{3}} + ... + \sqrt[n + 1]{\frac{n + 1}{n}}$.

Đánh giá bằng Cosi cho mỗi phần tử: $1<\sqrt[k + 1]{\frac{k + 1}{k}}<1+\frac{1}{k(k+1)}$
Thế nên $n<S_n<n+1-\frac{1}{n+1} \Rightarrow [S_n]=n$.

[/color]

Chỗ này : "Ma trận X giao hoán với A khi và chỉ khi X lần lượt giao hoán với $A_{1},A_{2},A_{3}$" tức

$$A_1X+A_2X+A_3X=XA_1+XA_2+XA_3 $$
$$\Leftrightarrow \begin{cases} A_1X=XA_1 \\ A_2X=XA_2 \\ A_3X=XA_3 \end{cases}$$

Nói chung là không đúng với ma trận bất kỳ nên cần phải CM anh !

Thực ra chỉ cần xét ma trận $B=A-2I$ để có $BX=XB$. Ở đây có thể thấy ma trận $-BX$ là ma trận thu được bằng cách tịnh tiến tất cả các dòng của $X$ lên phía trên 1 đơn vị, và dòng cuối chuyển thành 0. Còn ma trận $-XB$ là ma trận thu đuợc bằng cách tịnh tiến tất cả các các cột của $X$ sang phía phải 1 đơn vị, và chuyển tất cả các cột đầu thành 0. Thành thử việc quy về đẳng thức $BX=XB$ có thể dễ dàng tìm ra $X$.
Cụ thể, đặt $X=\begin{bmatrix} a & b & c & d\\ e & f & g & h\\ i & j & k & l\\ m & n & p & q \end{bmatrix}$ thì:
$\begin{bmatrix} e & f & g & h\\ i & j & k & l\\ m & n & p & q\\ 0 & 0 & 0 & 0 \end{bmatrix}=\begin{bmatrix} 0 & a & b & c\\ 0 & e & f & g\\ 0 & i & j & k\\ 0 & m & n & p \end{bmatrix}$
Dẫn đến:
$X=\begin{bmatrix} a & b & c & d\\ 0 & a & b & c\\ 0 & 0 & a & b\\ 0 & 0 & 0 & a \end{bmatrix}$

Bài toán: Cho $r,t,s \in \mathbb{Z}$ thỏa mãn:$r;s \ge 0;t \ge r+s$.Chứng minh đẳng thức sau:
$$\sum_{k=0}^{s}\frac{\binom{s}{k}}{\binom{t}{r+k}}=\frac{t+1}{\binom{t-s}{r}.(t+1-s)}$$

Hôm đi học môn Quản trị chiến lược, ngồi trong lớp chán quá ngồi nghĩ vu vơ tự dưng nghĩ ra bài này mới hay chứ.
Solution
Mình xin được dùng ký hiệu $C^{k}_{s}$ để tránh việc dùng quá nhiều dấu ngoặc.
Ký hiệu $W(s,r,t)=\sum_{k=0}^{s} \frac{C^{k}_{s}}{C^{r+k}_{t}}$.
Ta để ý phép nhóm khá đẹp mắt:
$W(s,r,t)=\sum_{k=0}^{s-1} [C^{k}_{s-1}(\frac{1}{C^{r+k}_{t}}+\frac{1}{C^{r+k+1}_{t}})]$
$\Leftrightarrow W(s,r,t)=(\frac{t+1}{t})(\sum_{k=0}^{s-1} \frac{C^{k}_{s-1}}{C^{r+k}_{t-1}})$
$\Leftrightarrow W(s,r,t)=\frac{t+1}{t} W(s-1,r,t-1)$
Như vậy ta đã thu được công thức truy hồi cho $W(s,r,t)$. Dựa vào truy hồi ta thấy ngay $W(s,r,t)=\frac{t+1}{t+1-s}W(0,r,t-s)$. (đpcm)
Comment
Hôm Trungpbc nói rằng "nhiều công thức Tổ hợp sẽ có thể giải quyết bằng nội suy Lagrange" làm mình rất phấn khích, vì đây cũng là ý tưởng mình đã từng suy nghĩ từ rất lâu (cụ thể làm từ ĐH năm 1). Hôm qua lục lại đống sổ tay từ hồi cấp 3 thì mình tìm thấy một bổ đề rất đẹp http://diendantoanho...83933-tinh-f-1/, đây là bài toán của thầy Hà Duy Hưng ra cho mình hồi năm lớp 11 (nhưng đáng tiếc mình đã quên mất lời giải ). Và từ bổ đề khá đẹp này, mình nảy ra ý tưởng giải quyết bài toán này bằng nội suy Lagarange theo đúng tư tưởng của Trungpbc.
Thật vậy, xét đa thức bậc $s$ thõa mãn $f(i)=\frac{(-1)^i}{C^{r+i}_{t}}$ (*) với mọi $i=0,1,....,s$.
Khai triển nội suy Lagrange đa thức này tại $s+1$ nút $0,1,2,....,s$ thì ta thu được:
$f(x)=\sum_{i=0}^{s} \frac{\prod_{j \neq i} (x-j)}{\prod_{j \neq i} (i-j)} f(i)$
Nếu gọi $a_s$ là hệ số cao nhất của $f(x)$ thì khi đồng nhất hệ số ta thu được:
$\sum_{i=0}^{s} \frac{f(i)}{\prod_{j \neq i} (i-j)}=a_n$
$\Leftrightarrow \sum_{i=0}^{s} \frac{(-1)^s C^{i}_{s}}{s!.C^{r+i}_{t}}=a_n$ (1)
Quay trở lại với $f(x)$, từ giả thiết (*) ta suy ra $(t-r-i).f(i+1)+f(i).(r+i+1)=0$ với mọi $i=0,...,s-1$ (**)
Đặt $g(x)=(t-r-x).f(x+1)+f(x).(r+x+1)$ thì dễ thấy $deg=s$ và có $s$ nghiệm (Theo (**)) cho nên ta đồng nhất:
$g(x)=(t-r-x).f(x+1)+f(x).(r+x+1)=A.\prod_{i=0}^{s-1}(x-i)$ với $A \in R$. (***)
Đồng nhất hệ số cao nhất ở đẳng thức (***) ta rút ra $A=a_n(t+1-s)$ (2) và nên nhớ rằng $A=\frac{g(-1)}{(-1)^s.s!}=\frac{(t-r+1)f(0)+rf(-1)}{(-1)^ss!} \Rightarrow A=\frac{(-1)^s(t+1)}{s!C^{r}_{t-s}}$ (3).
Gộp (1), (2) và (3) để thu được đẳng thức cần tìm.
PS: Chả hiểu sao gõ công thức ở diễn đàn ta khá khó khăn, nhiều công thức gõ đúng mà F5 nó chả chịu hiện ra gì cả. @_@

Problem: Cho $m,n,p \in N^*$ và $m+n \leq p$. Xét đa thức bậc $m$ thõa mãn $f(i)=\frac{(-1)^i}{C^{n+i}_{p}}$ với mọi $i=0,1,....,m$. Chứng minh rằng:
$nf(-1)=\frac{p+1}{C^{n}_{p-m}}-\frac{p-n+1}{C^{n}_{p}}$.

Định lý URF ? Bạn có thể giải thích rõ hơn về định lý này không ?

À cái này mình học từ hồi cấp 3, thầy giáo gọi nó là định lý URF chứ cũng chả biết URF là viết tắt của cái gì cả.
Mình thấy thầy bảo thế này:
Xét đa thức $f(x)=a_n x^n+a_{n-1} x^{n-1}+...+a_1 x+a_0$
Và số $M=cos \frac{2 \pi}{m}+i sin \frac{2 \pi}{m}$ là căn bậc $m$ của đơn vị.
Khi đó để ý rằng tổng $1+M^k+M^{2k}+...+M^{(m-1)k}$ sẽ bằng $0$ nếu $k$ không chia hết cho $m$,và bằng $m$ nếu $k$ chia hết cho $m$.
Áp dụng tính chất này vào đa thức, khi đó ở tổng $f(1)+f(M)+f(M^2)+...+f(M^{m-1})$, tất cả các mũ dạng $x^k$ mà $k$ không chia hết cho $m$ sẽ bị triệt tiêu hết, thành thử:
$f(1)+f(M)+f(M^2)+...+f(M^{m-1})=m(\sum a_i)$ (Ở đó $i$ là các bội của $m$).

Chứng minh đẳng thức sau với $n$ là số nguyên dương

$S=\sum_{k=0}^n \left[\sum_{j=0}^k \binom{n}{j}\right]^2=(n+2)2^{2n-1}-\dfrac{n}{2}\binom{2n}{n}$

Không gì khó chịu hơn việc khi gặp một bài toán khó mà trong đầu chỉ có mỗi ý tưởng biến đổi tương đương.
Vế trái tương đương với:
$\sum_{k=0}^n \left[\sum_{j=0}^k \binom{n}{j}\right]^2=[\sum_{i=0}^n \binom{n}{i}][\sum_{i=0}^n (i+1).\binom{n}{i}]-\sum_{i>j}[(i-j).\binom{n}{i}.\binom{n}{j}]$
Rõ ràng dễ thấy ngay $\sum_{i=0}^n \binom{n}{i}=2^n$ và $\sum_{i=0}^n (i+1).\binom{n}{i}=2^n+n2^{n-1}$. Thành thử bài toán quy về việc chứng minh:
$\sum_{i>j}[(i-j).\binom{n}{i}.\binom{n}{j}]=\dfrac{n}{2}\binom{2n}{n}$ (*)
Thật đáng tiếc đẳng thức (*) đã được các bác chứng minh ở http://diendantoanho...racn2binom2nn/. Như vậy bài toán đã được giải quyết.

Bài toán: Một câu lạc bộ bơi lội có n thành viên tổ chức 4 cuộc bơi lội và $F_1$, $F_2$, $F_3$, $F_4$ là các đội tham gia vào các cuộc bơi lội ấy. Hỏi có bao nhiêu cách chia các đội sao cho $F_{1}\cap F_{2}\neq\varnothing$, $F_{2}\cap F_{3}\neq\varnothing$, $F_{3}\cap F_{4}\neq\varnothing$.

Hoặc là:
Đặt $M=F_1 \cap F_3; N= F_3 \cap F_2; P=F_2 \cap F_4; H_1=F_1\M; H_2=M; H_3=F_3\(M \cup N); H_4=N; H_5=F_2\(N \cup P); H_6=P; H_7=F_4\P$.
Khi đó thấy ngay:
$|H_1|+|H_2|+|H_3|+|H_4|+|H_5|+|H_6|+|H_7|=n$
Bài toán quy về việc đếm số cách chia $n$ cái kẹo cho 7 em bé.
+Nếu các chiếc kẹo là phân biệt thì có $7^n$ cách.
+Nếu số kẹo là không phân biệt thì có $C^{6}_{n+6}$ cách.

Dạo này box tổ hợp và rời rạc của VMF có vẻ trầm lắng!
Để tránh tình trạng này kéo dài, tôi xin khuấy động bằng một bài nho nhỏ

Cho số nguyên $n\ge 3$. Chứng minh đẳng thức:

$\sum_{k=0}^{\left\lfloor\frac{n}{3}\right\rfloor} \binom{n}{3k} = \dfrac{2^n+(-1)^n\left(3\left\lfloor\frac{n}{3}\right\rfloor-3\left\lfloor\frac{n-1}{3}\right\rfloor-1\right)}{3}$

Đặt $f(x)=(1+x)^n$ và $a=cos \frac{2 \pi}{3}+i .sin \frac{2 \pi}{3}$
Áp dụng trực tiếp định lý URF để thu được:
$\sum_{k=0}^{\left\lfloor\frac{n}{3}\right\rfloor} \binom{n}{3k}=\frac{f(1)+f(a)+f(a^2)}{3}$. (đpcm)

Việt Dũng có 2 hàng cây giống nhau cần được trồng đối diện nhau. Mỗi hàng cây đều gồm có 10 cây táo, 9 cây xoài, 8 cây mận và 7 cây mít. Một cách trồng gọi là "hợp phong thủy" nếu 2 cây khác hàng, đối diện nhau thì luôn luôn khác loại. Đếm số cách trồng "hợp phong thủy" mà Việt Dũng có thể triển khai.

Xét tập A có m phần tử.
+Số cách chọn ra $n$ phần tử từ tập $A$ (tính cả lặp) là $m^n$.
+Với mọi bộ $(k_1,k_2,...,k_m)$ mà $k_1+k_2+....+k_m=n$. Số cách chọn $n$ phần tử từ $A$ mà phần tử thứ $i$ trong $A$ bị lặp đúng $k_i$ lần là: $\frac{n!}{k_1!.k_2!....k_m!}$.
Rõ ràng cả 2 đều là số cách chọn ra $n$ phần tử từ tập $A$. Cho nên:
$\sum \frac{n!}{k_1!.k_2!....k_m!}=m^n$. (đpcm)