Chủ đề này có 5 trả lời

[Nobodyv3]

Phòng Thi công của 1 xí nghiệp xây dựng muốn lập một nhóm thợ từ 10 thợ điện và 8 thợ nước để thi công công trình. Hỏi có bao nhiêu cách lập nhóm thợ gồm $a$ thợ điện và $b$ thợ nước sao cho $a-b\,\vdots\, 4$ và nhóm phải có ít nhất 1 thợ.

[Nobodyv3]

Đặt $x,y $ lần lượt là đại diện cho thợ điện, thợ nước. Xét đa thức $f(x,y)=(1+x)^{10}(1+y)^8$. Đó là $f(x,y)=\sum_{a=0}^{10}\sum_{b=0}^{8}T_{a,b}x^ay^b$ trong đó $T_{a,b}$ là số nhóm thợ có thể lập thỏa đề bài. Để tính toán, ta định nghĩa một hàm mới :
$$g(x)=f(x,x^{-1})=\sum_{a=0}^{10}\sum_{b=0}^{8}T_{a,b}x^{a-b}=(1+x)^{10}(1+x^{-1})^8$$.
Ta tính tổng các hệ số của các hạng tử có bậc $a-b\:\vdots \: 4$ trong khai triển $g(x)$.
Ta thấy :
$g(1)=2^{18}$
$g(-1)=0$
$g(i)=-g(-i)$
Nên số nhóm thợ lập được là :
$$\frac { g(1)+ g(-1) +g(i)+ g(-i) }{4}-1=2^{16}-1=65536-1=\boldsymbol {65535}$$
(ta loại trường hợp $T_{0,0}=1$)

[perfectstrong]

Phòng Thi công của 1 xí nghiệp xây dựng muốn lập một nhóm thợ từ 10 thợ điện và 8 thợ nước để thi công công trình. Hỏi có bao nhiêu cách lập nhóm thợ gồm $a$ thợ điện và $b$ thợ nước sao cho $a-b\,\vdots\, 4$ và nhóm phải có ít nhất 1 thợ.

 

Thử "nối tiếp" bài toán nhé Mặc dù sẽ không còn là bài toán đếm nữa.

Bài toán

Phòng Thi công của 1 xí nghiệp xây dựng muốn lập một nhóm thợ từ $n$ thợ điện và $n$ thợ nước để thi công công trình. Có $n$ công trình cần thi công, và ta cần chỉ định cho mỗi công trình một đội thợ, gồm 1 thợ điện và 1 thợ nước. Ta biết được rằng nếu lập đội gồm thợ điện $i$, thợ nước $j$ cho công việc $k$ thì sẽ tốn chi phí là $c_{ijk}$. Hãy tìm cách xếp đội sao cho ít tốn kém nhất (tổng chi phí là nhỏ nhất).

[Nobodyv3]

@perfectstrong: hic, quá sức em! Em ngồi hóng chuyện thui...

[hxthanh]

Bài toán của @perfectstrong với các số liệu mơ hồ có lẽ phải xây dựng thuật toán “tối ưu hoá” cho máy tính.
Đặt vấn đề cho pen&paper ta cho bài toán đơn giản hơn sau
$(d_k):\{1,1,2,3,5,8,13,…\}$
$(n_j):\{1,3,4,7,11,18,…\}$
Biết rằng chi phí cho mỗi công trình nếu chọn thợ điện $d_k$ và thợ nước $n_j$ là $d_k.n_j$
Hãy chọn ra $n$ đội thợ cho $n$ công trình với chi phí ít nhất.
Note: Hai dãy số đặc biệt!

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 12-04-2023 - 08:32

[chanhquocnghiem]

Bài toán của @perfectstrong với các số liệu mơ hồ có lẽ phải xây dựng thuật toán “tối ưu hoá” cho máy tính.
Đặt vấn đề cho pen&paper ta cho bài toán đơn giản hơn sau
$(d_k):\{1,1,2,3,5,8,13,…\}$
$(n_j):\{1,3,4,7,11,18,…\}$
Biết rằng chi phí cho mỗi công trình nếu chọn thợ điện $d_k$ và thợ nước $n_j$ là $d_k.n_j$
Hãy chọn ra $n$ đội thợ cho $n$ công trình với chi phí ít nhất.
Note: Hai dãy số đặc biệt!

Để dễ hình dung, ta xét bài toán cụ thể hơn nữa như sau :

Một chủ thầu có $6$ công nhân đang hưởng các mức lương theo giờ lần lượt là $80,50,30,20,10,10$ USD.

Một hôm trong lúc nhậu say (mừng công trình hoàn thành), ông cao hứng tuyên bố sẽ thưởng cho các công nhân bằng cách bốc thăm. Có $6$ lá thăm mang các số $18,11,7,4,3,1$. Ai bốc được lá thăm mang số nào thì sẽ nhận được tiền thưởng bằng con số đó nhân với mức lương của mình.

Ta hãy nghĩ xem trong tình huống nào thì tổng số tiền thưởng mà chủ thầu phải chi ra là ít nhất ?

 

Dễ dàng thấy rằng đó chính là tình huống "anh $80$" bốc số $1$, "anh $50$" bốc số $3$, "anh $30$ bốc số $4$,..., hai "anh $10$" bốc được số $11$ và $18$ (lương càng cao bốc số càng nhỏ)

Vậy thì số tiền thưởng ít nhất sẽ là $80.1+50.3+30.4+20.7+10.(11+18)=780$ USD

 

Trở lại bài toán của thầy Thanh, giải pháp sẽ là :

- Chọn $n$ thợ điện có chi phí thấp nhất và $n$ thợ nước có chi phí thấp nhất.

- Sắp xếp các thợ điện và thợ nước đã chọn theo chi phí tăng dần

   $d_1,d_2,d_3,...,d_n$ và $n_1,n_2,n_3,...,n_n$

- Kết hợp thợ điện và thợ nước thành các cặp $d_kn_{n-k+1}$

Khi đó tổng chi phí $d_1n_n+d_2n_{n-1}+d_3n_{n-2}+...+d_nn_1$ sẽ là ít nhất.