LỚP BÀI TOÁN PHỦ HÌNH TRONG TỔ HỢP(P1)
Đây là tâp hợp môt số bài toán liên quan đến xác định khoảng của 1 đại lượng đặc trưng cho 1 tập hợp hình (thường là diện tích) thỏa mãn mọi tập đó phủ được hình H cho trước
Lớp bài toán này xoay quanh việc lấp đầy hình vuông đơn vị:
Bài 1:Cho hình vuông đơn vị,tìm max S dể một tập hình vuông có tổng diện tích là S có thể "nhét vào trong hình vuông đơn vị(không có điểm trong chung)
Lời giải:
NX:Nếu $S>\frac{1}{2}$ thì ta chọn hai hình vuông cạnh $\frac{1}{2}+e$ với e nhỏ thì không xếp được
Ta chứng minh $S=\frac{1}{2}$ thỏa
Ý tưởng xếp tương tự bài 1:xếp các hình vuông theo thứ tự từ lớ đến bé,xếp trên hàng cho tới khi vượt qua phần giới hạn hv xếp lên tầng 2 và xếp trồng lên cạnh tầng 1
Gọi $h_1,h_2,...h_k$ lần lượt là độ cao tầng 1,tầng 2,...,tầng k
Gọi $l_1,l_2,...,l_k$ là độ dài đáy các tầng
Khi đó ta có $l_i+h_{i+1}>1$
Ta cần cm $\sum_{i=1}^{k-1}h_i=<1$
Lớp bài toán này xoay quanh việc lấp đầy hình vuông đơn vị:
Bài 1:Cho hình vuông đơn vị,tìm max S dể một tập hình vuông có tổng diện tích là S có thể "nhét vào trong hình vuông đơn vị(không có điểm trong chung)
Lời giải:
NX:Nếu $S>\frac{1}{2}$ thì ta chọn hai hình vuông cạnh $\frac{1}{2}+e$ với e nhỏ thì không xếp được
Ta chứng minh $S=\frac{1}{2}$ thỏa
Ý tưởng xếp tương tự bài 1:xếp các hình vuông theo thứ tự từ lớ đến bé,xếp trên hàng cho tới khi vượt qua phần giới hạn hv xếp lên tầng 2 và xếp trồng lên cạnh tầng 1
Gọi $h_1,h_2,...h_k$ lần lượt là độ cao tầng 1,tầng 2,...,tầng k
Gọi $l_1,l_2,...,l_k$ là độ dài đáy các tầng
Khi đó ta có $l_i+h_{i+1}>1$
Ta cần cm $\sum_{i=1}^{k-1}h_i=<1$
Thật vậy:Ta có $S>=h_1^2+h_2.(l_1-h_1+h_2)+h_3(l_2-h_2+h_3)+...+h_k(l_{k-1}-h_{k-1}+h_k)$
mà $l_i-h_i+h_{i+1}>1-h_i>1-h_1$
=>$1/2>=h-1^2+(1-h_1)(h_2+...+h_k)$
từ đây dễ dàng suy ra đpcm
Bài toán 2 giải theo phương pháp tương tự
Bài 2:Cho hình vuông đơn vị,tìm min S dể một tập hình vuông có tổng diện tích là S có thể bao hết hình vuông đơn vị
(đáp số:Smin=3)
CHỨNG MINH Ck_n KHÔNG LÀ LŨY THỪA
Bài toán:Prove that, if 
, then the equation 
has no solution in Z
Chứng minh của Erdos:Chứng minh C^k_n không là lũy thừa
, then the equation has no solution in ZChứng minh của Erdos:Chứng minh C^k_n không là lũy thừa
BÀI TOÁN CỦA TÁC GIẢ
Cho một hình H kín không có trục đối xứng,tại mặt kín của mỗi cạnh đặt 1 gương phẳng và ở mỗi đỉnh có gương phẳng có pháp tuyến là phân giác của 2 cạnh kề.Từ một điểm sáng nằm bên trong hình phát ra một tia sáng,tia sang phản xạ và gặp các cạnh hình tại các tiếp điểm.Hỏi rằng hợp các tiếp điểm này có phải là hình H?
BÀI TỔ HỢP ĐỀ THI HSG TP HÀ NỘI LỚP 12
Đề bài:(bài V,đề thi hsg toán tp Hà Nội,2017):
Gọi các số k là loại n với $n \in \{1;2;3\}$ nếu $k=0$ hoặc k là phần tử của dãy $(n+2)^a$ hoặc k là tổng một số phần tử của dãy trên(chú ý là phân biệt).CMR:Mọi số nguyên dương đều viết được dưới dạng tổng của một số loại 1,một số loại 2 và một số loại 3.
Dựa trên lời giả của nhóm các thầy,bài toán là hệ quả trực tiếp của bổ đề sau:
Cho dãy số nguyên dương $a_n$,$a_0$=1 và $a_n <=a_0+a_1+...+a_{n-1}$
CMR:mọi số tự nhiên đều biểu diễn được dưới dạng tổng của các số $a_k$ phân biệt
Bổ đề trên có thể chứng minh dễ dàng bằng phương pháp quy nạp mạnh,và từ đó ta có thể áp dụng vào bài toán với dãy $a_{3k}=3^k,a_{3k+1}=4^k,a_{3k+2}=5^k$
Thế nhưng với không phải ai cũng biết bổ đề trên (kể cả tác giả bài viết này),nên tác giả đưa ra một lời giải khác,và sẽ nhắc đến việc sử dụng thuật toán:
Lời giải:
Xét quá trình sau:
(A):Với số nguyên dương n,gọi k là số tự nhiên thỏa:$3^{k+1}>n>=3^k$,đặt $n_1=n-3^k$
tương tự ta có $4^{t+1}>n_1>=4^t$,đặt $n_2=n_1-4^t$, và $5^{s+1}>n_2>=5^s$,$n_3=n_2-5^s$
Nếu $n_3<3^k$,ta có thể tiếp tục (A),ngược lại thực hiện (B):
(B):Xét $n_4=n-3^k-5^{s+1}$,nếu $n_4<0$ thì số $n-5^{s+1}$ thỏa,còn $n_4$>0 thì số $n_4$ thỏa
Ta sẽ chứng minh thuật toán trên đúng:
Giả sử (A) dừng ở một điểm nào đó.Khi đó ta có:
$2.3^k+4^t+5^s=<n<min\{3^k+4^t+5^{s+1};3^k+4^{t+1};3^{k+1}\}$
=>$4^t+5^s<3^k;3^k+5^s<3.4^t;3^k<4.5^s$
Nếu $4^t=<5^s$ thì $3^k<24^t$ và từ đây có vô lí
vậy $4^t>5^s$ và ta có $n>2.3^k+4^t+5^s>2(4^t+5^s)+5^s>5^{s+1}$,tới đây xét $a=n-3^k-5^{s+1}$
Nếu a>0 thì số $n-5^{s+1}$,ngược lại thì $a<2.3^k-3^k-3^k=3^k$,đúng
Vậy thuật toán luôn chạy và giảm n.
Gọi các số k là loại n với $n \in \{1;2;3\}$ nếu $k=0$ hoặc k là phần tử của dãy $(n+2)^a$ hoặc k là tổng một số phần tử của dãy trên(chú ý là phân biệt).CMR:Mọi số nguyên dương đều viết được dưới dạng tổng của một số loại 1,một số loại 2 và một số loại 3.
Dựa trên lời giả của nhóm các thầy,bài toán là hệ quả trực tiếp của bổ đề sau:
Cho dãy số nguyên dương $a_n$,$a_0$=1 và $a_n <=a_0+a_1+...+a_{n-1}$
CMR:mọi số tự nhiên đều biểu diễn được dưới dạng tổng của các số $a_k$ phân biệt
Bổ đề trên có thể chứng minh dễ dàng bằng phương pháp quy nạp mạnh,và từ đó ta có thể áp dụng vào bài toán với dãy $a_{3k}=3^k,a_{3k+1}=4^k,a_{3k+2}=5^k$
Thế nhưng với không phải ai cũng biết bổ đề trên (kể cả tác giả bài viết này),nên tác giả đưa ra một lời giải khác,và sẽ nhắc đến việc sử dụng thuật toán:
Lời giải:
Xét quá trình sau:
(A):Với số nguyên dương n,gọi k là số tự nhiên thỏa:$3^{k+1}>n>=3^k$,đặt $n_1=n-3^k$
tương tự ta có $4^{t+1}>n_1>=4^t$,đặt $n_2=n_1-4^t$, và $5^{s+1}>n_2>=5^s$,$n_3=n_2-5^s$
Nếu $n_3<3^k$,ta có thể tiếp tục (A),ngược lại thực hiện (B):
(B):Xét $n_4=n-3^k-5^{s+1}$,nếu $n_4<0$ thì số $n-5^{s+1}$ thỏa,còn $n_4$>0 thì số $n_4$ thỏa
Ta sẽ chứng minh thuật toán trên đúng:
Giả sử (A) dừng ở một điểm nào đó.Khi đó ta có:
$2.3^k+4^t+5^s=<n<min\{3^k+4^t+5^{s+1};3^k+4^{t+1};3^{k+1}\}$
=>$4^t+5^s<3^k;3^k+5^s<3.4^t;3^k<4.5^s$
Nếu $4^t=<5^s$ thì $3^k<24^t$ và từ đây có vô lí
vậy $4^t>5^s$ và ta có $n>2.3^k+4^t+5^s>2(4^t+5^s)+5^s>5^{s+1}$,tới đây xét $a=n-3^k-5^{s+1}$
Nếu a>0 thì số $n-5^{s+1}$,ngược lại thì $a<2.3^k-3^k-3^k=3^k$,đúng
Vậy thuật toán luôn chạy và giảm n.
LỜI GIẢI BÀI SỐ HỌC HSGSTST
Đề bài:Tìm tất cả các số nguyên dương $n$ sao cho với mọi số nguyên $k$ thì tồn tại $m$ để $n|m^4+m^3+m^2+k$
Lời giải:
+$n=1$ và $n=2$ thỏa
+Xét $n>=3$
Khi đó $\{m^4+m^3+m^2,m=0,n-1\}$ là hê thặng dư đầy đủ mod $n$ (gọi là hệ (1))
Xét $p|n$,$p>=3$,$p$ lẻ (nếu có),khi đó có $\frac{n}{p}$ phần tử của (1) chia hết cho $p$
Nếu $(\frac{-3}{p}) \in {0;1}$ thì tồn tại $t$ để $p|t^2+t+1$ khi đó có $>\frac{n}{p}$ phần tử của (1) chia hết cho $p$,vô lý.
Như vậy $n$ không chia hết cho 3
Mặt khác dễ cm $n$ không chia hết cho 4( chọn k=2)
Đặt $n=2^s.t$ với $s<2$,nếu t không là số nguyên tố thì $t=ab$,$a>=b>=5$,áp dụng bổ đề trên được $(\frac{-3}{a})=(\frac{-3}{b})=(\frac{-3}{t})=-1$,vô lý.Nên $n \in \{t,2t|t is prime\}$
TH1:$n=t$
Chọn $k=2$ được $m^4+m^3+m^2+2=((m+1)^2+1)(m^2-m+1)$ nên tương tự trên ta có $(\frac{-1}{t})=1$
từ đó ta có $(p-1)!= \prod_{k=1}^{p-1}(m^4+m^3+m^2)=((\frac{p-1}{2})!)^2=1$ vô lí.
TH2:$n=2t$
Khi đó cm đc $\{m^4+m^3+m^2,m=0,n-1\}$ là hê thặng dư đầy đủ mod $t$,đưa về TH1
KL:$n \in \{1;2\}$
Lời giải:
+$n=1$ và $n=2$ thỏa
+Xét $n>=3$
Khi đó $\{m^4+m^3+m^2,m=0,n-1\}$ là hê thặng dư đầy đủ mod $n$ (gọi là hệ (1))
Xét $p|n$,$p>=3$,$p$ lẻ (nếu có),khi đó có $\frac{n}{p}$ phần tử của (1) chia hết cho $p$
Nếu $(\frac{-3}{p}) \in {0;1}$ thì tồn tại $t$ để $p|t^2+t+1$ khi đó có $>\frac{n}{p}$ phần tử của (1) chia hết cho $p$,vô lý.
Như vậy $n$ không chia hết cho 3
Mặt khác dễ cm $n$ không chia hết cho 4( chọn k=2)
Đặt $n=2^s.t$ với $s<2$,nếu t không là số nguyên tố thì $t=ab$,$a>=b>=5$,áp dụng bổ đề trên được $(\frac{-3}{a})=(\frac{-3}{b})=(\frac{-3}{t})=-1$,vô lý.Nên $n \in \{t,2t|t is prime\}$
TH1:$n=t$
Chọn $k=2$ được $m^4+m^3+m^2+2=((m+1)^2+1)(m^2-m+1)$ nên tương tự trên ta có $(\frac{-1}{t})=1$
từ đó ta có $(p-1)!= \prod_{k=1}^{p-1}(m^4+m^3+m^2)=((\frac{p-1}{2})!)^2=1$ vô lí.
TH2:$n=2t$
Khi đó cm đc $\{m^4+m^3+m^2,m=0,n-1\}$ là hê thặng dư đầy đủ mod $t$,đưa về TH1
KL:$n \in \{1;2\}$
Đăng ký:
Bài đăng (Atom)