Đến nội dung

Hình ảnh

Bài toán tháng 7/2014 - Trò chơi Rubik

* * * - - 5 Bình chọn pom

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

#21
ChinhLu

ChinhLu

    Binh nhất

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

Xuất phát từ chỗ này nhé!

Ta thấy rằng mỗi mặt Up và Left đều được xoay đi 105 lần (góc vuông) tương đương với $4\times 26+1$ góc vuông

Như vậy về màu sắc thì Rubik đã "chuẩn" nhưng ô ở tâm 2 mặt trên đều đã xoay đi $90^\circ$

 

Dựa vào việc xoay như trên, ta kỳ vọng một thuật toán đơn giản chỉ làm biến đổi ô giữa mặt đỏ xoay $180^\circ$

Dãy lệnh $L$ của ta sẽ chỉ chứa các thao tác $d_+$ (mặt đỏ xoay $90^\circ$) kết hợp với một mặt liên kết bất kỳ xoay $180^\circ$ ở đây là lấy mặt UP(ký hiệu là U).

Thực hiện $L=U_2d_+$ đúng 30 lần khi đó: mặt U xoay một số chẵn lần $180^\circ$ nên có hướng không đổi. Còn mặt đỏ xoay $7\times 4+2$ = 7,5 vòng nên mũi tên có hướng ngược lại. Các mặt khác không liên quan!

Thuật toán có thể thực nghiệm dễ dàng, thế nhưng để chứng minh $L=U_2d_+$ sẽ tuần hoàn (theo bổ đề c) và có chu kỳ $T=4n+2$ thì mình chịu!

Mình xin cung cấp thêm một cách xoay nữa ngắn hơn các của bạn hxthanh:

 

(R U Ri U) xoay đúng 5 lần. U (mặt đỏ) xuất hiện 10 lần nên mũi tên đổi chiều, R và Ri xuất hiện cùng nhau nên mũi tên mặt R không đổi hướng. Giống như khi bạn hxthanh xoay 2 vòng vậy (nhưng làm vậy hơi lâu). 

 

Nguyên bản nằm ở đây:  http://www.speedsolv...be-Center-piece

Mình xoay thử rồi và chính xác. 



#22
Nxb

Nxb

    Thiếu úy

  • ĐHV Toán học Hiện đại
  • 679 Bài viết

Khi đó nếu ta áp dụng thuật toán $L$ cho Rubik vô hướng (nghĩa là không có mũi tên) thì ta cũng thu được ánh xạ đồng nhất. Như vậy $L$ là một phép hoán vị chẵn. Bên cạnh đó các mũi tên ở các mặt khác giữ nguyên hướng. Tức là số lần xuất hiện các $x_i\neq D$ trong $L$ là số chẵn. 

Có lẽ chỗ lập luận này cần nói rõ hơn, không phải ai cũng nhìn ra tại sao $L$ chẵn thì phải có một số chẵn lần các $x_i$ xuất hiện? Ví dụ có người bảo lẻ lần vẫn được thì bạn trả lời thế nào.


Bài viết đã được chỉnh sửa nội dung bởi Nxb: 08-07-2014 - 07:48


#23
ChinhLu

ChinhLu

    Binh nhất

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

Có lẽ chỗ lập luận này cần nói rõ hơn, không phải ai cũng nhìn ra tại sao $L$ chẵn thì phải có một số chẵn lần các $x_i$ xuất hiện? Ví dụ có người bảo lẻ lần vẫn được thì bạn trả lời thế nào.

Mỗi $x_i$ là một hoán vị lẻ. Tích của một số chẵn các hoán vị lẻ là một hoán vị chẵn. Tích của một hoán vị lẻ và một hoán vị chẵn là một hoán vị lẻ. Mỗi $x_i\neq D$ xuất hiện một số chẵn lần trong $L$ vì mũi tên không đổi chiều. Từ đó suy ra $D$ cũng vậy.



#24
Nxb

Nxb

    Thiếu úy

  • ĐHV Toán học Hiện đại
  • 679 Bài viết

Mỗi $x_i$ là một hoán vị lẻ. Tích của một số chẵn các hoán vị lẻ là một hoán vị chẵn. Tích của một hoán vị lẻ và một hoán vị chẵn là một hoán vị lẻ. Mỗi $x_i\neq D$ xuất hiện một số chẵn lần trong $L$ vì mũi tên không đổi chiều. Từ đó suy ra $D$ cũng vậy.

Đấy, ý mình là tại sao $x_i$ lại lẻ, bạn nên tính ra cho mọi người thấy.



#25
ChinhLu

ChinhLu

    Binh nhất

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

Đấy, ý mình là tại sao $x_i$ lại lẻ, bạn nên tính ra cho mọi người thấy.

Mỗi $x_i$ là một hoán vị kiểu (1,2,3,4) biến thành (2,3,4,1). Có tổng cổng 3 lần inversion nên là lẻ. 



#26
Nxb

Nxb

    Thiếu úy

  • ĐHV Toán học Hiện đại
  • 679 Bài viết

Mỗi $x_i$ là một hoán vị kiểu (1,2,3,4) biến thành (2,3,4,1). Có tổng cổng 3 lần inversion nên là lẻ. 

Bạn đang nói hoán vị lẻ trên tập nào vậy, ý bạn là $x_i=(1234)$ nếu thế thì bạn xét $id$ trên đâu, bởi nếu thế thì nó không phải phép đồng nhất vì nó chỉ đồng nhất vị trị chứ hướng không đồng nhất hướng. Bạn nên chỉ ra nó lẻ trên tập nào. 


Bài viết đã được chỉnh sửa nội dung bởi Nxb: 08-07-2014 - 15:08


#27
ChinhLu

ChinhLu

    Binh nhất

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

Bạn đang nói hoán vị lẻ trên tập nào vậy, ý bạn là $x_i=(1234)$ nếu thế thì bạn xét $id$ trên đâu, bởi nếu thế thì nó không phải phép đồng nhất vì nó chỉ đồng nhất vị trị chứ hướng không đồng nhất hướng. Bạn nên chỉ ra nó lẻ trên tập nào.


Minh xet tap cac vi tri thoi. Khong tinh mui ten

#28
Nxb

Nxb

    Thiếu úy

  • ĐHV Toán học Hiện đại
  • 679 Bài viết

Minh xet tap cac vi tri thoi. Khong tinh mui ten

$x_i$ là phép quay mặt, thế sao lại chỉ là $(1234)$ được.


Bài viết đã được chỉnh sửa nội dung bởi Nxb: 08-07-2014 - 15:13


#29
ChinhLu

ChinhLu

    Binh nhất

  • Thành viên
  • 38 Bài viết
Ah.minh tinh cac canh ma thoi. Vi canh va goc khong doi cho nhau duoc ma. Moi mat co 4 canh ( la cai o giua noi 2 mat voi nhau)

#30
Nxb

Nxb

    Thiếu úy

  • ĐHV Toán học Hiện đại
  • 679 Bài viết

Ah.minh tinh cac canh ma thoi. Vi canh va goc khong doi cho nhau duoc ma. Moi mat co 4 canh ( la cai o giua noi 2 mat voi nhau)

Kiểu này mình với bạn hiểu hoàn toàn khác nhau rồi. Nếu thế thì phép biến đổi rubik của bạn đâu có đồng nhất.



#31
ChinhLu

ChinhLu

    Binh nhất

  • Thành viên
  • 38 Bài viết
Tai sao nhi?
Neu phep L la dong nhat thi khi han che L len tap con gom vi tri cac canh ( hoac dinh) thi L van la dong nhat ma.

#32
Nxb

Nxb

    Thiếu úy

  • ĐHV Toán học Hiện đại
  • 679 Bài viết

Tai sao nhi?
Neu phep L la dong nhat thi khi han che L len tap con gom vi tri cac canh ( hoac dinh) thi L van la dong nhat ma.

Mặt giữa có các cạnh không đứng yên bạn ạ.



#33
ChinhLu

ChinhLu

    Binh nhất

  • Thành viên
  • 38 Bài viết
Thoi noi cac dinh cho de hinh dung nhe. Co 8 dinh. Moi phep xoay mat se la hoan vi le cua 4 vi tri , 4 vi tri khac dung yen. Nhu vay la phep xoay mat la mot hoan vi le dung k?

#34
Nxb

Nxb

    Thiếu úy

  • ĐHV Toán học Hiện đại
  • 679 Bài viết

Thoi noi cac dinh cho de hinh dung nhe. Co 8 dinh. Moi phep xoay mat se la hoan vi le cua 4 vi tri , 4 vi tri khac dung yen. Nhu vay la phep xoay mat la mot hoan vi le dung k?

