Đến nội dung

Hình ảnh

Làm sao để vừa được vàng vừa được vợ ?

- - - - -

  • Please log in to reply
Chủ đề này có 11 trả lời

#1
Kimluan

Kimluan

    Thượng sĩ

  • Thành viên
  • 226 Bài viết
Một anh tuy nhà giàu nhưng học giỏi, anh ta được phụ thân cho một túi vàng (có 13 đồng vàng) nhưng khốn nổi ông cha xỏ lá đã bỏ vào đó một đồng tiền giả có hình dạng y chang các đồng thật (không biết nặng hơn hay nhẹ hơn). Ông cho anh một cái cân thăng bằng rồi bắt anh thực hiện lần lượt các nhiệm vụ :
Nhiệm vụ 1: Bắt anh trong 3 lần cân phải tìm được đồng vàng giả trong túi vàng gồm 13 đồng vàng trên, nếu thực hiện xong túi vàng này sẽ thuộc về anh (tất nhiên vứt đồng vàng giả đi nếu không muốn đi tù)
Chàng trai thông minh không mấy khó khăn để thực hiện được nhiệm vụ thứ nhất và lập tức có 12 đồng vàng thật nhét túi.

Nhiệm vụ 2: Ông cha rất hài lòng và đưa tiếp cho cậu con trai bị vàng thứ hai có 37 đồng vàng, ông cho biết trong bị này cũng có một đồng vàng giả và bắt anh trong 4 lần cân phải tìm được đồng vàng giả, nếu làm được bị vàng thứ hai sẽ thuộc về anh (đậm hơn bị thứ nhất nhiều :D)

Nhiệm vụ3: Chàng trai thông minh một lần nữa lại đáp ứng yêu cầu của cha, ông cha vuốt râu mỉm cười rồi chỉ vào người con gái mặc áo xanh (rất xinh đẹp) ở góc phòng, rồi bảo:
ìCon hãy chứng minh: trong http://dientuvietnam...cgi?4.3^{n-2} 1 đồng vàng
Nếu con chứng minh được, ngày mai người con gái kia sẽ là vợ con, còn không, thì cũng ngày mai thôi nó là mẹ con ?!! ì

Nhiệm vụ 4: Chàng trai lại chứng minh được, ông cha tuy miệng cười để chúc mừng con, nhưng trong bụng lại làu bàu: ” định bắt ép nó không ngờ nó lại giải ra”, ông bèn nghĩ ra một cách để hại con liền mừng rỡ bảo:
ì Con hãy chứng minh hoặc bác bỏ mệnh đề sau:
Mệnh đề: trong http://dientuvietnam...n/mimetex.cgi?n lần cân (http://dientuvietnam...cgi?4.3^{n-2} 1 đồng vàng
Nếu mệnh đề sai con hãy chỉ ra một ví dụ rồi tìm số vàng lớn nhất để trong n lần cân có thể tìm được đồng vàng giả trong số vàng trên.
Nếu thực hiện được nhiệm vụ này thì toàn bộ gia tài của ta sẽ trao cho con, bằng không ta sẽ lấy lại toàn bộ số tiền ở nhiệm vụ 1 và nhiệm vụ 2, kể cả…vợ của con nữa. ì

Nhiệm vụ 4 quả là khó, nếu là bạn, bạn sẽ giải như thế nào nếu không muốn bị trắng tay ?

*PS: Mình đã giải quyết xong ba nhiệm vụ đầu, nhưng nhiệm vụ cuối thì chỉ có nước… pó tay thui (nếu gặp ông cha như vậy thì chắc hận mà chết :D), sẽ rất khâm phục nếu bạn nào ra tay giải quyết được nhiệm vụ này, nhưng trước hết xin mời các bạn lần lượt giải quyết ba nhiệm vụ đầu cái đã. Như đã thông báo từ trước : ông cha rất xỏ lá , do đó không có nhiệm vụ nào là dễ cả, các bạn nên giải với một cây bút và một quyển vở chứ ngồi nhẩm thì không ra được đâu, và cũng đừng ngạc nhiên nếu một tiếng trở lại vẫn ko giải quyết được nhiệm vụ nào :D

#2
kyoshiro_hp

