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$

  

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)