PDA

View Full Version : Bài toán dán sticker lên rubik



thomasblack
30-03-2009, 06:53 PM
Giả sử bạn có một khối rubik DIY 3x3x3 vừa mới lắp và chưa dán sticker. Bài toán đặt ra là nếu bạn dán từng miếng sticker (tất cả là 54 miếng ứng với 6 màu ở 6 mặt của rubik) một cách ngẫu nhiên lên đó thì xác suất để khối rubik có đúng màu là bao nhiêu % ?

(Sẽ "Thanks" cho những ai tham gia trả lời :D)

nghiavn
30-03-2009, 08:51 PM
Tạm thời nếu tính là mỗi sticker phải ở đúng vị trí ban đàu thì sẽ có !54 TH là 230,843,697,339,241,000,000,000,000,000,000,000,00 0,000,000,000,000,000,000,000,000,000,000,000
TH, thực ra sẽ ít hơn vì ko nhất thiết phải về vị trí ban đầu mà chỉ cần cùng màu trên một mặt là đc

nhatelecom
30-03-2009, 09:37 PM
Anh tính ra rồi đây, tính mệt chết
Công thức xác suất thu gọn lại là: [54*36*(8!)^2!*(9!)^4]/ 54!

Tính bằng Matlab ra được xác suất là: 2.3739 * 10^(-037) (quá bé)

Ghi chú: * là phép nhân, / là phép chia, ^ là mũ, ví dụ 2^4 = 16

nghiavn
31-03-2009, 11:11 AM
Anh nhatelecom có thể cho biết các giá trị trong biểu thức của anh tương ứng với mỗi cái j và tại sao lại thế đc ko
Anh thomas nợ mọi ng cái thanks kìa

nhatelecom
31-03-2009, 08:17 PM
Okay, mình sẽ giải thích tại sao mình có được công thức cuối cùng như thế này: [54*36*(8!)^2!*(9!)^4]/ 54!

Không mất tính tổng quát, giả sử mình dán hết 9 sticker của 1màu, sau đó mới dán sticker màu khác. Và mình sẽ dán theo thứ tự: trắng - vàng - đỏ - cam - lam - lục.
Mình kí hiệu sticker 1 là s1, ... sticker 54 là s54 nhé.

Ví dụ: Kí hiệu: S10: 2/3
nghĩa là khi dán sticker thứ 10 thì có 2 trường hợp có thể cho ra rubik đúng trong tổng số 3 trường hợp có thể. Nói cách khác, khi dán sticker 10, ta có 3 cách dán, và 2 cách cho ra rubik đúng, 1 cách cho ra rubik sai, do đó xác suất đúng là 2/3
(Số 2/3 chỉ là ví dụ thôi nhé!)


Sticker màu trắng
s1: 54/54 (vì là sticker đầu tiên nên dán ở đâu cũng được)
s2: 8/53 (có 8 vị trí đúng trên cùng 1 mặt trong tổng số 53 vị trí)
s3: 7/52 ...
s4: 6/51
s5: 5/50
s6: 4/49
s7: 3/48
s8: 2/47
s9: 1/46

Nhân các số trên với nhau ta có xác suất để 9 miếng trắng cùng 1 mặt là:
A1 = 54 * 8! * 45!/ 54!

Sticker màu vàng:
màu vàng thì phải đối xứng với trắng, do đó chỉ có 9 trường hợp đúng cho s10 trong tổng số 45 trường hợp (các s11,s12 xét tương tự). Ta có: xác suất để dán đúng 18 sticker đầu tiên là:

A2 = A1 * (9!*36!)/45! = 54 * 8! * 45!/(54!) *(9!*36!)/45!
A2 = 54 * 8! /(54!) *(9!*36!) = 54 * 8! *9! * 36! / 54!