kyoshiro_hp

    Thượng sĩ

  • Thành viên
  • 202 Bài viết
Em xin giải 3 NV đầu thế này ạ:
NV 1 thì hình như đã có ở phần THCS :D nên thôi ( làm luôn NV2 chứ 13 đồng thì bõ bèn gì :D)
- Ta chia 37 đồng vàng thành 3 nhóm A(1.12),B(1.12),C(1.13).
-Đem cân A với B , nếu A=B thì trở thành bài toán 1 (công nhận ko cm hehe)
.Nếu A<B chẳng hạn, ta chia A lần lượt ra thành 4 nhóm A(1.3),A(4.6),A(7.9),A(10.12),tương tự với B
-Đem cân chéo bất kì chẳng hạn được A(1.3)+B(1.3)<>B(4.6)+A(4.6):D
-Cân A(1.3) với A (4.6) nếu ko bằng nhau thì có nghĩa là đv giả thuộc Nhóm A(1.6)=> nó nhẹ hơn đv thật => nó thuộc nhóm A và ở phần nhẹ hơn ở 1 trong 2 vế của :Rightarrow, cân 2 đv bất kì của nhóm đó ta tìm được đồng vàng giả.
Nếu kết quả là bằng nhau thì đv giả thuộc nhóm B, nặng hơn đv thật và nó thuộc nhóm nằm ở vế nặng hơn của :D, cân 2 đv bất kì nhóm đó ta được đv giả.
Vậy ta hoàn thành nhiệm vụ 2.
-Nhiệm vụ 4 thì...để lại đã vì ...chưa đến tuổi lấy vợ :Rightarrow ,đành nhường lại cho mấy anh,hihi.(Máy của em bi lỗi sẽ post NV3 sau :D)

Bài viết đã được chỉnh sửa nội dung bởi kyoshiro_hp: 23-08-2006 - 22:55

Tạm biệt toán, tạm biệt diễn đàn.

#3
emvaanh

emvaanh

    Thượng sĩ

  • Thành viên
  • 206 Bài viết
Mệnh để trong nhiệm vụ 4 sai với n>3. Đáp số đúng phải là [3^n/2]=(3^n-1)/2=f(n) với mọi n>1
Hướng dẫn tí nhé.
Với n=2, f(n)=4 khỏi bàn. cách chia là 1,1,2
Với n=3, f(n)=13 .Cách chia 4,4,5
Với n=4, f(n)=40 . Cách chia là 13,13,14
Để CM được điều này thì truớc hết hãy CM muốn tìm được đồng vàng thật thì sớ vàng phải <=f(n).Điều này không khó.
Để có cách cân cho số vàng =f(n) thì chia nó thành 3 nhóm f(n-1),f(n-1),f(n-1)+1
Vài dòng thế thôi.
Everything having a start has an end.

#4
kyoshiro_hp

kyoshiro_hp

    Thượng sĩ

  • Thành viên
  • 202 Bài viết
C/m cho NV 3 thì rõ là quá dễ (chỉ dùng qui nạp)và thấy bài của anh emvaanh thì ko cần post làm gì nữa. Nhưng vì tư duy co hạn anh có thể chỉ cho em làm thế nào mà x/đ được đồng vàng giả trong 40 đồng và tại sao số vàng >f(n) thì ko thể tìm được? Thanks
Tạm biệt toán, tạm biệt diễn đàn.

#5
Kimluan

Kimluan

    Thượng sĩ

  • Thành viên
  • 226 Bài viết

