nhungvienkimcuong

Cho một bộ bài gồm 52 quân bài bình thường, gồm các quân Át, 2, 3,..., J, Q, K và 4 chất Bích, Nhép, Rô, Cơ. Bạn Hiền chia bộ bài thành 13 bộ 4 con một cách ngẫu nhiên. Chứng minh rằng Hiền có thể sắp xếp lại 13 bộ của mình sao cho bộ thứ nhất chứa con Át, bộ thứ 2 chứa con 2, bộ thứ 3 chưa con 3,...v...v..., bộ cuối cùng chứa con K.

cứ $\text{Hall}$ mà lần thôi anh nhỉ =))

ta quy định $\text{Át,J,Q,K}$ lần lượt là các số $1,11,12,13$ nên ta có tổng cộng $13$ số khác nhau và mỗi số xuất hiện $4$ lần trong tổng cộng $52$ số

ta gọi $13$ bộ lần lượt là $\mathcal{A}_1,\mathcal{A}_2,...,\mathcal{A}_{13}$ với $\left | \mathcal{A}_i \right |=4,i=\overline{1,13}$

theo đề bài ta chỉ cần chứng minh $\exists a_1,a_2,..,a_{13}$ tương ứng thuộc $\mathcal{A}_1,\mathcal{A}_2,...,\mathcal{A}_{13}$ sao cho $a_i\neq a_j,i\neq j$

theo định lý $\text{Hall}$ thì ta chỉ cần chứng minh

$\left | \mathcal{A}_{i_1}\cup \mathcal{A}_{i_2}\cup ...\cup \mathcal{A}_{i_k} \right |\ge k,\ \ \forall k\le 13$

với tập $\mathcal{A}=\mathcal{A}_{i_1}\cup \mathcal{A}_{i_2}\cup ...\cup \mathcal{A}_{i_k}$ có tổng cộng $4k$ số (ở đây chưa trừ đi các số bị lặp)

mà mỗi số xuất hiện nhiều nhất trong $4$ tập nên

$\left | \mathcal{A} \right |\ge \frac{4k}{4}=k$

do đó ta có $\text{Q.E.D}$

Cho một bộ bài gồm 52 quân bài bình thường, gồm các quân Át, 2, 3,..., J, Q, K và 4 chất Bích, Nhép, Rô, Cơ. Bạn Hiền chia bộ bài thành 13 bộ 4 con một cách ngẫu nhiên. Chứng minh rằng Hiền có thể sắp xếp lại 13 bộ của mình sao cho bộ thứ nhất chứa con Át, bộ thứ 2 chứa con 2, bộ thứ 3 chưa con 3,...v...v..., bộ cuối cùng chứa con K.

ý bài toán cách sắp xếp ở đây là như thế nào vậy anh 

Bài toán :
Cho $a_i\ge 1; i=1,2,...,n$
Chứng minh rằng :
$$\prod_{i=1}^{n} \left (a_i+1\right ) \ge \dfrac{2^n}{n+1}\left [\left (\sum_{i=1}^{n} a_i\right ) +1\right ]$$

cứ thấy $n$ mà quy nạp thôi nào 

ta gọi $\mathcal{P}(n)$ là mệnh đề với bất kì $n$ số $a_i\ge 1; i=1,2,...,n$ thì

$\prod_{i=1}^{n} \left (a_i+1\right ) \ge \dfrac{2^n}{n+1}\left ( \sum_{i=1}^{n}a_i+1 \right )$

$\bullet$ dễ dàng chứng minh $\mathcal{P}(1)$ đúng

$\bullet$ với $n\ge 2:$ giả sử $\mathcal{P}(k)$ đúng $\forall k\le n$

$\bullet$ ta chứng minh $\mathcal{P}(n+1)$ đúng

thật vậy với $n+1$ số $a_i\ge 1,i=\overline{1,n+1}$ ta hoàn toàn có thể giả sử $a_{n+1}=\max\left \{ a_i\mid i=\overline{1,n+1} \right \}$

ta cần chứng minh

$\prod_{i=1}^{n+1} \left (a_i+1\right ) \ge \dfrac{2^{n+1}}{n+2}\left ( \sum_{i=1}^{n+1}a_i+1 \right )$

mà với $n$ số $a_i,i=\overline{1,n}$ thì theo $\mathcal{P}(n)$ ta có

$\prod_{i=1}^{n} \left (a_i+1\right ) \ge \dfrac{2^n}{n+1}\left ( \sum_{i=1}^{n}a_i+1 \right )$

do đó ta chỉ cần chứng minh

$\frac{2^n}{n+1}\left ( \sum_{i=1}^{n}a_i+1 \right )\left ( a_{n+1}+1 \right )\ge \frac{2^{n+1}}{n+2}\left ( \sum_{i=1}^{n+1}a_i+1 \right )$