Sticker màu đỏ
Ta thấy lúc này màu vàng và trắng đã được dán xong, và nếu chúng ở vị trí đúng thì chúng sẽ đối diện nhau. Như vậy với sticker đầu tiên của màu đỏ, ta có thể dán vào bất kì vị trí nào trong 36 vị trí còn lại.
s19: 36/36
s20: 8/35
s21: 7/34
s22: 6/33
s23: 5/32
s24: 4/31
s25: 3/30
s26: 2/29
s27: 1/28

Xác suất hiện tại là:
A3 = A2 * 36 * 8! * 27! / 36!
A3 = 54 * 8! *9! * 36! /(54!) * 36 * 8! * 27! / 36!
A3 = 54 * 8! *9! /(54!) * 36 * 8! * 27!

Viết lại cho đẹp ^_^ : A3 = 36 * 54 * 8! * 8! *9! * 27! / (54!)


Sticker màu cam
Màu cam thì phải đối xứng với đỏ, do đó có 9 vị trí đúng để dán sticker cam đầu tiên (s28) trong tổng số 27 trường hợp. Và cứ xét tương tự như thế ta có

Xác suất hiện tại
A4 = A3 * 9! * 18! / 27!
A4 = 36 * 54 * 8! * 8! *9! *9! * 18! / (54!)

Sticker màu lam (hay có thể là màu xanh đậm, blue)
Dán sticker này khá quan trọng. Đối với các bạn chưa dán sticker lần nào, khi đến giai đoạn này, có thể nghĩ là còn 2 mặt nữa, dán màu BLUE ở đâu cũng như nhau. Nhưng các bạn hãy cầm cục rubik của mình lên, đặt mặt Trắng là UP, Đỏ là FRONT, thì màu xanh đậm phải nằm ở RIGHT mới là đúng. Do đó, với bài toán này ta chỉ có 9 vị trí đúng cho sticker blue đầu tiên (s37).
Xét tương tự như trường hợp của vàng và cam, ta có xác suất đến thời điểm hiện tại là:

A5 = A4 * 9! *9! / 18!
A5 = 36 * 54 * 8! * 8! *9! *9! *9! *9! / (54!)

Sticker màu lục (green)
Còn 9 cái sticker màu green, và còn đúng 9 vị trí để dán, thế thì dán kiểu gì cũng đều đúng cả, xác suất đúng của phần này = 1 (100% đúng)

Vậy xác suất cuối cùng cho bài toán dán sticker là
A6 = A5 * 1
= 36 * 54 * 8! * 8! *9! *9! *9! *9! / (54!)

Nếu công thức trên khó nhìn, các bạn có thể xem trên file mình gửi kèm

Nếu ai thấy mình sai thì góp ý nhé! ^_^

nghiavn
31-03-2009, 09:32 PM
Em chưa xem chi li nhưng cách lí luận có vẻ đúng, quyết định donate cho anh $10

nhatelecom
31-03-2009, 10:24 PM
@ nvt_zion: Học sinh lớp 11 cũng chưa chắc đã hiểu đâu. Anh học cái này năm lớp 12. Hi vọng có bạn nào chuyên Toán, hoặc bạn NghiaVN sẽ hiểu ^^

@ nghiavn: cảm ơn em nhé, keke.

thomasblack
01-04-2009, 12:13 AM
OK, mình đã xem sơ qua lập luận trong lời giải của anh nhatelecom và thấy khá ổn. Còn đáp số anh nhatelecom đưa ra thì hoàn toàn trùng khớp với đáp số của mình. Xin tặng anh nhatelecom 2 thanks và tặng nghiavn 1 thanks khích lệ.

Còn đây là cách giải của mình (có hơi khác :D) :

Ta chia bài toán làm 2 phần :

1. Tính khả năng để rubik có sticker được dán đúng quy ước (không cần đúng màu - hiểu nôm na là có được khối rubik đang bị xáo trộn và có thể giải được)

2. Tính khả năng để rubik có đúng màu (nghĩa là đã được giải)

Như vậy, ta thấy rằng đáp số của bài toán sẽ là : xác suất của (1) x xác suất của (2) (các bạn tự lí giải vì sao nhé :))