Em xin giải 3 NV đầu thế này ạ:
NV 1 thì hình như đã có ở phần THCS :Rightarrow nên thôi ( làm luôn NV2 chứ 13 đồng thì bõ bèn gì :Rightarrow)
- Ta chia 37 đồng vàng thành 3 nhóm A(1.12),B(1.12),C(1.13).
-Đem cân A với B , nếu A=B thì trở thành bài toán 1 (công nhận ko cm hehe)
.Nếu A<B chẳng hạn, ta chia A lần lượt ra thành 4 nhóm A(1.3),A(4.6),A(7.9),A(10.12),tương tự với B
-Đem cân chéo bất kì chẳng hạn được A(1.3)+B(1.3)<>B(4.6)+A(4.6):Rightarrow
-Cân A(1.3) với A (4.6) nếu ko bằng nhau thì có nghĩa là đv giả thuộc Nhóm A(1.6)=> nó nhẹ hơn đv thật => nó thuộc nhóm A và ở phần nhẹ hơn ở 1 trong 2 vế của :D, cân 2 đv bất kì của nhóm đó ta tìm được đồng vàng giả.
Nếu kết quả là bằng nhau thì đv giả thuộc nhóm B, nặng hơn đv thật và nó thuộc nhóm nằm ở vế nặng hơn của :D, cân 2 đv bất kì nhóm đó ta được đv giả.
Vậy ta hoàn thành nhiệm vụ 2.
-Nhiệm vụ 4 thì...để lại đã vì ...chưa đến tuổi lấy vợ :Rightarrow ,đành nhường lại cho mấy anh,hihi.(Máy của em bi lỗi sẽ post NV3 sau :in)

he trình bày y chang "rừng xà nu" khó kiểm tra we', mà hình như nhiều hơn 4 lần cân rùi thì phải :D
13 đồng bõ bèn gì thì bạn cứ trình bày kĩ ra đi, mức độ từ dễ đến khó mừ. Nhớ ghi rõ ràng ra nhé, đọc mỏi con mét lém :D

#6
Kimluan

Kimluan

    Thượng sĩ

  • Thành viên
  • 226 Bài viết

Mệnh để trong nhiệm vụ 4 sai với n>3. Đáp số đúng phải là [3^n/2]=(3^n-1)/2=f(n) với mọi n>1
Hướng dẫn tí nhé.
Với n=2, f(n)=4 khỏi bàn. cách chia là 1,1,2
Với n=3, f(n)=13 .Cách chia 4,4,5
Với n=4, f(n)=40 . Cách chia là 13,13,14
Để CM được điều này thì truớc hết hãy CM muốn tìm được đồng vàng thật thì sớ vàng phải <=f(n).Điều này không khó.
Để có cách cân cho số vàng =f(n) thì chia nó thành 3 nhóm f(n-1),f(n-1),f(n-1)+1
Vài dòng thế thôi.

Có lẽ đây là một đáp số đúng, để tối nay về em chứng minh điều này thử xem, rất cảm ơn anh nhé :D

#7
Kimluan

Kimluan

    Thượng sĩ

  • Thành viên
  • 226 Bài viết

Mệnh để trong nhiệm vụ 4 sai với n>3. Đáp số đúng phải là [3^n/2]=(3^n-1)/2=f(n) với mọi n>1
Hướng dẫn tí nhé.
Với n=2, f(n)=4 khỏi bàn. cách chia là 1,1,2
Với n=3, f(n)=13 .Cách chia 4,4,5
Với n=4, f(n)=40 . Cách chia là 13,13,14
Để CM được điều này thì truớc hết hãy CM muốn tìm được đồng vàng thật thì sớ vàng phải <=f(n).Điều này không khó.
Để có cách cân cho số vàng =f(n) thì chia nó thành 3 nhóm f(n-1),f(n-1),f(n-1)+1
Vài dòng thế thôi.

Em đã chứng minh được trong n lần cân có thể lọc được đồng vàng giả từ http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{3^n-1}{2} (http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{3^n-1}{2} đồng vàng

Xin mời các bạn cùng ra tay giải quyết mệnh đề trên, đặt biệt rất hân hạnh được mời riêng anh emvaanh một lần nữa biểu lộ chút "thần công" để giải quyết vấn đề nan giải này (tất nhiên nan giải chỉ là đối với em :)).

Bài viết đã được chỉnh sửa nội dung bởi Kimluan: 26-08-2006 - 18:37


#8
kyoshiro_hp

kyoshiro_hp

    Thượng sĩ

  • Thành viên
  • 202 Bài viết
Em cũng đã c/m được có thể tìm đồng vàng giả trong, nói chung là ko khó , tuy nhiên ko biết làm thế nào thì ko giống ''rừng xà nu'' :).Mà đã có kết quả này rồi thì mấy trường hợp nhỏ bỏ qua luôn đi :D. Nhưng c/m cái mệnh đề thì bó tay :Leftrightarrow, anh emvaanh chỉ bảo thêm chút chứ ạ !
Tạm biệt toán, tạm biệt diễn đàn.

