Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh
* * * - - 5 Bình chọn

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

pom

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

#21 ChinhLu

ChinhLu

    Binh nhất

  • Thành viên
  • 38 Bài viết
  • Giới tính:Nam
  • Đến từ:Pisa Italy
  • Sở thích:Football, chess

Đã gửi 08-07-2014 - 00:54

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

  • Thành viên
  • 536 Bài viết
  • Giới tính:Nam

Đã gửi 08-07-2014 - 06:42

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
  • Giới tính:Nam
  • Đến từ:Pisa Italy
  • Sở thích:Football, chess

Đã gửi 08-07-2014 - 14:03

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

  • Thành viên
  • 536 Bài viết
  • Giới tính:Nam

Đã gửi 08-07-2014 - 14:18

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
  • Giới tính:Nam
  • Đến từ:Pisa Italy
  • Sở thích:Football, chess

Đã gửi 08-07-2014 - 14:36

Đấ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

  • Thành viên
  • 536 Bài viết
  • Giới tính:Nam

Đã gửi 08-07-2014 - 15:06

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
  • Giới tính:Nam
  • Đến từ:Pisa Italy
  • Sở thích:Football, chess

Đã gửi 08-07-2014 - 15:10

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

  • Thành viên
  • 536 Bài viết
  • Giới tính:Nam

Đã gửi 08-07-2014 - 15:12

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
  • Giới tính:Nam
  • Đến từ:Pisa Italy
  • Sở thích:Football, chess

Đã gửi 08-07-2014 - 15:16

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

  • Thành viên
  • 536 Bài viết
  • Giới tính:Nam

Đã gửi 08-07-2014 - 15:20

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
  • Giới tính:Nam
  • Đến từ:Pisa Italy
  • Sở thích:Football, chess

Đã gửi 08-07-2014 - 15:22

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

  • Thành viên
  • 536 Bài viết
  • Giới tính:Nam

Đã gửi 08-07-2014 - 15:25

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
  • Giới tính:Nam
  • Đến từ:Pisa Italy
  • Sở thích:Football, chess

Đã gửi 08-07-2014 - 15:31

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

  • Thành viên
  • 536 Bài viết
  • Giới tính:Nam

Đã gửi 08-07-2014 - 18:46

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
  • Giới tính:Nam
  • Đến từ:Pisa Italy
  • Sở thích:Football, chess

Đã gửi 08-07-2014 - 19:32

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

  • Thành viên
  • 3327 Bài viết
  • Giới tính:Nam

Đã gửi 08-07-2014 - 20:10

Ý 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?


Cuộc sống thật nhàm chán! Ngày mai của ngày hôm qua chẳng khác nào ngày hôm qua của ngày mai, cũng như ngày hôm nay vậy!

#37 ChinhLu

ChinhLu

    Binh nhất

  • Thành viên
  • 38 Bài viết
  • Giới tính:Nam
  • Đến từ:Pisa Italy
  • Sở thích:Football, chess

Đã gửi 08-07-2014 - 20:31

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
  • Giới tính:Nam
  • Đến từ:Pisa Italy
  • Sở thích:Football, chess

Đã gửi 12-07-2014 - 18:46

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 q123456

q123456

    Lính mới

  • Thành viên
  • 1 Bài viết
  • Giới tính:Nam

Đã gửi 02-08-2014 - 17:44

câu c:

Theo mình thì giữ nguyên vị trí
g/s :mặt a là mặt đối diện,mặt trên là mặt b,mặt phải là mặt c, quy định chiều thay đổi góc theo chiều kim đồng hồ(+)

 Thực hiện liên tiếp dãy lệnh sau,kèm theo phải giữ mặt a đối diện :

   {c+,b-}

Khoảng 30 lần là xong thì phải.


Bài viết đã được chỉnh sửa nội dung bởi q123456: 02-08-2014 - 17:45

gia sưgia sutìm gia sư, tim gia sulàm gia sư, lam gia sugia sư toán, gia su toangia sư lý, gia su lygia sư hóa, gia su hoagia sư tiếng anh, gia su tieng anh, gia sư văn, gia su vangia sư tiếng việt, gia su tieng viet, gia sư tin, gia su ve, gia sư vẽgia sư luyện chữ, gia su luyen chugia su dan nhac, gia sư đàn nhạcgia su quan ba dinhgia su quan dong dagia su quan cau giaygia su quan hoan kiemgia su quan hoang maigia su quan hai ba trunggia su quan ha donggia su quan thanh xuangia su quan tay hogia su huyen tu liemgia su quan long biengia su huyen thanh trigia su huyen gia lam, gia sư quận ba đìnhgia sư quận đống đagia sư quận cầu giấygia sư quận hoàn kiếmgia sư quận hoàng maigia sư quận hai bà trưnggia sư quận hà đônggia sư quận thanh xuângia sư quận tây hồgia sư huyện từ liêmgia sư huyện thanh trìgia sư quận long biêngia sư huyện gia lâmgia sư toán lớp 1-12 ôn thi đại họcgia sư lý cấp 2, cấp 3gia sư hóa cấp 2, cấp 3gia sư văn cấp 2 cấp3gia sư tiếng anh 1-12gia sư tiếng việtgia sư cấp 1gia sư cấp 2gia sư cấp 3gia sư giỏigia su gioigia sư uy tíngia sư hà nộigia sư uy tín việt, gia su lop 12, gia sư lớp 12, Nữ giảng viên phải lòng cậu học trò nghèo, giúp con học giỏi, giup con hoc gioi, dạy tiếng anh cho trẻ em, day tieng anh cho tre em, gia sư tiểu học, gia su tieu hoc, học Hóa với gia sư tại nhà, hoc hoa voi gia su tai nha, hướng dẫn cách giải bài toán vecto lớp 10, huong dan cach giai bai toan vecto lop 10, Để con bạn giỏi Toán 8, de con ban gioi toan 8, cải thiện khả năng học Toán cho học sinh kém, cai thien kha nang hoc toan cho hoc sinh kem, bí quyết để học giỏi Toán hình 9, bi quyet de hoc gioi toan hinh 9, gia sư lớp 1, gia su lop 1, gia sư dạy lớp 5, gia su day lop 5, tìm gia sư dạy kèm học sinh lớp 8, tim gia su day kem hoc sinh lop 8, gia sư dạy học sinh lớp 7, gia su day hoc sinh lop 7, gia sư tiếng anh, gia su tieng anh, gia sư môn toán, gia su mon toan, gia sư uy tín, gia su uy tin, bí quyết tìm gia sư cho con, bi quyet tim gia su cho con, tieng anh, tiếng anh, phương pháp giải nhanh vật lý, phuong phap giai nhanh vat ly, gia sư uy tín việt, gia su uy tin viet, học tiếng anh, hoc tieng anh, làm gì để con học tốt, làm gì để con học tốt, gia sư giỏi luyện thi đại học, gia su gioi luyen thi dai hoc, ngữ pháp tiếng anh, ngu phap tieng anh, cần gia sư, can gia su


#40 quanghs1020

quanghs1020

    Binh nhì

  • Thành viên mới
  • 16 Bài viết
  • Giới tính:Nam
  • Đến từ:Bình Định
  • Sở thích:Học toán , tiếng anh

Đã gửi 16-07-2016 - 08:20

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

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

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