Ta đã biết khối rubik 3x3x3 (hợp lệ) sẽ có 43252003274489856000 trạng thái tất cả (có thể có 8! cách sắp xếp các khối ở cạnh, 7 khối có thể được xoay tùy ý vì chiều của khối thứ 8 phụ thuộc 7 khối còn lại; tạo ra 3⁷ hoán vị. Các khối ở cạnh có 12!/2 hoán vị. Xem chiều của 1 khối ở cạnh là cố định, chiều của 11 khối có thể độc lập với nhau; tạo ra 2¹¹ hoán vị - trích từ Wikipedia)

=> Xác suất của (2) là 1/43252003274489856000

Bây giờ ta đi tìm xác suất của (1).

Dễ thấy là khối rubik có sticker được dán đúng quy ước sẽ là khối rubik có màu của sticker được dán nằm ở 1 trong 43252003274489856000 trạng thái có thể có của nó.

Nhưng con số trạng thái 43252003274489856000 là chỉ xét khi ta cầm rubik theo một hướng cố định, nghĩa là các tâm nằm ở vị trí cố định. Trong khi đó, với cách dán sticker của đề bài thì các tâm có thể thay đổi theo màu sticker. Tuy nhiên, số khả năng vị trí của các tâm không phải là 6! vì các tâm phải nằm đối nhau theo đúng quy ước. Vì vậy, con số này sẽ phải là 24.

Giải thích lí do đưa đến con số 24 : Xét một mặt bất kỳ, giả sử mặt UP, có 6 cách chọn màu tâm cho nó. Kế đến là mặt DOWN, chỉ có 1 cách chọn màu tâm cho nó mà thôi, đó là màu đối diện với màu của mặt UP theo quy ước. Tiếp theo là mặt LEFT sẽ có 4 cách chọn màu tâm cho nó vì 4 hướng không quan trọng. Đến mặt RIGHT thì lại chỉ có 1 cách chọn màu tâm cho nó mà thôi (là màu đối diện với màu của mặt LEFT theo quy ước). Tương tự thì mặt FACE sẽ có 1 cách chọn, mặt BACK cũng là 1 cách chọn. Và ta có : 6x1x4x1x1x1 = 24 :D.

Mà 9 sticker cùng một màu có thể hoán đổi vị trí cho nhau, lại có 6 màu tất cả => Có (9!)^6 khả năng cho sticker

Và có tất cả là 54! cách chọn cho 54 miếng sticker.

Từ đó, xác suất của (1) sẽ là (43252003274489856000 x (9!)^6 x 24) / 54!

Do vậy, ta đưa đến kết quả bài toán là :

[ (43252003274489856000 x (9!)^6 x 24) / 54! ] x [ 1/43252003274489856000 ] = [ (9!)^6 x 24 ] / 54!

Tính bằng Maple thì ra xấp xỉ 2.3739 x 10^(-37)