#9
Kimluan

Kimluan

    Thượng sĩ

  • Thành viên
  • 226 Bài viết

Em cũng đã c/m được có thể tìm đồng vàng giả trong, nói chung là ko khó , tuy nhiên ko biết làm thế nào thì ko giống ''rừng xà nu'' :perp.Mà đã có kết quả này rồi thì mấy trường hợp nhỏ bỏ qua luôn đi :perp. Nhưng c/m cái mệnh đề thì bó tay :perp, anh emvaanh chỉ bảo thêm chút chứ ạ !

Đúng là cái này khó trình bày thật, mà thôi cũng không cần trình bày cho tốn công, chỉ cần làm và thấy hay là được rồi.
Mấy cái bài lẽ tẻ cho qua đi nhé.Bây giờ chúng ta thử công phá mệnh đề trên thử xem, chỉ cần đường hướng không cần chi li. Bạn nào có ý gì thì cứ pót cả lên đừng ngại gì hết :D

#10
emvaanh

emvaanh

    Thượng sĩ

  • Thành viên
  • 206 Bài viết
Ý tương giải quyết là thế này:
Trước hết, xét bài toán trong trường hợp nếu biết đống giả nhẹ hơn đống thật Khi đó với $n$ lần cân cho ta một bộ gồm $n$ trạng thái, mỗi trạng thái có 3 giá trị. Suy ra có tất cả $3^n$ bộ như vậy.
Xét k là số sao cho với 1 đống giả và $k-1$ đống thật (nặng hơn đốn giả) qua $n$ lần cân ta có thể xác định được đống giả là đống nào. Khi đó có một đơn ánh từ tập các đống giả vào tập gồm $3^n$ bộ trạng thái nói trên. Suy ra $k\le 3^n$.

Với ý tưởng trên, trở về bài toán của ta, cho $k$ đống, có một đống giả ( không biết nặng hay nhẹ hơn đống thật), biết rằng có cách cân để sau $n$ lần cân ta xd được đống giả. Gọi $k_n$ là số lớn nhất trong các số $k$. Khi đó hãy cm chỉ xảy ra các trường hợp sau.
Trường hợp 1: Trong các cân tất cả các đống đều có xuất hiện. Khi đó đống giả sau khi được xác định ta sẽ biết chắc chắn rằng nó là nặng hay nhẹ hơn đống thật.
Bây giờ ta xét bộ ($a_1,a_2,...,a_k)$ trong đó $a_i=0$ nếu đống thứ $i$ thật và $-1$ nếu đống thứ $i$ là giả và nhẹ hơn( nặng hơn đống thật).
CÓ $2k$ bộ như vậy. Có một đơn ánh từ $2k$ bộ này vào $3^n$ bộ trạng thái các cân, từ đó suy ra $k\le 3^n/2$
TRường hợp không xảy ra do $k_n$ lớn nhất: Có đúng một đống không xuất hiện trong lần cân (phải chú ý chỉ có tối đa một đống không xuất hiện trong các lần cân).
Everything having a start has an end.

#11
Kimluan

Kimluan

    Thượng sĩ

  • Thành viên
  • 226 Bài viết
anh emvaanh lí giải kĩ hơn một chút đi, khó hiểu quá (anh nhớ ghi dấu tiếng việt nhé)

#12
emvaanh

emvaanh

    Thượng sĩ

  • Thành viên
  • 206 Bài viết
Anh tưởng bài này nói thế là đã xong rồi chứ. Thôi kì này phá lệ giải quyết kĩ hơn vậy:
*) Bài toán giải quyết: Hãy tìm số đồng vàng lớn nhất, sao cho với $n$ lần cân
ta có thể tìm ra 1 đồng vàng giả.
Qui tắc cân: Bằng cân thăng bằng, mỗi lần đặt lên hai dĩa số đồng vàng bằng nhau.

