2 replies to this topic

[minhtuyb]

$\fbox{Bài toán:}$ Cho $1000$ số $000;001;...;999$ và $100$ hộp $00;01;...;99$. Một số $\overline{abc}$ có thể được xếp vào một trong các hộp $\overline{ab};\overline{bc};\overline{ac}$.
 
VD: Số $000$ chỉ có thể xếp vào hộp $00$; số $123$ có thể được xếp vào hộp $12$,$13$ hoặc $23$
 
Hỏi số hộp tối thiểu để xếp đủ $1000$ số trên?
 
 
$\fbox{Tổng quát}$

Spoiler

Một tập hợp được gọi là kiểu $A$ nếu tập hợp đó có đúng $k$ phần tử $\left\{x_1;x_2;...;x_k \right\}$(có kể đến thứ tự), trong đó mỗi phần tử $x_i\ (i=\overline{1,k})$ có thể nhận một trong $l$ giá trị cho trước (VD $\left\{1;2;...;l \right\}$). (Có tất cả $k^l$ tập hợp kiểu $A$)

Một chiếc hộp là một tập hợp có đúng $n$ phần tử $\left\{y_1;y_2;...;y_n \right\}$(có kể đến thứ tự) và mỗi phần tử cũng nhận một trong $l$ giá trị như trên $(0<n<k)$ (Có tất cả $n^l$ chiếc hộp)

Một tập hợp kiểu $A$ có thể được xếp vào một chiếc hộp $\left\{y_1;y_2;...;y_n \right\}$ nếu như tồn tại một cách xóa $n-k$ phần tử của tập hợp đó thỏa mãn tập hợp mới sau khi xóa chính là $\left\{y_1;y_2;...;y_n \right\}$ (có kể thứ tự)

Hỏi để xếp tất cả các tập hợp kiểu $A$ vào các hộp thì cần ít nhất bao nhiêu hộp?
 
Trường hợp bài toán trên là với :$k=3;l=10;n=2$ ($l=10$ ứng với các giá trị là các chữ số)

[mathforlife]

Có lẽ là sư dụng bô đê này:

Cho đô thị đâỳ đủ 10 đỉnh. Tìm sô cạnh nhỏ nhât của đô thị cân đánh dâú đê tam giác bât kì có đỉnh là đỉnh đô thị có ít nhât môt cạnh đc đánh dâú.

 

Đáp sô là 20 cạnh,. Áp dụng vào bài toán ra 50 hôp

Edited by mathforlife, 27-06-2013 - 17:53.

[minhtuyb]

Có lẽ là sư dụng bô đê này:

Cho đô thị đâỳ đủ 10 đỉnh. Tìm sô cạnh nhỏ nhât của đô thị cân đánh dâú đê tam giác bât kì có đỉnh là đỉnh đô thị có ít nhât môt cạnh đc đánh dâú.

 

Đáp sô là 20 cạnh,. Áp dụng vào bài toán ra 50 hôp

Bạn có thể nêu cho mình cách chứng minh bổ đề cũng như cách áp dụng vào bài toán không nhỉ? Cảm ơn bạn nhiều .