n đồng tiền chưa biết khối lượng

Có http://dientuvietnam...n/mimetex.cgi?n đồng tiền chưa biết khối lượng và cái cân hai đĩa.Ở mỗi thời điểm ta có thể chọn một số chẵn các đồng tiền và đặt mỗi đĩa một nửa số đồng tiền đã chọn,sau đó xem bên nào nặng hơn.Mục đích của ta là xem khối luợng của http://dientuvietnam...n/mimetex.cgi?n đồng tiền đó có bằng nhau tất cả hay không?Chứng minh rằng cần ít nhất http://dientuvietnam...mimetex.cgi?n-1 lần cân thì mới đạt được mục đích trên.

Nhìn lại các bài toán của Iran TST 2006

Tôi làm như sau, thấy cũng không chính xác lắn:

Gọi n quả cân từ 1 đến n, có cân nặng là m = (m1,…mn). Ta cho tương ứng 1 lần cân với 1 vector độ dài n như sau : giả sử cân các quả cân thứ (i1,…,ik) với (j1,…,jk) thì vector v xác định như sau: v(i1) =…v(ik)=1, v(j1)=…v(jk) = -1, còn lại = 0, tức là sau lần cân đó biết được v*m âm, dương hay bằng 0.Giả sử sau 1 số lần cân là h, các vector tương ứng là v1,…vh, ta nói được n quả cân bằng nhau hay không, tức là nếu có 1 lần cân không cân băng thì sai, còn nếu tất cả cân bằng thì đúng (cái này tôi không chắc lắm). Ta xét trường hợp tất cả đều cân bằng, ta phải nói được tất cả băng nhau.

Xét các vector ei xác định như sau ei(i) = 1,còn lại bằng 0. Ta có các tc sau:

_ 2 quả cân thứ i và j có nói được bằng nhau khi và chỉ khi tồn tại 1 bộ số thực (x1,…,xh) sao cho ei – ej = x1*v1 + … + xh*vh (theo nghĩa là nếu so sánh được 2 quả cân đó thì phải liên hệ được với kết quả các lần cân: vì (ei-ej)*m = mi- mj ) (cúng không chắc luôn), tức là ei - ej nằm trong L(v1,v2,…,vh).

_ n quả cân có thể nói tất cả băng nhau khi và chỉ khi 2 quả cân bất kì nói được bằng nhau .

Như vậy nếu n quả cân nói được có thể bằng nhau tất cả thì e1- e2, e2-e3, … e(n-1)-en phải nằm trong L(v1,v2,…vh) Tuy nhiên dễ thấy n-1 vector e1-e2, e2-e3, … , e(n-1)-en là độc lập tuyến tính, trong khi số chiều của L(v1,v2,…vh) không vượt quá h, do đó h >= n-1, dpcm, xong .

Cách trên chưa chính xác, có thể giải bài này dễ hiểu hơn như sau:

Bài toán cho ta (v1,v2,...vh), sao cho với mọi vector m = (m1,m2,...,mn), mj dương bất kì thì: nếu tồn tại i sao cho vi*m khác 0 thì m không tuyến tính với e = (1,1,...,1) (tức là các mj không cùng bằng nhau), còn nếu vi*m = 0 với mọi i thì m tuyến tính với e. Ta cần cm h>=n-1.

Thật vậy nếu h <= n-2, số chiều của L(v1,...vh) không quá n-2, nên phần bù trực giao của L(v1,...vh) có chiều không bé hơn 2, suy ra tồn tại 1 vector u khác 0 không tuyến tính với e (các uj không đồng thời bằng nhau) mà vi*u = 0 với mọi i, lấy 1 số t ta có vi*(e + tu) = 0 với mọi i, tuy nhiên ta có thể chọn t đủ nhỏ sao cho m = e + tu có tất cả các hệ số đều dương. Mâu thuẫn vì vi*m = 0 với mọi i mà các hệ số của m không đồng thời bằng nhau.

Vậy h>= n-1, xong .

Gọi n quả cân là a1,...,an. Không mất tính tổng quát, có thể giả sử a1+a2+...+an=n. Ta chọn trường hợp mà n quả cân này bằng nhau và h là số lần cân ít nhất để đạt được mục đích. Như vậy sau mỗi 1 lần cân ta được 1 phương trình dạng ai1+ai2+...+aik - aj1-aj2-...-ajk=0. Như vậy ta được 1 hệ h+1 phương trình và n ẩn. Vì phương trình có nghiệm duy nhất là a1=...=an=1 nên phải có h+1 >= n. Tức là h >= n-1.

Cách của bác Quân đúng rồi, thực chất cách tôi cũng thế, tuy nhiên bác phải chú ý là hệ pt trên là trên miền số dương . Có khả năng hệ có nhiều nghiệm nhưng chỉ có 1 nghiệm duy nhất là toàn dương là e = (1,1,..,1) thì vẫn thỏa mãn tc đầu bài, nhưng trường hợp này không xảy ra vì nếu có 1 nghiệm khác a = (a1,...,an) thì xét t đủ bé thì (e + t*a)/(1+n*t) cũng là nghiệm và toàn dương.

Edited by VŨ Thanh Tùng, 29-04-2006 - 14:08.

tôi cũng nghĩ đến trường hợp này rồi . thực ra khi có 1 nghiệm âm, ví dụ là (b1,...,bn) thì có thể xét T đủ lớn thì (b1+T,...,bn+T) sẽ toàn dương. Nhưng ta lại có (1+T,...,1+T) cũng là nghiệm của hệ phương trình mới với cái tổng chuẩn hóa ban đầu là n thay bằng n+nT

Lần này thì bác làm chính xác hoàn toàn rồi, .