+Bước 1: Giả sử với n lần cân xác định được 1 đv giả từ $k$ đồng vàng, ta CM rằng $k\le 3^{n-1}/2$
CM: Đánh các đồng vàng theo thứ tự $1,2,...,k$. Xét một cách cân sao cho dù dv giả ở vị trí nào ta cũng tìm ra được.
Vị trí i gọi là xấu nếu dv giả đặt ở đây ta sẽ tìm đựoc nhưng không biết năng hay nhe hơn thật
+TH1: Nếu không có vị trí xấu, đồng vàng giả sau khi xác định đều biết được là nặng hay nhẹ hơn dv thật. Như vậy từ$ 3^n$ 'bộ n trạng thái cân' phải xác định được $ 2k $'bô $ k$ tinh chất dv' suy ra $2k\le 3^n$
+TH2: Nếu có một số vị trí xấu. Khi đó để ý chỉ có đúng một vị trí xấu.
Giả sử có hai vị trí 1, 2 là xấu
-Khi đó dv 1, dv 2 không xuất hiện trong lần cân đầu. (Để ý lần cân đầu là như nhau bất chấp dv giả đặt ở đâu).
-Qui nạp: Trong hai trường hợp dv giả đặt ở vi trí 1 hay 2 , thì trong lần cân thứ k dv1, dv2 không xuất hiện, và luôn như nhau
-Suy ra trong th dv giả đặt ở vt 1 hay 2, thì cho mọi lần cân đều thăng bằng và đến lần cân cuối cũng có 2 đồng là dv1, dv2 chưa hề được đặt lên cân => không thể xác định đồng vàng giả
Như vậy ta đã CM chỉ có dúng một vị trí xấu.
Bây giờ nếu đánh giá như TH1 thì ta có$ 3^n$ 'bộ n trạng thái cân' phải xác định được $2k-1$ ( do có đúng một vị trí xấu) 'bô k tinh chất dv' suy ra $2k\le 3^n+1.$Đến đây không được như ta mong muốn, bây giờ ta giải quyết khéo hơn một tí.
Xét lần cân đầu đặt $x$ dv $a_1,..,a_x $với $x$ đồng vàng $b_1,...,b_x$, chừa lại $y$ đồng vàng $c_1,...c_y$ $(2x+y=n)$, trong đó có một vị trí xấu
+Cân thăng bằng cho ta $3^{n-1}$
'bộ n trạng thái cân', lúc này đồng giả ở các vị trí $c_1,...,c_y$ có đúng một vị trí xấu, cho ta $2y-1$ 'bô $k$ tinh chất dv'. Như vậy với $3^{n-1}$
'bộ $n$ trạng thái cân' phải xác định được $2y-1$ 'bô k tinh chất dv' suy ra $y\le (3^{n-1}+1)/2$
+Cân không thăng bằng cho ta $2.3^{n-1}$ 'bộ $n$ trạng thái cân', lúc này đồng vàng giả là thuộc $a_1,...,a_x,b_1,...,b_x$ còn $c_1,...,c_y$ là thật cho ta $4x$ 'bô $k$ tinh chất dv' (do không dv giả không ở vị trí xấu) ta suy ra $4x\le 2.3^{n-1}$ suy ra $2x\le 3^{n-1}-1$, do đó $2x+y\le (3^n-1)/2$

Ta vừa CM xong $k\le (3^n-1)/2$

Bước 2. Chỉ ra một cách cân với $(3^n-1)/2$ thì không khó. Phần này để ý hai kết quả
(a) Nếu trong tay có một đồng thật, thì ta có cách cân với $k=(3^n+1)/2$ (và đây cũng là lớn nhất, tuy nhiên phần CM $k\le (3^n+1)/2$ lại dơn giản hơn trên)
(b) Khi cân lệch thì phải tận dụng tối đa. Không thể quy nạp bình thường, mà phải không khéo, lấy một số viên bên cân này sáng bên kia, dồng thời lấy ra ngoài mộ số viên.

Nên kết thúc bài này ở đây thì hơn. Với những ý chính trên,mình cho rằng hễ dộng não là hiểu.
Sao càng ngày mình càng làm biến post bài quá???

Bài viết đã được chỉnh sửa nội dung bởi lehoan: 12-03-2008 - 06:13

Everything having a start has an end.




0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh