PDA

View Full Version : Bài toán về số trạng thái của rubik



thomasblack
30-03-2009, 07:27 PM
Hãy tính :

a. Số trạng thái có thể có của một khối rubik 3x3x3 bình thường ? (quá quen thuộc rồi nhỉ :D)
b. Số trạng thái có thể có của một khối rubik 3x3x3 nếu tính cả việc được quyền tháo các viên cạnh (edge) và góc (corner) ra và lắp lại ở vị trí tùy ý ?
c. Số trạng thái có thể có của một khối rubik 3x3x3 nếu tính cả việc được quyền tháo các viên cạnh (edge), góc (corner) và kể cả viên ở tâm (center) ra và lắp lại ở vị trí tùy ý ?

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

nghiavn
30-03-2009, 08:01 PM
a. Hình như khoảng 4,33 x 10^19
b. Theo CT của em thì là !12 x 2^12 + !8 x 3^8
c. Cái này thì như trên + !6

nhatelecom
30-03-2009, 09:09 PM
Rubik 3x3x3 phải giả thiết là chỉ dán 6 màu thôi, chứ không dán hình nhé.
Câu 1: câu này chịu, :D

Câu 2: Đồng ý với Nghiavn, có 12! x 2^12 + 8! x 3^8 = 5.1902 x 10^20 cách.

Câu 3: bằng đáp án câu 2 nhân thêm số trường hợp xếp tâm nữa (30 cách)
Do đó đáp án câu 3 sẽ là:
5.1902 x 10^20 x 30 = 1.55707 x 10^22

ngân
30-03-2009, 09:49 PM
theo mình vì các tâm có vai trò như nhau nên chỉ có 5!-(C2/5 + C2/3) cách đổi các tâm thôi (bài của nghiavn), không biết đúng vậy không :-?

nghiavn
31-03-2009, 11:19 AM
To anh nhatelecom: Cái câu b anh nhatelecom chắc chắn là sai, vì có 12 viên cạnh tất cả có 2 TH thì phải nhân với 2 mũ 12, góc thì phải là 3 mũ 8
To Mr.Jun: ! tức là giai thừa, !n là 1x2x3x4x....xn
To ngân: Còn bài của bạn Ngân (hoặc chị Ngân) mình ko hiểu
To anh Quyền: Công thức thì em tự chế, chỉ có cái giai thừa ("!") là em xem ké trên rung chuông vàng mới biết
To mọi ng, em xin giải thik cách làm của mình:
a. Em lấy từ wikipedia
b. !12 là có 12 viên góc, viên đầu tiên có thể đặt trong 12 vị trí, viên thứ 2 còn 11 vị trí và cứ thế đến viên cuối còn 1 vị trí, tổng TH là bằng 1x2x3x...x12 = !12.
2^12 là mỗi viên có 2 TH thuận nghịch, có 12 viên là nhân với 12 lần số 2 = 2^12
Tương tự với các viên góc
c. Có 6 viên góc nên mới là !6. Nhưng câu c của em có nhiều TH bị trùng nên ko thể nhiều thế đc, chỉ khi tính cả move xyz thì bài của em mới đúng

nhatelecom
31-03-2009, 03:55 PM
@Nghĩa VN: viết là 12! mới đúng, sao lại viết là !12 ???

Câu 2: Đồng ý với Nghĩa về đáp số câu 2. You're right!! ^^
Tính ra số: 12! x 2^12 + 8! x 3^8 = 5.1902 x 10^20

Câu 3 = đáp án câu 2 NHÂN với số trường hợp xếp tâm, không phải là CỘNG với số trường hợp của tâm đâu.

Theo mình tính được thì có 30 trường hợp xếp tâm. Do đó đáp án câu 3 sẽ là:
5.1902 x 10^20 x 30 = 1.55707 x 10^22

Lý giải tại sao lại có 30 cách xếp tâm: Không mất tính tổng quát, giả sử mình xếp tâm theo theo thứ tự là: trắng - vàng - đỏ - cam - lam - lục

- Tâm trắng: chọn chỗ nào cũng như nhau vì có tính đối xứng: 1 cách
- Tâm vàng: có 2 cách: đối xứng với vàng và kề với vàng.
Lý giải thêm: có 4 mặt kề với mặt trắng, nhưng dán màu vàng vào mặt nào cũng như nhau cả.

Vậy đến đây mình đã có: 1x2 = 2 trường hợp để dán 2 màu này rồi

Xét trường hợp 1: trắng và vàng đối xứng nhau
- Đỏ: dán mặt nào cũng như nhau - 1 cách
- Cam: 3 cách (vì còn 3 vị trí)
- Lam: 2 cách
- Lục: 1 cách

Số cách cho trường hợp 1 này là 3x2x1 = 6 cách

Xét trường hợp 2: trắng và vàng kề nhau

Lúc này do rubik đã mất tính đối xứng nên ta có
- Đỏ: 4 cách
- Cam: 3 cách
- Lam: 2 cách
- Lục: 1 cách

Số cách cho trường hợp 2 này là 4x3x2x1 = 24 cách

Tổng 2 trường hợp, cũng là tổng số cách xếp TÂM là: 24+6 = 30 cách

Do xếp tâm không phụ thuộc vào xếp cạnh và góc nên ta lấy số này nhân với đáp án câu 2 sẽ có đáp án như trên.