$\Leftrightarrow \left ( 1-\frac{2(n+1)}{(n+2)\left ( \sum_{i=1}^{n}a_i+1 \right )} \right )a_{n+1}\ge \frac{n}{n+2}$

mà ta lại có $a_{n+1}=\max\left \{ a_i\mid i=\overline{1,n+1} \right \}$ nên

$\Rightarrow a_{n+1}\ge \frac{\sum_{i=1}^{n}a_i}{n}=\frac{\mathcal{A}}{n}$

do đó ta chỉ cần chứng minh

$\left ( 1-\frac{2n+2}{(n+2)\left ( \mathcal{A}+1 \right )} \right ).\frac{\mathcal{A}}{n}\ge \frac{n}{n+2}$

$\Leftrightarrow (n+2)\mathcal{A}^2-(n^2+n)\mathcal{A}-n^2\ge 0$

điều trên luôn đúng bởi vì để ý $\mathcal{A}\ge n$ thì ta được

$(n+2)\mathcal{A}^2-(n^2+n)\mathcal{A}-n^2\ge (n+2)n.\mathcal{A}-(n^2+n)\mathcal{A}-n^2=n\mathcal{A}-n^2\ge 0$

do đó $\mathcal{P}(n+1)$ được chứng minh nên theo quy nạp ta có $\text{Q.E.D}$

Cho p là số nguyên tố. Chứng minh rằng tồn tại số nguyên tố q sao cho với mọi n nguyên dương, 

   $n^p-p$ không chia hết cho q

Bài toán mạnh hơn. Chứng minh tồn tại vô hạn số nguyên tố $q$ thỏa mãn.

chứng minh tồn tại vô hạn ý tưởng thì cũng giống chứng minh tồn tại thôi =))

giả sử tồn tại hữu hạn số nguyên tố thỏa đề là $q_1,q_2,...,q_t$

ta đặt $a=pq_1^pq_2^p...q_t^p$

tương tự như trên ta dễ dàng chứng minh được $q_{t+1}\notin \left \{ q_1,q_2,...,q_t \right \}:\left\{\begin{matrix} q_{t+1}\mid \frac{a^p-1}{a-1}\\q_{t+1}\not\equiv 1\left ( \mod\ p^2 \right ) \end{matrix}\right.$

ta sẽ chứng minh số $q_{t+1}$ này cũng thỏa đề thật vậy

giả sử tồn tại số nguyên dương $n$ sao cho

$q_{t+1}\mid n^p-p\Rightarrow n^p\equiv p\left ( \mod\ q_{t+1} \right )$

$\Rightarrow \left ( nq_1q_2...q_t \right )^p\equiv pq_1^pq_2^p...q_t^p\equiv a\left ( \mod\ q_{t+1} \right )$

$\Rightarrow \left ( nq_1q_2...q_t \right )^{p^2}\equiv a^p\equiv 1\left ( \mod\ q_{t+1} \right )$

$\Rightarrow ord_{q_{t+1}}\left ( nq_1q_2...q_t \right )\mid p^2\rightarrow ord_{q_{t+1}}\left ( nq_1q_2...q_t \right )\in \left \{ 1,p,p^2 \right \}$

mặt khác ta lại có

$ord_{q_{t+1}}\left ( nq_1q_2...q_t \right )\mid q_{t+1}-1$

với cách chọn $q_{t+1}$ ta suy ra được

$ord_{q_{t+1}}\left ( nq_1q_2...q_t \right )\notin p^2\rightarrow ord_{q_{t+1}}\left ( nq_1q_2...q_t \right )\in \left \{ 1,p \right \}$

$\Rightarrow \left ( nq_1q_2...q_t \right )^p\equiv 1\left ( \mod\ q_{t+1} \right )$

$\Rightarrow p\left ( nq_1q_2...q_t \right )^p\equiv p\left ( \mod\ q_{t+1} \right )$

$\Rightarrow n^p.a\equiv p\left ( \mod q_{t+1} \right )$

mà theo sự tồn tại của $n$ thì $n^p\equiv p\left ( \mod\ q_{t+1} \right )$

$\Rightarrow pa\equiv p\left ( \mod\ q_{t+1} \right )$

ta dễ thấy rằng $p\neq q_{t+1}\Rightarrow a\equiv 1\left ( \mod\ q_{t+1} \right )$

từ đây ta có được

$p\equiv \frac{a^p-1}{a-1}\equiv 0\left ( \mod\ q_{t+1} \right )$

tới đây có mâu thuẫn do đó ta có $\text{Q.E.D}$

Anh ơi , thế  thì thà dùng Zsigmondy còn dễ cm hơn

dùng sao em nhỉ? anh có nghĩ tới rồi nhưng do còn lòi cái thằng $d$ ở ngoài cứ vướng vướng ấy