Chọn bi giả từ 13 bi bằng 3 lần cân?

[khachvanglai]

Toi co mot bai toan va mot bai ly the nay lam khong duoc . Nho cac cao thu giup tieu nhan voi .
Co 13 vien bi ,trong so co mot vien khac khoi luong .Bang 3 lan can hay xac dinh vien khac khoi luong do , dong thoi chi ra xem no nang hay nhe hon cac vien con lai .
Khong biet bai toan co loi giai khong nhi . Khong co thi ai do lam on chi ra gium toi cai nhe!
Thanks

:P
Con bai ly chac qua ben trang ve Vat ly post len nho moi nguoi ben do vay

[Bảo Kê]

Bài này ngày xưa đã được nêu ra bên diễn đàn CNTT Hương Sen , nhưng nó đã chết cho nên mình ko bít kết quả thế nào . Cũng đã từng nghiên cứu để tìm lời giải nhưng chưa thành công . Nếu biết nó nặng hay nhẹ hơn thì dễ quá .
Anh em đâu ra tay đê !!!

[huyenmy]

khó thật anh ạ , nhưng chẳng nhẽ Lam Son mà không ai giải quyết được à .Anh Lam son cứ nghiên cứu tiếp đi em tin anh sẽ ra thôi mà hii
mà bài này có giải được hay chỉ có đề bài mà lời giải thì không thì ai mà giải được cơ chứ.

[khachvanglai]

:s
Hay moi nguoi tu tu hang lam bai 13 vien bi .Lam thu bai 12 bi truoc di da . Cung hay ra phet day

[Bảo Kê]

A 13 viên bi à ?? Bài này khác rùi . Cái bài tôi nói là 12 viên bi cơ

[khachvanglai]

A 13 viên bi à ?? Bài này khác rùi . Cái bài tôi nói là 12 viên bi cơ :s
Bai 12 bi co loi giai do moi nguoi cu lam di nhe

[kid]

Ta không thể biết được nó nặng hay nhẹ hơn các viên còn lại thì phải . chỉ có thể xác định được thôi nếu đã biết được nó nặng hay nhẹ hơn nhưng quả còn lạ.

[khachvanglai]

Tui da noi roi do . Bai 12 vien bi co loi giai han hoi , moi nguoi lam thu di nhe

[huyenmy]

nếu tôi nhớ không nhầm thì chia thành ba phần đấy 4 -4 -4 hình như trong báo vật lý phổ thông có đấy . nhưng nếu không thì bây giờ ta cùng làm hihih

[Ronaldo]

Th 2: 4a > 4b Còn hai lần cân và có 5 đồng tiền thật đã biết
Lấy 1a + 2 b cân vớI 2 b + 2 t
Ở đây phải là 1a + 2b cân với 2b ( 2b còn lại trong 4b) và 1 t (1 thật chứ không phải hai thật đâu nhé).


Bà con có đóng góp gì cứ gửi lên nhé

[huyenmy]

các chú cứ làm sao thế , nếu 12 viên thì làm ra thôi nhưng 13 viên thì không có lời giải đâu mà đâm đầu vào đi àm nghe chưa . còn cách giái bài 12 viên tôi sẽ đăng nếu không có ai đăng .

[lephuochongnga]

tuyensingapore wrote:
các chú cứ làm sao thế , nếu 12 viên thì làm ra thôi nhưng 13 viên thì không có lời giải đâu mà đâm đầu vào đi àm nghe chưa . còn cách giái bài 12 viên tôi sẽ đăng nếu không có ai đăng .
__________________________________________________ ______________
Qua day cho biet tuyensingapore may moc qua do! Co le ban " chu quan " hay ban doc ko lien tuong duoc bai toan co chu!
hay y ban la cach giai ruom ra qua, dai qua thi ban co the post len di!
Moi nguoi tiep nhan y kien cua ban!

[Tucurie]

Nếu tớ nhớ không lầm thì bài này đã một dạo được tranh luận khá hay ho ở sinhvienvietnam.Mọi người có thể vào địa chỉ sau để tham khảo cách giải của các sinh viên Việt Nam:
http://sinhvienvietnam.net/viewtopic.nvn?t...bde5de6b3992775 (http://sinhvienvietnam.net/viewtopic.nvn?t=441&postdays=0&postorder=asc&start=0&sid=eca182e9053739ddabde5de6b3992775)
:D:D

[nowornever]

Nói chung là bài toán này giải rùi không có gì phải bàn cả nữa.
Tôi có thể nói :