Có ai thấy mình sai ở đâu không?? ^_^

nghiavn
02-04-2009, 11:35 AM
Cách lí giải về TH tâm của anh nhatelecom khác em, nghĩ là tâm đầu tiên có 6 chỗ, cái tiếp theo có 5, cái cuối có 1, nhân tất lên sẽ ra 6!, còn nhân với số tâm hay cộng với số tâm thì em đang nghĩ

jackblk
02-04-2009, 12:55 PM
Câu c: 5.1902 x 10^20 x 30 = 1.55707 x 10^22, đồng ý với anh nhatelecom
câu a: 8! x 3^7 x ((12!x2^11)/2) với 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^7 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^11 hoán vị. Có tham khảo wiki sau khi tính
câu c: đồng ý với anh nhatelecom là x2 chứ không phải +2

brokenheart1991
20-05-2009, 12:55 PM
Xin chào các bạn. Sau đây mình xin giải thích cách tính số TH rubik 3x3 của mình:
Một khối 3x3 có tất cả 8 khối góc, 12 khối cạnh và 6 khối tâm. Tuy nhiên trong quá trình xoay rubik, chỉ có cạnh và góc làm ảnh hưởng tới số TH của khối mà thôi. Do vậy, ta chỉ cần xét số TH của cạnh và góc là đủ.
Mỗi góc của khối 3x3 có 3 màu => có thể có tới 3^8 TH lật góc. Tuy nhiên trên thực tế, khi 7 góc đã có trạng thái lật xác định thì góc còn lại chỉ có duy nhất 1 trạng thái => số trạng thái lật góc là 3^7 TH => số TH của góc (cả lật và hoán vị) là 3^7x8! TH.
Mỗi cạnh của khối 3x3 có 2 mầu => có thể có tới 2^12 Th lật cạnh. Tuy nhiên trên thực tế, khi 11 cạnh đã có trạng thái lật xác định thì cạnh còn lại cũng chỉ có duy nhất 1 trạng thái => số TH lật cạnh là 2^11 TH. Xét tiếp tới số hoán vị của cạnh. Khi các góc có vị trí xác định, thì cạnh thứ nhất có 12 vị trí đưa được vào, cạnh thứ hai có 11 vị trí,… Tuy nhiên 2 cạnh cuối chỉ có duy nhất 1 cách sắp xếp (nếu không sẽ sinh ra parity) => số Th của cạnh (cả lật và hoán vị) là: 2^11x12!:2 TH.
Tóm lại số Th của 3x3 là: (3^7x8!)x(2^11x12!:2)= 43252003274489856000 TH.
Chúc các bạn hiểu được cách tính trên và yêu thích cả toán lẫn rubik!
[font=Times New Roman]

nhatelecom
21-05-2009, 07:47 AM
@brokenheart1991: Cách của bạn chính xác, nhưng bài toán này đã có đáp án rồi :cool:

brokenheart1991
21-05-2009, 12:12 PM
@brokenheart1991: Cách của bạn chính xác, nhưng bài toán này đã có đáp án rồi :cool:

vậy mà vẫn có bạn giải sai đấy chứ. đa số các bạn không để ý tới trạng thái của góc cuối, cạnh cuối và parity nên kết quả thường gấp 12 lần so với thực tế

nhatelecom
21-05-2009, 01:13 PM
@brokenheart1991:
Bạn trung95 đã đưa ra đáp án đúng ngay trước bài viết của bạn. Mình chỉ không hiểu bạn dùng chương trình tính gì mà cho đến kết quả cuối cùng chuẩn như vậy. Vì mình dùng Matlab cũng chỉ cho kết quả là 4.325200327448986 x 10^19

nanotek2711
27-05-2009, 07:42 PM
câu cúi cùng theo em nhá .ta có 12 viên cạnh nên có 12! số trường hợp sắp xếp và 2^12 số trường hợp lật vậy fần cạnh là 12!*2^12. h tới góc thì ta có 8 góc nên có 8! trường hợp hoán vị, 3^8(góc có 3 trạng thái) trường hợp lật nên fần góc là 8!*3^8 còn fần center có 6 center nên có 6! trường hợp center hoán đổi, kết wả cuối cùng là 12!*2^12*8!*3^8*6!=373697308291592355840000 trường hợp ^^

brokenheart1991
28-05-2009, 04:30 PM
pm Nhatelecom: mình dùng chương trình calculator của Windows thôi, không có j` đặc biệt cả. Còn về việc trung95 đưa ra ĐA đúng trước mình thì có lẽ do mình không để ý, nhưng mình cũng chưa thấy ai có thể giải thích cách tính và đưa ra kết quả chính xác tuyệt đối được như mình. Nên chăng chúng ta dừng việc tranh luận về vấn đề này ở đây?

ngogiuoc
14-06-2009, 11:55 AM
@brokenheart1991: cách giải của e hay quá, rất ngắn gọn và dể hiểu.
câu c hoàn toàn đống ý với nhatelecom. câu b thì rõ ràng quá rồi.
vậy đến h có thể kết luận đáp số như sau:

câu a: 43 252 003 274 489 856 000

câu b: 519 024 039 293 878 272 000

câu c: 15 570 721 178 816 348 160 000