(hi vọng có người hiểu mình :()

nhatelecom
01-04-2009, 09:07 AM
Haha, đáp án của thomasblack giống hệt mình.
@ Quyền: Hồi cấp 3, ai mới học chẳng gà hả em. Cứ luyện nhiều sẽ thành thần thôi mà. Như anh xoay rubik 10 năm còn không bằng em học trong 6 tháng, keke
[hr]



Ta đã biết khối rubik 3x3x3 (hợp lệ) sẽ có 43252003274489856000 trạng thái tất cả (có thể có 8! cách sắp xếp các khối ở cạnh, 7 khối có thể được xoay tùy ý vì chiều của khối thứ 8 phụ thuộc 7 khối còn lại; tạo ra 3⁷ hoán vị. Các khối ở cạnh có 12!/2 hoán vị. Xem chiều của 1 khối ở cạnh là cố định, chiều của 11 khối có thể độc lập với nhau; tạo ra 2¹¹ hoán vị - trích từ Wikipedia)
=> Xác suất của (2) là 1/43252003274489856000


Thật sự là anh không hiểu cái số 43252003274489856000 em lấy ở đâu ra cả. Vì theo lập luận thì anh có phép tính tổng số trạng thái của 3x3x3 là
8! * 3^7 * 12! /2 * 2^11. Đáp số của phép tính này không bằng đáp số em đưa ra.

thomasblack
01-04-2009, 12:00 PM
Thật sự là anh không hiểu cái số 43252003274489856000 em lấy ở đâu ra cả. Vì theo lập luận thì anh có phép tính tổng số trạng thái của 3x3x3 là
8! * 3^7 * 12! /2 * 2^11. Đáp số của phép tính này không bằng đáp số em đưa ra.

Trên Wikipedia viết như vậy mà anh, mà cái 8! * 3^7 * 12! /2 * 2^11 của anh em tính bằng Maple nó cũng ra đúng là 43252003274489856000 mà. Anh xem lại nhé. Mà với cách tính của em thì con số này không quan trọng lắm, vì khi nhân 2 xác suất với nhau thì nó sẽ triệt tiêu nhau, em chỉ nêu ra cho chính xác thôi.


a thomas hình như đang chuẩn bị thi olimpic toán phải ko ?

Sai rồi em, anh đâu có thi Olympic gì đâu, chỉ học Toán cho vui mà thôi, làm gì đã có đủ trình độ đấy :D.

nghiavn
01-04-2009, 07:16 PM
Mà em xem lại thấy hình như có sai sót, chẳng hạn như 1 miếng s1 (trắng) thì có 54 TH, các viên từ s2-s9 có lần lượt 8-1 TH nên
A1 = 45 * 8! thôi
Mặt vàng, s10 có 9 TH, các s lần lượt từ 11-18 có lần lượt 8 về 1 TH nên
A2 = A1 * 9! hay
A2 = 45 * 8! * 9!
Mặt đỏ, s19 có 36 TH , các s từ 20-27 lại có từ 8-1 TH nên
A3 = A2 * 36 * 8!hay
A3 = 45 * 36 * 8! * 9! * 9* = 1620 * 8! * (9!)^2

Bây h tất cả 3 mặt còn lại đều đc xác định và các sticker trong đó đều có số TH xác định từ 9-1 nên
Số TH cho cả bài toán là
1620 *8! (9!)^5
Bài này em giải thik ko kĩ như anh nhatelecom nhưng vì đang dùng laptop bé tí ngại type lắm có j em edit lại sau

Em đang học lớp chuyên toán 1 của khối 7 trường Giảng Võ nè[hr]
Nhưng có lẽ bài trên sai, vì đây là bài toán tính xác suất em chịu

nhatelecom
02-04-2009, 09:32 AM
Anh giải thích lại cho NghĩaVN nè: em lý luận đúng nhưng em viết nhầm số 54 thành 45, và ở mặt đỏ, em tính ra có 36 * 8! cách, nhưng lại thế số thành 36 * 9! cách, nên kết quả cuối cùng của em sai.

Ở mặt trắng thì A1 phải bằng 54 * 8! chứ, (em viết là 45 * 8!)
Tương tự như thế mặt vàng ta có 9! cách dán
Mặt đỏ thì có 36 * 8! cách
3 mặt còn lại thì có 9!*9!*9! = (9!)^3 cách

Tích của tất cả là 54 * 36 * (8!)^2 * (9!)^4 = 24 * (9!)^6 (giống Thomasblack) cách dán đúng

Mà tổng số các hoán vị sticker có thể là là 54! cách, do đó ta sẽ lấy kết quả trên chia cho 54!, sẽ có xác suất dán đúng.

UMU
02-04-2009, 11:38 AM
Sticker màu trắng
s1: 54/54 (vì là sticker đầu tiên nên dán ở đâu cũng được)
s2: 8/53 (có 8 vị trí đúng trên cùng 1 mặt trong tổng số 53 vị trí)


Thực sự thì lớp 10 chưa được học toán xác suất Nhưng hình như em thấy lời giản của anh có vấn đề chút xíu.
Đồng ý là S1 muốn dán đâu thì dán:
Sau khi dán S1 vào 1 viên thì S2 muốn dãn ở đâu cũng dc, chỉ cần không phải viên đã dán S1 là được, ko phải chỉ có 8 case đâu. Do vậy:
- Nếu S1 dán vào Edge thì S2 có 54-2=52 TH (vì 1 viên Edge có 2 mặt)
- Nếu S1 dán vào Corner thì S2 có 54-3=51 TH (vì 1 Corner có 3 mặt)
- Nếu S1 dán vào Center thì S2 có 54-1 =43 TH (vì 1 Center có 1 mặt)
Vậy là kết quả của anh chưa thật đúng :D
Em chỉ giỏi chỉ lỗi sai của người khác thôi, còn tính tiếp thì chịu hihi

thomasblack
02-04-2009, 12:05 PM
Sai rồi UMU, anh nhatelecom đang xét s1 -> s9 là sticker màu trắng mà, cho nên s1 đã dán vào mặt nào rồi thì s2 cũng phải dán vào mặt đó chứ, như vậy mới ra đúng màu được, miễn là không trùng với vị trí đã dán s1 là được.

nghiavn
02-04-2009, 12:05 PM
Chưa đọc kĩ nhưng sau lời nhận xét của anh nhatelecom, em xin giải lại như sau
Trắng: s1 dán đâu thì dán, 54TH, s2-9 như trên
A1 = 54 x 8!
Vàng: s10-18 có lần lượt từ 9 TH
A2 = 54 x 8! x 9!
Đỏ: s19 có 36, s20-27 có lần lượt từ 8 nên
A3 = 54 x 8! x 9! x 36 x 8!
A3 = 1944 x (8!)^2 x 9!
Cam: như vàng
A4 = 1944 x (8!)^2 x (9!)^2
Xanh và xanh lá cũng tương tự vậy kết quả cuối là
A = 1944 x (8!)^2 x (9!) ^4
A = 1944 x 1.625.702.400 x 15.906.579.537.576.591.360.000
A = 2.585.936.453.002.915.475.777.126.000.000 x 1944 và đoạn cuối em ko tính đc do nó to quá, ra error
Em khác anh nhatelecom ở chỗ có mấy cái là 8!

UMU
02-04-2009, 10:44 PM
Sai rồi UMU, anh nhatelecom đang xét s1 -> s9 là sticker màu trắng mà, cho nên s1 đã dán vào mặt nào rồi thì s2 cũng phải dán vào mặt đó chứ, như vậy mới ra đúng màu được, miễn là không trùng với vị trí đã dán s1 là được.

vì mới chỉ dán màu trắng, các ô còn lại là chưa có màu => sau khi dán s1 vào 1 mặt, ta dán s2 ở 1 viên ở 1 mặt bất kỳ rồi xoay nó lên mặt đã dán s1 vẫn đúng màu dc mà, đúng ko anh thomasblack ?? Vì vậy ko phải chỉ có 8 chỗ để dán s2 để rubik đúng màu :D ko thì mọi người cứ lấy cục DIY dán thử là bit ngay mà :P

thomasblack
02-04-2009, 11:13 PM
Chà, biết ngay là UMU sẽ lại thắc mắc vậy mà. Cái này nó là một phương pháp khá hữu dụng trong giải quyết các bài toán tổ hợp. Nghĩa là để bài toán đơn giản, anh nhatelecom chia bài toán thành 54 phần, ứng với 54 sticker mà xét cách dán từng sticker để có được 6 màu đúng. Anh nhatelecom sẽ tính xác suất của mỗi sticker rồi nhân chúng lại với nhau. Giải thích thì lằng nhằng lắm (chắc cũng do kiến thức của mình chưa sâu lắm nên không nói rõ ràng được :(), UMU nếu có điều kiện thì chịu khó xem một số sách về vấn đề này sẽ rõ (hình như là SGK Giải tích 12 có thì phải).

UMU
02-04-2009, 11:39 PM
hì hì, vậy thì khoản này em chịu rồi :D phải đọc thêm tài liệu về toán tổ hợp mới dc:shy:

lacthan77
03-04-2009, 11:47 AM
Em tính cách này xem có đúng không nha!

*Ta có 54 sticker ứng với 54 chổ của nó, vậy ta có 54! số trường hợp xảy ra khi ta gắn sticker vào (coi như các sticker trùng màu đc xếp vào các truờng họp khác nhau).
*Còn trường hợp gắn đúng sẽ là:(6!)^6(vì ở trên ta đã coi như các sticker trùng màu đc xếp vào các truờng họp khác nhau).
*Xác suất: [(6!)^6]/54!=(chưa tính ^_^)
Vậy có dc coi là đúng không vậy không anh! Nếu sai vậy tại sao vậy? phần tổ hợp xác suất này em dở lắm!

nhatelecom
03-04-2009, 08:40 PM
....
kết quả cuối là
A = 1944 x (8!)^2 x (9!) ^4
Em khác anh nhatelecom ở chỗ có mấy cái là 8!


Giải thích tiếp cho NghĩaVN:

Trông thì khác nhưng thực chất chỉ là một:
Đáp án ban đầu của anh là 54 x 36 x (8!)^2 x (9!)^4 / (54!)
Đáp án của Thomasblack là 24 x (9!)^6 / (54!)
Đáp án của NghĩaVN là 1944 x (8!)^2 x (9!)^4 / (54!)

Ta thấy 1944 = 54 x 36 . Vậy là đáp án của Nghĩa giống anh.
Ta lại có 54 x 36 = 6 x 9 x 4 x 9 = 24 x 9 x 9
Mà 8! x 9 = 1x2x3x4x5x6x7x8 x9 = 9!
nên 54 x 36 x (8!)^2 (9!)^4 = 24 x (9!)^2 x (9!)^ 4 = 24 x (9!)^6
Vậy nên đáp số của anh và của Thomasblack là như nhau cả.


@ UMU: Cách hiểu vấn đề của em lại giống với cách giải bài toán của Thomasblack. Còn với cách của anh, anh giả sử anh không xoay rubik, nên mới giải như vậy. 2 cách đều cho kq giống nhau, tuy nhiên em phải hiểu được tại sao rubik lại có tổng cộng hơn 4,3 x10^19 trạng thái như Thomasblak đã nói

ngogiuoc
14-06-2009, 06:00 PM
Đáp số 2.3739 x 10^(-37) đưa ra là chính xác, sau đây là cách làm khác của anh:
Có 54 vị trí, dán màu đầu tiên gôm 9 miếng, số trường hợp sảy ra là 54C9 ( theo máy fx casino, chứ còn sách giáo khoa là A hay P hay C gì đó a kô nhớ rõ T,T), xác xuất có 9 miếng cùng 1 mặt là 6/54C9 = 6/5 317 936 260
Vị trí màu đối, thứ 2, có xác xuất 1/45C9 = 1/886 163 135
Vị trí mặt bên màu thứ 3 là 4/36C9 = 4/94 143 280
Tương tự màu thứ 4,5,6 1/27C9 = 1/4 686 825 và 1/18C9 = 1/48 620 và 1/09C9 = 1/1

Do đó xác xuất đúng của mỗi mặt 1 màu theo đúng trạng thái giải song là 24/(54C9 x 45C9 x 36C9 x 27C9 x 18C9 x 09C9)
=1/8,424780185302038524265035197461x10^36 = 2,3739491785070207019820953173329 x 10^-37

còn nếu muốn tính trường hợp dán đúng, nhưng có thể bị xáo trộn, chưa giải, thì chỉ cần nhân thêm 43 252 003 274 489 856 000
thôi