Bài toán giải được từ 2--->13.

Bài toán không có lời giải với giá trị 14 trở lên.

Chứng minh:

lần cân đầu tiên must be cho a(status: s1) quả cân với a(status :s2) quả còn lại b quả (status: s3).

điều kiện a+a+b >= 14.

Suy ra:

a>=5 hoặc b>=6.

Nếu b>=6, chọn s1 bằng s2 bài toán nay tương đương với cân hai lần 6 quả với

chân lý về cân nặng---> chứng minh tiếp đi.

Nếu a>=5 cũng dễ dàng chứng minh chon s1>s2-----xong luon nha.

Loại bai toan nay coi nhu xong nhe. Con loai nao khac khong?

[Nothing]

Bài 12 viên bi này tôi đã được học trong giáo trình của môn Trí Thông Minh Nhân Tạo . Thật sự là hay !
Có sử dụng 1 số kiến thức về duyệt cây và đồ thị .

[huyenmy]

bài 12 viên bi thì em nghĩ anh phải biết chứ anh Trà hcihic. Bài 12 viên bi "thầy em" đã cho làm trên lớp roài ( không phải chỉ mình đội tuyển đâu nhé). Cách làm :

Đánh số 12 viên bi từ 1 đến 12: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.

Chia thành 3 nhóm: + Nhóm 1:{ 1, 2, 3, 4} + Nhóm 2:{ 5, 6, 7, 8} + Nhóm 3;{9, 10, 11, 12}

*Lần cân 1: Nhóm 1 cân với Nhóm 2.

Trường hợp 1: N1 = N2 ===> N3 gồm 9, 10, 11, 12 có chứa bi giả.

(++) Lần cân 2:Lấy 3 viên {1, 2, 3} = A đem cân với 3 viên {9, 10, 11} = B.

Trường hợp 1.1: A = B =====> viên 12 là viên giả.

Trường hợp 1.2: A > B =====> Viên giả nhẹ hơn và nằm trong B={9, 10, 11}

(--) Lần cân 3: Lấy 9 đem cân với 10.

Trường hợp 1.2.1: 9 = 10 ====> Viên bi giả là viên 11.

Trường hợp 1.2.2: 9 < 10 ====> Viên bi giả là viên 9.

Trường hợp 1.2.3: 9 > 10 ====> Viên bi giả là viên 10.

Trường hợp 2: N1 > N2.=====> N3 = {9,10,11,12} là bi thật. Bi giả nằm trong (N1+N2)={1,2,3,4,5,6,7,8}

và (1,2,3,4)>(5,6,7,8)


(++) Lần cân 2: Lấy 4 viên {1,5,6,7}=C đem cân với {8,9,10,11}=D

Trường hợp 2.1: C = D. ====> bi giả nằm trong G={2,3,4} và bi giả nặng hơn bi thật.

(--) Lần cân 3: Lấy 2 đem cân với 3.

Trường hợp 2.1.1: 2 = 3=====> 4 là bi giả nặng hơn thật

Trường hợp 2.1.2: 2 < 3=====> 3 là bi giả , nặng hơn thật

Trường hợp 2.1.3: 2 > 3=====> 2 là bi giả , nặng hơn thật

Trường hợp 2.2: C > D ===> 5,6,7 là bi thật. Bi 8 hoặc bi 1 là bi giả.

(--) Lần cân 3: Lấy viên 1 cân với 5

Trường hợp 2.2.1: 1 > 5 ===> 1 là bi giả, nặng hơn bi thật.

Trường hợp 2.2.2: 1 = 5====> 8 là bi giả, nhẹ hơn bi thật.

Trường hợp 2.3: C < D =====> {5, 6, 7} có bi giả , nhẹ hơn thật.

(--) Lần cân 3: Lấy viên 5 cân với viên 6

Trường hợp 2.3.1: 5 = 6 ===> bi 7 là bi giả nhẹ hơn bi thật.

Trường hợp 2.3.2: 5 < 6 ====> bi giả là bi 5 nhẹ hơn bi thật.

Trường hợp 2.3.3: 5 > 6 ====> bi giả là bi 6 , nhẹ hơn bi thật

Trường hợp 3: N1 < N2. Chúng ta hoàn toàn xác định như cách ở trường hợp 2.


Trường hợp 3 em không cần ghi rõ ra nữa , vf em nghĩ ghi lại mất công, tin chắc mọi người đều hiểu ở trường hợp 2 thì thay đổi vị trí cho trường hợp 3 là xong.