Thế được rồi, Nhưng vấn đề không phải chẵn hay lẻ đâu bạn, nó chẵn cũng được tùy vào tập ta xét. Không hiểu bạn có hiểu tại sao mình hỏi vậy nữa không.


Bài viết đã được chỉnh sửa nội dung bởi Nxb: 08-07-2014 - 18:58


#35
ChinhLu

ChinhLu

    Binh nhất

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

Thế được rồi, Nhưng vấn đề không phải chẵn hay lẻ đâu bạn, nó chẵn cũng được tùy vào tập ta xét. Không hiểu bạn có hiểu tại sao mình hỏi vậy nữa không.


Thuc su khong hieu ban muon noi gi o day nua? Ban co the noi ro hon khong?

#36
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết

Ý bạn Nxb muốn nói là nếu tồn tại một dãy lệnh trong đó các hoán vị là lẻ vẫn cho kết quả đồng nhất thì phải giải thích làm sao? Hay nói cách khác trường hợp a) có thể khả thi?



#37
ChinhLu

ChinhLu

    Binh nhất

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

Cảm ơn bạn hxthanh. 

 

Dãy $L=x_1...x_n$ cho ra kết quả đồng nhất thì $n$ phải là số chẵn vì mỗi $x_i$ là một hoán vị lẻ. Ở đây mình chỉ xét hoán vị của 8 phần tử là vị trí các gốc. Mỗi $x_i$ là một phép hoán vị lẻ như đã chứng minh ở trên.  Nếu $n$ lẻ thì tích của $n$ phép hoán vị lẻ vẫn là lẻ. Nhưng $L=id$ nên không thể lẻ được. 



#38
ChinhLu

ChinhLu

    Binh nhất

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

Mình xin cung cấp thêm một cách xoay nữa ngắn hơn các của bạn hxthanh:

 

(R U Ri U) xoay đúng 5 lần. U (mặt đỏ) xuất hiện 10 lần nên mũi tên đổi chiều, R và Ri xuất hiện cùng nhau nên mũi tên mặt R không đổi hướng. Giống như khi bạn hxthanh xoay 2 vòng vậy (nhưng làm vậy hơi lâu). 

 

Nguyên bản nằm ở đây:  http://www.speedsolv...be-Center-piece

Mình xoay thử rồi và chính xác. 

Van con mot thuat toan khac ngan hon: 

 

(URLUURiLi)^2 =Id

 

Mat U xoay 6 lan, cac mat khac giu nguyen.



#39
quanghs1020

quanghs1020

    Binh nhì

  • Thành viên mới
  • 16 Bài viết

Xuất phát từ chỗ này nhé!

Ta thấy rằng mỗi mặt Up và Left đều được xoay đi 105 lần (góc vuông) tương đương với $4\times 26+1$ góc vuông

Như vậy về màu sắc thì Rubik đã "chuẩn" nhưng ô ở tâm 2 mặt trên đều đã xoay đi $90^\circ$

 

Dựa vào việc xoay như trên, ta kỳ vọng một thuật toán đơn giản chỉ làm biến đổi ô giữa mặt đỏ xoay $180^\circ$

Dãy lệnh $L$ của ta sẽ chỉ chứa các thao tác $d_+$ (mặt đỏ xoay $90^\circ$) kết hợp với một mặt liên kết bất kỳ xoay $180^\circ$ ở đây là lấy mặt UP(ký hiệu là U).

Thực hiện $L=U_2d_+$ đúng 30 lần khi đó: mặt U xoay một số chẵn lần $180^\circ$ nên có hướng không đổi. Còn mặt đỏ xoay $7\times 4+2$ = 7,5 vòng nên mũi tên có hướng ngược lại. Các mặt khác không liên quan!

Thuật toán có thể thực nghiệm dễ dàng, thế nhưng để chứng minh $L=U_2d_+$ sẽ tuần hoàn (theo bổ đề c) và có chu kỳ $T=4n+2$ thì mình chịu!

 

P/s: Thuật toán của bạn ChinhLu đưa ra rất hay và ngắn! thế nhưng ... vẫn không ổn!

Đếm ra thì thấy mặt F xuất hiện tổng cộng 18 lần nghĩa là sẽ bị xoay đi 4,5 vòng và mũi tên sẽ bị đảo chiều :luoi:

Đúng thật hay tuyệt, cậu ấy giải được rùi







Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: pom

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

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