Như vậy với 3 lần cân có thể xác định rõ viên bi giả trong 12 viên bi và biết được nặng hơn hay nhẹ hơn. Bài 13 viên em nghĩ không có cách giả. Bác nào có thì thử nêu ra coi ạ.

[huyenmy]

hichic trong phần trả lời em trình bày rất dễ đọc , lùi vô thụt ra tử tế, thế mà bây giwò hichic. Thôi kệ . Như vậy là bài 12 viên đã được giải quyết. Em đợi bài 13 viên của cái bác gù bảo là làm được đó.

[huyenmy]

hichic 2h42 phut ngồi chát xong lại có thêm 2 cách khác nhau nữa để giải bài 12 viên bi. Nhưng bài 13 viên bi thì không có cách giải. Bác nào nói có cách giải thì giả đi

[huyenmy]

10am. Bài 13 viên bình tĩnh đã, có khi em có cách ehhe. Làm thử cái đã. :D :D

[nowornever]

Bọn trẻ dao này học hanh thế nào ấy.

Bài 14 trở lên không có lời giải xem chứng minh của tôi ở trên ấy

nào quay lại bài 13 bi.

----->quy uớc trạng thái của một nhóm là true thì tất cả đều là thật
chia 13 bi thành 3 nhóm
nhóm1:4 viên (trạng thái nhóm:s1),
nhóm 2:4 viên (trạng thái nhóm:s2),
nhóm 3: 5viên (trạng thái nhóm :s3),

cân nhóm 1 với nhóm 2 nếu khác cân nặng ---> bài toán 12 viên.

nếu nhóm 1 và nhóm 2 bằng nhau ta có 8 viên lập thành nhóm A trạng thái s1=s2=true; và một nhóm gọi là nhóm B 5 viên có trạng thái false.


-------------------Chỉ còn hai lần cân------------------------------------------------

trong nhóm B chia thành 2 nhóm B1 3 viên (trạng thái: s_b1) và nhóm B2 2 viên (trạng thai: s-b2). Nhận thấy rằng s_b1 hoặc s_b2 là false;

Cân nhóm B1 với 3 viên thật có hai trường hợp xảy ra:

bằng nhau suy ra nhóm B2 có trạng thái s_b2=False (có 2 viên mà còn

một lần cân) lấy một viên thuộc B2cân với viên có trạng thái True thế là

xong. Còn nếu không


-------------------Chỉ còn một lần cân-----------------------------------------------

Ta có 3 viên thuộc B1 có trạng thái là False và giả sử là nặng hơn đi lấy

hai viên thuộc B1 cân với nhau, viên nào nặng hơn thì là viên giả, còn

không thì là viên còn lại giả

Nhấn mạnh là bai toán giải xong rồi đấy.

[Nothing]

Định đưa ra minh hoạ bằng 1 hình vẽ đồ thị duyệt cây . Nhưng có vẻ như mọi người ko cần thì thôi . :P

[Unregistered]

Định đưa ra minh hoạ bằng 1 hình vẽ đồ thị duyệt cây

Đồ thì duyệt cây của ông bạn suy cho cùng cũng là sự mô hình hoá của các trường hợp: Nếu lớn hơn thì đi theo nhánh này, nếu bé hơn thì nhánh này, nếu bằng thì nhánh này.

Nếu vẽ ra được thì cứ vẽ đi. Unregistered tôi rất chờ đấy.

[Nothing]

Rõ ràng , nếu tôi đưa ra 1 bức tranh mô hình hoá , thì dễ hình dung hơn là các bạn viết dài ngoằng như trên kia . Và dùng lý thuyết về duyệt cây đồ thị thì cũng chẳng có gì là cao siêu cả . Rất đơn giản , ai cũng có thể hiểu , nhưng nó lại rất hiệu quả . Với bài này , đó là phép duyệt cây theo chiều sâu .

[Unregistered]

OK, đúng là dùng đồ thị thì dễ nhìn hơn, nhưng cái quan trọng mà tôi quan tâm là có giải được không thôi (có chỉ được phép cân hay không?). Nothing đưa ra cách giải xem lào.

[huyenmy]

bài 13 viên giải được còng gì. Xong rồi mấy bác còn cãi nhau gì nữa.

[nowornever]

/
với 3 lần cân thì không thể nào mà xác định được đâu bạn ạ còn muốn xác định đâu là viên bi giả có thế làm như thế này ạ
Lấy 4 đồng tiền bất kì ( gọI là a ) cân vớI 4 đồng tiền khác ( gọI là B) ( tiền thật gọI là t)
Th 1: Nếu 4a = 4b,-> trong năm đồng còn lạI phảI có đồng tièn giả : gọI là 5 c.
Còn hai lần cân. Lấy 3 c cân vớI 3 đồng thật

Th 1.1: Nếu 3c = 3t:
Lấy một trong hai đồng c còn lạI cân vớI một đồng thật.
Th 1.1.1 : = nhau -> đồng c còn lạI là giả. Không biết tiền giả nặng hơn hay nhẹ hơn.
Th 1.1.2 : # nhau -> đồng c đem cân là giả, biết được tiền giả nặng hơn hay nhẹ hơn
Th 1.2: Nếu 3c > 3t : Biết được hai điều : Tiền giả nằm trong 3c này và tiền giả nặng hơn tiền thật. Còn một lần cân phảI tìm ra đồng giả
Cân 2 đồng bất kì trong 3c còn lạI
Th 1.2.1: = nhau -> đồng c còn lạI là giả, tiền giả nặng hơn tiền thật
Th 1.2.2: Chênh lệch -> đồng nào nặng hơn là giả
Th 1.3: 3c < 3t :Làm tương tự 1.2
/

Trường hợp 4 quả cân 4 quả mà có sự khác biệt thì chả khác gì một cái đã cũ mà bạn không cần quan tâm. Nếu các bạn lập trình hướng đối tượng nhiều thì các bạn sẽ có tư duy này-----> Không nên quan tâm đến nhứng cái tool mà người ta cung cấp cho mình là đúng hay sai.

To Unregister:

Nếu bạn muốn biết lời giải của trường hợp còn lại bạn có thể tham chiếu cách giải của Lucky boy.

To everyone:

Bài toán này tôi cũng đã chứng minh với 14 viên bi thì không có lời giải xem trang 2.
(Tôi chỉ đưa ra gợi ý)
Muốn mở rộng hơn nữa bạn có thể làm như sau:

Số lần cân tăng lên. 4 chẳng hạn.--> Tôi chỉ guest thôi là tầm 29 hay 30 viên gì đấy bạn từ tìm ra số max của mình nhé
Số bi giả tăng lên. 2 chẳng hạn.

Nếu bạn nào siêu thuật toán bạn hãy tìm quan hệ giữa m,n,l trong bài toán: có m viên bi , n quả giả(giới hạn là giả nhưng giả cùng loại), l là số lần cân.


Nhấn mạnh lần nữa Bài toán đã giải xong với trường hợp số bi là 13

[huyenmy]

Originally posted by Unregistered@Mar 1 2003, 11:35 AM
Lại có chú Lucky boy vào nói linh tinh. Giải được hồi nào thía, sao tôi không đọc thấy lời giải ở đây. Đọc kĩ hướng dẫn trước khi sử dụng.
đúng là cái bác Unregister này ngoan cố quá, rõ ràng là xong rồi còn gì . Nhưng mà bác nowornever đã giải rồi đó còn gì.
Trường hợp bi giả nằm trong 5 viên thì đơn giản roài. Còn nằm trong 8 viên thì qua lại bài giải 12 bi thế là xong roài còn gì.
hi`hi` lần này bác Unregister coi lại nhé. Đừng bảo em đọc kĩ hướng dẫn nhé :D :D

[huyenmy]

hic hic ông anh thân mến. Trường hợp bi giả nằm trong 8 quả em giải ở bài 12 viên rồi mà. Còn bài của em thì đã vô tình chứng minh hộ trường hợp bi giả nằm trong 8 viên( của bài 13 viên). Và em nghĩ như vậy ghép lại thì rõ ràng ai cũng có thể giải bài 13 viên rồi còn gì ạ. EM đợi ý kiến bác, nếu bác không đồng ý thì lên tiếng , hôm sau em mất công ngồi type lại lời giải bài 13 viên cho bác coi.
Em: Luckyboy.
Kính bác.

[huyenmy]

nói thêm bác chút, cái trường hợp bi giả nằm trong 8 bi hiện nay em đã nắm được tới 3 cách giải roài, bác thử đọc bài của em coi, em nghĩ là đúng. Nếu sai em sẽ post tiếp cho bác coi hcihic. Dù sao cũng cám ơn bác. Em cũng quý bác lắm :) :)