Đến nội dung


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ó 39 trả lời

#1 PSW

PSW

    Những bài toán trong tuần

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

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

Trò chơi và bài toán về rubik

 

Hân cầm cục rubik đưa cho Kiên và khoe: "Xem này tớ xoay đủ 6 mặt hết chưa đầy một phút!".

 

Kiên cầm cục rubik đã hoàn thành 6 mặt ngắm nghía hồi lâu rồi nghĩ ra một "kế". Kiên lấy bút vẽ lên tất cả các mặt của rubik mỗi mặt gồm những mũi tên cùng chiều ở mỗi ô, duy nhất mặt màu đỏ thì Kiên vẽ mũi tên ở ô chính giữa vuông góc với các mũi tên ở xung quanh (Xem hình a) rồi đem đố Hân làm sao xoay lại cho đúng chiều.

 

rubik.png

 

a) Hân có xoay rubik được theo yêu cầu của Kiên không? Vì sao?

 

b) Nếu Kiên vẽ mũi tên như hình b) thì Hân có xoay lại được không? Hãy chỉ cho Hân cách xoay rubik lại trong trường hợp này nếu bạn giải được!

 

c) Ta gọi các mặt rubik là $a,b,c,d,e,g$ mỗi phép xoay sẽ được ký hiệu là $+, - , 2$ và được viết như là chỉ số của mặt ("+" tương ứng với xoay $+90^{\circ}$, "-" là xoay $-90^{\circ}$ còn $2$ là xoay $180^{\circ}$). Ta được tập hợp mẫu $E$:

$$E=\{a_+,a_-,a_2,...,g_+,g_-,g_2\}$$

$L$ là một dãy hữu hạn các phần tử $L=\{x_1,x_2,...,x_k\}$ trong đó $x_i\in E, \forall i=\overline{1,k}$ được gọi là dãy lệnh

 

Chứng minh rằng tồn tại một số tự nhiên $n$ để sau khi áp dụng $n$ lần liên tiếp dãy lệnh $L$, rubik sẽ trở lại trạng thái ban đầu!


Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 01-09-2014 - 09:32

1) Thể lệ
2) Danh sách các bài toán đã qua: 1-100, 101-200, 201-300, 301-400
Còn chờ gì nữa mà không tham gia!  :luoi:
 


#2 gatoanhoc1998

gatoanhoc1998

    Hạ sĩ

  • Thành viên
  • 66 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT Chuyên Quốc Học Huế
  • Sở thích:Xem sách

Đã gửi 05-07-2014 - 10:30

câu c:

Theo kinh nghiệm thì giữ nguyên vị trí rubik (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-}

Mình nhớ là khoảng 20-30 lần là xong.

Chỉ ra trực tiếp như vậy có được không vậy?



#3 Nxb

Nxb

    Thiếu úy

  • ĐHV Toán học Hiện đại
  • 618 Bài viết
  • Giới tính:Nam

Đã gửi 05-07-2014 - 22:37

Mình chưa giải được hoàn toàn, nhưng có ý tưởng thế này và ít nhất giải được câu c.

 

Xét tập $A$ gồm 52.6 hình vuông dùng để đánh 6 hướng của 48 hình vuông không phải ở tâm và 4 hướng của 6 hình vuông ở tâm (vì khi quay luôn có 2 hướng trước sau không thay đổi nên không cần xét nữa). 

 

Xét nhóm đối xứng $S$ của tập $A$, và $a,b,c,d,e,g$ lần lượt là các phép quay góc $90$ độ theo chiều kim đồng hồ khi nhìn vào các mặt của các mặt $a,b,c,d,e,g$, ta có thể coi đây là các phần tử của S. Đặt $H=\left\{a,b,c,d,e,g\right\}$, do để quay khối rubik ta chỉ có thể thực hiên các phép này nên nhóm $<H>$ sinh bởi $H$ chứa tất cả các phép biến đổi của khối rubik.

 

Như vậy dãy lệnh $L$ là một phần tử của $<H>$ mà $L^{|<H>|}=id$ nên tồn tại số n thỏa mãn câu c. Nếu cần có thể chỉ ra một con số cụ thể. $L$ là một phần tử của $S$ nên ta có $L^{|S|}=id$ hay $L^{(52.6)!}=id$

 

P/S: Mình đã phải sửa lại khá nhiều cho ngắn và đúng hơn, bài giải trước có lỗi sai nghiêm trọng.


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


#4 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 07-07-2014 - 06:53

Đồng ý với cách giải của bạn Nxb (dùng lý thuyết nhóm). Mình trình bày cách chứng minh câu a và cách xoay cho câu b như sau.

 

Câu a: Ta nhìn thẳng vào ô màu đỏ và đánh số các ô theo như sau 

x 1 x

4 x 2

x 3 x

 

Giả sử rubik này giải được. Khi đó các mũi tên mặt bên phải hướng lên trên, mặt đáy hướng thẳng vào mắt.  

Như vậy ta phải thực hiện phép hoán vị (giữa 4 cạnh  1, 2, 3, 4 với nhau) như sau: (1234) biến thành (2413). Đây là một phép hoán vị lẻ và do đó không thể thực hiên qua các phép xoay rubik được. 

 

 

Câu b: Để tiện theo dõi ta đánh số các ô như sau:

 

1 2 3

4 5 6

7 8 9

 

Nếu rubik là "giải được" thì mũi tên ở mặt phải sẽ hướng vào phía mắt người quan sát, trong khi mũi tên ở mặt đáy hướng về bên trái. Từ đó suy ra ta phải làm các phép biến đổi sau (cố định mặt đỏ): 

 

Đổi 1 và 9 cho nhau, 3 và 7 cho nhau (nhưng không xoay măt đỏ đi chỗ khác, nghĩa là 9 ô trước măt ta vẫn là màu đỏ).

 

Đổi 2 và 8, 4 và 6 cho nhau (cũng giữ nguyên màu đỏ, như trên).

 

Trong rubik căn bản (6 màu, không có mũi tên) có thuật toán cụ thể để làm việc này (có thể xem trên website của Rubik). 



#5 hxthanh

hxthanh

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

Đã gửi 07-07-2014 - 08:23

Đồng ý với cách giải của bạn Nxb (dùng lý thuyết nhóm). Mình trình bày cách chứng minh câu a và cách xoay cho câu b như sau.

 

Câu a: Ta nhìn thẳng vào ô màu đỏ và đánh số các ô theo như sau 

x 1 x

4 x 2

x 3 x

 

Giả sử rubik này giải được. Khi đó các mũi tên mặt bên phải hướng lên trên, mặt đáy hướng thẳng vào mắt.  

Như vậy ta phải thực hiện phép hoán vị (giữa 4 cạnh  1, 2, 3, 4 với nhau) như sau: (1234) biến thành (2413). Đây là một phép hoán vị lẻ và do đó không thể thực hiên qua các phép xoay rubik được. 

 

 

Câu b: Để tiện theo dõi ta đánh số các ô như sau:

 

1 2 3

4 5 6

7 8 9

 

Nếu rubik là "giải được" thì mũi tên ở mặt phải sẽ hướng vào phía mắt người quan sát, trong khi mũi tên ở mặt đáy hướng về bên trái. Từ đó suy ra ta phải làm các phép biến đổi sau (cố định mặt đỏ): 

 

Đổi 1 và 9 cho nhau, 3 và 7 cho nhau (nhưng không xoay măt đỏ đi chỗ khác, nghĩa là 9 ô trước măt ta vẫn là màu đỏ).

 

Đổi 2 và 8, 4 và 6 cho nhau (cũng giữ nguyên màu đỏ, như trên).

 

Trong rubik căn bản (6 màu, không có mũi tên) có thuật toán cụ thể để làm việc này (có thể xem trên website của Rubik). 

Tiếc rằng các thao tác cơ bản để đổi "cạnh" lại làm thay đổi hướng ô "giữa" của các mặt xung quanh. :luoi:

Nếu chứng minh được sự đúng đắn của câu $c$ (xem như là một bổ đề) thì câu $b$ có thể lập luận và suy ra được lời giải với thuật toán (chỉ ra một dãy lệnh $L$ để thực hiện)


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!

#6 Nxb

Nxb

    Thiếu úy

  • ĐHV Toán học Hiện đại
  • 618 Bài viết
  • Giới tính:Nam

Đã gửi 07-07-2014 - 08:34

Đồng ý với cách giải của bạn Nxb (dùng lý thuyết nhóm). Mình trình bày cách chứng minh câu a và cách xoay cho câu b như sau.

 

Câu a: Ta nhìn thẳng vào ô màu đỏ và đánh số các ô theo như sau 

x 1 x

4 x 2

x 3 x

 

Giả sử rubik này giải được. Khi đó các mũi tên mặt bên phải hướng lên trên, mặt đáy hướng thẳng vào mắt.  

Như vậy ta phải thực hiện phép hoán vị (giữa 4 cạnh  1, 2, 3, 4 với nhau) như sau: (1234) biến thành (2413). Đây là một phép hoán vị lẻ và do đó không thể thực hiên qua các phép xoay rubik được. 

 

 

Câu b: Để tiện theo dõi ta đánh số các ô như sau:

 

1 2 3

4 5 6

7 8 9

 

Nếu rubik là "giải được" thì mũi tên ở mặt phải sẽ hướng vào phía mắt người quan sát, trong khi mũi tên ở mặt đáy hướng về bên trái. Từ đó suy ra ta phải làm các phép biến đổi sau (cố định mặt đỏ): 

 

Đổi 1 và 9 cho nhau, 3 và 7 cho nhau (nhưng không xoay măt đỏ đi chỗ khác, nghĩa là 9 ô trước măt ta vẫn là màu đỏ).

 

Đổi 2 và 8, 4 và 6 cho nhau (cũng giữ nguyên màu đỏ, như trên).

 

Trong rubik căn bản (6 màu, không có mũi tên) có thuật toán cụ thể để làm việc này (có thể xem trên website của Rubik). 

Có chỗ mình chưa hiểu lắm, tại sao phép xoay rubik phải là một hoán vị chẵn. Và ở dưới là bạn đánh số từ 1 đến 9 ở mặt nào vậy, còn phép xoay của bạn có giữ cố định các ô giữa của các mặt không?



#7 bangbang1412

bangbang1412

    Độc cô cầu bại

  • Phó Quản trị
  • 1596 Bài viết
  • Giới tính:Không khai báo
  • Đến từ:l'Université de Rennes 1
  • Sở thích:Motivic integration, motivic stable homotopy category

Đã gửi 07-07-2014 - 13:11

Câu cuối nếu ai đã chơi qua rubic thì chắc chắn biết rất nhiều là đằng khác vì các dãy thuật toán để thu lại rubic ban đầu là 1 chiêu luyện tay mà. 

À nhân tiện cũng nói rằng câu $c$ là sai nhé sau 

Đây là ký hiệu chuẩn mọi người tham khảo cho em dễ nói http://blog.zing.vn/...42485?from=like

Ví dụ $(ul)_{n}$ với $u,l$ là $U,L$ nhưng quay $2$ tầng dãy này không được có thể thử . 


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

Declare to yourself that, from now on, your life is dedicated to one and only one woman, the greatest mistress of your life, the tenderest woman you have ever encountered, Mathematica.


#8 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 07-07-2014 - 13:41

Có chỗ mình chưa hiểu lắm, tại sao phép xoay rubik phải là một hoán vị chẵn. Và ở dưới là bạn đánh số từ 1 đến 9 ở mặt nào vậy, còn phép xoay của bạn có giữ cố định các ô giữa của các mặt không?

Vì mỗi lần xoay là một phép hoán vị chẵn và một phép biến đổi là tích các hoán vị chẵn nên vẫn là môt hoán vị chẵn. Ở dưới mình đánh số ô màu đỏ. Các phép quay không làm thay đổi vị trí (chiều mũi tên) ở các ô giữa ở các mặt khác mặt màu đỏ.  Đối với ô màu đỏ phép hoán vị  1 thành 9, 3 thành 7 không làm thay đổi mũi tên.  Hai phép cuối (2 thành 8, 4 thành 6) phải thực hiện liên tiếp 2 thuật toán (giống nhau): Cố định 2, hoán vị 4 thành 6, 6 thành 8 và 8 thành 4, sau đó cố định 6 và hoán vị 2, 4, 8 cho nhau. Mỗi phép biến đổi sẽ làm xoay chiều mũi tên giữa ở ô đỏ 180° nên sau 2 lần mũi tên giữ nguyên.  



#9 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 07-07-2014 - 14:21

Câu cuối nếu ai đã chơi qua rubic thì chắc chắn biết rất nhiều là đằng khác vì các dãy thuật toán để thu lại rubic ban đầu là 1 chiêu luyện tay mà. 

À nhân tiện cũng nói rằng câu $c$ là sai nhé sau 

Đây là ký hiệu chuẩn mọi người tham khảo cho em dễ nói http://blog.zing.vn/...42485?from=like

Ví dụ $(ul)_{n}$ với $u,l$ là $U,L$ nhưng quay $2$ tầng dãy này không được có thể thử . 

Tai sao câu c sai nhỉ. Đây là nhóm hữu hạn và do đó $L^k(x)$ sẽ là dãy dừng, nghĩa là $L^k (x)=x$ với $k$ là số phần tử của nhóm. 



#10 chanhquocnghiem

chanhquocnghiem

    Thiếu tá

  • Thành viên
  • 2072 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũng Tàu
  • Sở thích:Toán,Thiên văn,Lịch sử

Đã gửi 07-07-2014 - 15:04

Trò chơi và bài toán về rubik

 

Hân cầm cục rubik đưa cho Kiên và khoe: "Xem này tớ xoay đủ 6 mặt hết chưa đầy một phút!".

 

Kiên cầm cục rubik đã hoàn thành 6 mặt ngắm nghía hồi lâu rồi nghĩ ra một "kế". Kiên lấy bút vẽ lên tất cả các mặt của rubik mỗi mặt gồm những mũi tên cùng chiều ở mỗi ô, duy nhất mặt màu đỏ thì Kiên vẽ mũi tên ở ô chính giữa vuông góc với các mũi tên ở xung quanh (Xem hình a) rồi đem đố Hân làm sao xoay lại cho đúng chiều.

 

attachicon.gifrubik.png

 

a) Hân có xoay rubik được theo yêu cầu của Kiên không? Vì sao?

 

b) Nếu Kiên vẽ mũi tên như hình b) thì Hân có xoay lại được không? Hãy chỉ cho Hân cách xoay rubik lại trong trường hợp này nếu bạn giải được!

 

c) Ta gọi các mặt rubik là $a,b,c,d,e,g$ mỗi phép xoay sẽ được ký hiệu là $+, - , 2$ và được viết như là chỉ số của mặt ("+" tương ứng với xoay $+90^{\circ}$, "-" là xoay $-90^{\circ}$ còn $2$ là xoay $180^{\circ}$). Ta được tập hợp mẫu $E$:

$$E=\{a_+,a_-,a_2,...,g_+,g_-,g_2\}$$

$L$ là một dãy hữu hạn các phần tử $L=\{x_1,x_2,...,x_k\}$ trong đó $x_i\in E, \forall i=\overline{1,k}$ được gọi là dãy lệnh

 

Chứng minh rằng tồn tại một số tự nhiên $n$ để sau khi áp dụng $n$ lần liên tiếp dãy lệnh $L$, rubik sẽ trở lại trạng thái ban đầu!

Mình xin đóng góp một cách chứng minh khác cho câu $c$, tuy dài dòng hơn nhưng cũng dễ hiểu hơn.

 

Xét khối rubik $ABCD.A'B'C'D'$ gồm $27$ khối nhỏ, trong đó có $26$ khối có ít nhất $1$ mặt được tô màu, chia ra như sau :

+ $8$ khối ở đỉnh (tạm gọi là $8$ viên đỉnh), mỗi viên đỉnh có $3$ mặt được tô màu.

+ $12$ khối ở cạnh (tạm gọi là $12$ viên cạnh), mỗi viên cạnh có $2$ mặt được tô màu.

+ $6$ khối ở tâm các mặt, mỗi khối này chỉ có $1$ mặt được tô màu.

Nhận xét rằng khi thực hiện bất kỳ dãy lệnh nào thì các khối ở tâm các mặt chỉ có thể xoay chứ không thay đổi vị trí nên ta không cần quan tâm đến chúng.

Trước hết ta chứng minh rằng với mỗi viên đỉnh và mỗi dãy lệnh $L$ bất kỳ cho trước, tồn tại số tự nhiên $m> 0$ sao cho sau khi thực hiện $m$ lần liên tiếp dãy lệnh $L$ thì viên đỉnh đó trở lại đỉnh ban đầu.

Không làm mất tính tổng quát, ta chỉ cần xét viên đỉnh có vị trí ban đầu ở đỉnh $A$, có mặt hướng về phía ta màu đỏ, mặt trên màu xanh, mặt bên trái màu vàng.Ta gọi viên đỉnh này là $\alpha$ và trạng thái ban đầu của nó là $A_{V/Đ}^{X}$ (nêu rõ vị trí và màu các mặt)

Giả sử $\alpha$ không bao giờ trở lại đỉnh $A$ sau khi thực hiện xong $k$ dãy lệnh $L$ bất kỳ ($\forall k\in \mathbb{N}^+$).

Ta gọi $F$ là tập hợp các đỉnh khác $A$ ($F=\left \{ B,C,D,A',B',C',D' \right \}$)

Sau dãy lệnh $L$ lần thứ nhất, $\alpha$ đến đỉnh $K$ ($K\in F$).Một viên đỉnh khác (tạm gọi là $\beta$) sẽ đến $A$.

Sau dãy lệnh $L$ lần thứ hai, $\beta$ sẽ đến $K$ nên $\alpha$ phải đến $M$ ($M\in F$ và $M\not\equiv K$).Một viên đỉnh khác ($\gamma$) sẽ đến $A$.

Sau dãy lệnh $L$ lần thứ ba, $\gamma$ sẽ đến $K$, $\beta$ sẽ đến $M$ nên $\alpha$ phải đến $N$ ($N\in F$ và $K,M,N$ khác nhau từng đôi một).Một viên đỉnh khác ($\delta$) sẽ đến $A$.

..........................................................................................

.........................................................................................

Sau dãy lệnh $L$ lần thứ bảy, $\zeta \rightarrow K,\varepsilon \rightarrow M,\epsilon \rightarrow N,\delta \rightarrow P,\gamma \rightarrow Q,\beta \rightarrow R$ nên $\alpha$ phải đến $S$ ($S\in F$ và $K,M,N,P,Q,R,S$ khác nhau từng đôi một).Một viên đỉnh khác ($\eta$) sẽ đến $A$.

Sau dãy lệnh $L$ lần thứ tám, $\eta \rightarrow K,\zeta \rightarrow M,\varepsilon \rightarrow N,\epsilon \rightarrow P,\delta \rightarrow Q,\gamma \rightarrow R,\beta \rightarrow S$ nên $\alpha$ "không còn chỗ để đi"

Vậy điều giả sử trên là sai và ta suy ra : Sau không quá $8$ dãy lệnh $L$ thì $\alpha$ phải trở lại đỉnh ban đầu (ta chưa xét màu của các mặt) (điều này cũng đúng với bất kỳ viên đỉnh nào)

Giả sử sau $m_{\alpha }$ dãy lệnh $L$ thì $\alpha$ trở lại đỉnh $A$ ($1\leqslant m_{\alpha }\leqslant 8$).Có $2$ trường hợp :

+ Nếu khi đó trạng thái của $\alpha$ là $A_{V/Đ}^{X}$ thì có nghĩa là sau $n_{\alpha }=m_{\alpha }$ dãy lệnh $L$, viên đỉnh $\alpha$ trở lại trạng thái ban đầu (về cả vị trí và màu các mặt)

+ Nếu khi đó trạng thái của $\alpha$ là $A_{X/V}^{Đ}$ hoặc $A_{Đ/X}^{V}$ thì tức là sau $n_{\alpha }=3m_{\alpha }$ dãy lệnh $L$, viên đỉnh $\alpha$ sẽ trở lại trạng thái ban đầu (vì các trạng thái này chỉ là trạng thái $A_{V/Đ}^{X}$ xoay quanh trục $AD'$ góc $\pm 120^o$)

Tương tự, với viên đỉnh $\beta, \gamma,...$ thì sau $n_{\beta },n_{\gamma },...$ dãy lệnh $L$, chúng cũng trở về trạng thái ban đầu.

Hoàn toàn tương tự, ta chứng minh được với mỗi viên cạnh và mỗi dãy lệnh $L$ bất kỳ, tồn tại số tự nhiên $m> 0$ sao cho sau khi thực hiện xong $m$ dãy lệnh $L$ thì viên cạnh ấy trở về cạnh ban đầu.

Bây giờ xét viên cạnh có vị trí ban đầu trên cạnh $AB$, mặt trên xanh, mặt hướng về ta đỏ.Gọi đó là viên cạnh $1$, trạng thái ban đầu là $AB_{Đ}^{X}$.Giả sử sau $m_{1}$ dãy lệnh $L$ thì vc $1$ trở về cạnh $AB$.Có $2$ trường hợp :

+ Nếu khi đó trạng thái của vc $1$ là $AB_{Đ}^{X}$ thì tức là sau $n_{1}=m_{1}$ dãy lệnh $L$ thì vc $1$ trở lại trạng thái ban đầu.

+ Nếu khi đó trạng thái của vc $1$ là $AB_{X}^{Đ}$ thì tức là sau $n_{1}=2m_{1}$ dãy lệnh $L$ thì vc $1$ trở lại trạng thái ban đầu.

Tương tự, với các viên cạnh $2,3,...,12$ thì sau $n_{2},n_{3},...,n_{12}$ dãy lệnh $L$ thì chúng cũng trở về trạng thái ban đầu.

 

Vậy nếu $n$ là bội số chung của $n_{\alpha },n_{\beta },...,n_{\eta },n_{1},n_{2},...,n_{12}$ (có vô số số $n$ như thế) thì sau khi thực hiện $n$ dãy lệnh $L$ liên tiếp, khối rubik sẽ trở lại trạng thái ban đầu.


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

...

Ðêm nay tiễn đưa

Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...

 

http://www.wolframal...-15)(x^2-8x+12)


#11 Nxb

Nxb

    Thiếu úy

  • ĐHV Toán học Hiện đại
  • 618 Bài viết
  • Giới tính:Nam

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

Vì mỗi lần xoay là một phép hoán vị chẵn và một phép biến đổi là tích các hoán vị chẵn nên vẫn là môt hoán vị chẵn. Ở dưới mình đánh số ô màu đỏ. Các phép quay không làm thay đổi vị trí (chiều mũi tên) ở các ô giữa ở các mặt khác mặt màu đỏ.  Đối với ô màu đỏ phép hoán vị  1 thành 9, 3 thành 7 không làm thay đổi mũi tên.  Hai phép cuối (2 thành 8, 4 thành 6) phải thực hiện liên tiếp 2 thuật toán (giống nhau): Cố định 2, hoán vị 4 thành 6, 6 thành 8 và 8 thành 4, sau đó cố định 6 và hoán vị 2, 4, 8 cho nhau. Mỗi phép biến đổi sẽ làm xoay chiều mũi tên giữa ở ô đỏ 180° nên sau 2 lần mũi tên giữ nguyên.  

Mình vẫn có chỗ khó hiểu: ý của bạn là tồn tại một thuật toán như bạn nói, nếu thế bạn nên chỉ ra nó như thế nào vì đề bài bắt chỉ ra. Còn điều nữa là 1 luôn cố định ở một khối vuông có 3 màu đỏ xanh vàng, bạn chuyển 1 đến 9 thì phải chuyển cả cái khối đó, nếu thế thì đâu thể có được cái rubik đúng màu.

Câu cuối nếu ai đã chơi qua rubic thì chắc chắn biết rất nhiều là đằng khác vì các dãy thuật toán để thu lại rubic ban đầu là 1 chiêu luyện tay mà. 

À nhân tiện cũng nói rằng câu $c$ là sai nhé sau 

Đây là ký hiệu chuẩn mọi người tham khảo cho em dễ nói http://blog.zing.vn/...42485?from=like

Ví dụ $(ul)_{n}$ với $u,l$ là $U,L$ nhưng quay $2$ tầng dãy này không được có thể thử . 

Anh thử rồi nhé, được. Cái này khi học về lý thuyết nhóm ít nhiều mọi người đều phải biết nên không có chuyện sai đâu.

http://ruwix.com/onl...solver-program/

Có thể thử ở đây, cứ ấn UL liên tục. Anh ấn khoảng 100 lần thì được.

Chanhquocnghiem: thực ra cũng không phải khó hiểu đâu, ý tưởng của nó khá rõ ràng. Mọi nguời đừng thấy toán cao cấp là ngại vì thực ra các ý tưởng cao cấp rất trong sáng, tranh thủ học luôn thì tốt. Có một bài viết ở đây khá dễ hiểu http://zung.zetamu.n...cho-mirella-2/ 


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


#12 hxthanh

hxthanh

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

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

Anh thử rồi nhé, được. Cái này khi học về lý thuyết nhóm ít nhiều mọi người đều phải biết nên không có chuyện sai đâu.

http://ruwix.com/onl...solver-program/

Có thể thử ở đây, cứ ấn UL liên tục. Anh ấn khoảng 100 lần thì được.

Chính xác là $(UL)^{105}$ (210 động tác xoay)

 

Cái này lại mâu thuẫn với chanhquocnghiem mới thú vị làm sao :D

Vì rằng thì là mà ... Ai cũng biết nếu xoay một mặt $4$ lần thì ô góc (thậm chí toàn bộ các ô) trở về vị trí cũ

Ấy thế mà $105$ đâu có phải là bội của $4$ đâu ? :))

_________________________

Vì đâu phát sinh mâu thuẫn? Mời bác chanhquocnghiem mua cục rubik về tự tìm hiểu :))


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!

#13 bangbang1412

bangbang1412

    Độc cô cầu bại

  • Phó Quản trị
  • 1596 Bài viết
  • Giới tính:Không khai báo
  • Đến từ:l'Université de Rennes 1
  • Sở thích:Motivic integration, motivic stable homotopy category

Đã gửi 07-07-2014 - 16:46

Chính xác là $(UL)^{105}$ (210 động tác xoay)

 

Cái này lại mâu thuẫn với chanhquocnghiem mới thú vị làm sao :D

Vì rằng thì là mà ... Ai cũng biết nếu xoay một mặt $4$ lần thì ô góc (thậm chí toàn bộ các ô) trở về vị trí cũ

Ấy thế mà $105$ đâu có phải là bội của $4$ đâu ? :))

_________________________

Vì đâu phát sinh mâu thuẫn? Mời bác chanhquocnghiem mua cục rubik về tự tìm hiểu :))

:D ui kinh quá 


Declare to yourself that, from now on, your life is dedicated to one and only one woman, the greatest mistress of your life, the tenderest woman you have ever encountered, Mathematica.


#14 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 07-07-2014 - 17:31

Mình vẫn có chỗ khó hiểu: ý của bạn là tồn tại một thuật toán như bạn nói, nếu thế bạn nên chỉ ra nó như thế nào vì đề bài bắt chỉ ra. Còn điều nữa là 1 luôn cố định ở một khối vuông có 3 màu đỏ xanh vàng, bạn chuyển 1 đến 9 thì phải chuyển cả cái khối đó, nếu thế thì đâu thể có được cái rubik đúng màu.

Mình nghĩ là chỉ cần mũi tên đúng chiều còn màu thì không quan tâm. Nếu vừa đúng màu vừa đúng mũi tên thì không bao giờ làm được cả a lẫn b.  Cần tác giả bài toán confirm lại vì có thể gây hiểu lầm. 

Thuật toán cụ thể thì như mình đã nói. Bạn tham khảo trên trang web cua rubik: http://eu.rubiks.com/solving-guide/3x3. Tuy nhiên mình cũng sẽ cố gắng viết rõ thuật toán theo các ký hiệu trên trang web này (Việc này đòi hỏi viết rất chi tiết và rất dễ lẫn lộn khi ta không thể trao đổi face to face). 



#15 hxthanh

hxthanh

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

Đã gửi 07-07-2014 - 17:50

Cả màu và mũi tên đều trùng thì mới là điều cần phải nói chứ bạn!

Và xin nhắc lại: tồn tại ít nhất một thuật toán chỉ làm biến đổi mỗi hướng của mũi tên chính giữa mặt đỏ (xoay $180^\circ$) mà không ảnh hưởng gì tới bất kỳ vị trí nào xung quanh (tôi có thuật toán cho trường hợp b)

Trường hợp $a)$ là bất 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!

#16 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 07-07-2014 - 18:37

Ban hxthanh noi dung. Minh ap dung thuat toan tren trang rubik dung 3 lan (doi cho cac edges voi nhau, moi lan mui ten o giua xoay 180) thi mui ten o giua se xoay 180 do va nhung vi tri khac khong doi. Sorry da ket luan voi vang ( va sai).

#17 chanhquocnghiem

chanhquocnghiem

    Thiếu tá

  • Thành viên
  • 2072 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũng Tàu
  • Sở thích:Toán,Thiên văn,Lịch sử

Đã gửi 07-07-2014 - 19:00

Chính xác là $(UL)^{105}$ (210 động tác xoay)

 

Cái này lại mâu thuẫn với chanhquocnghiem mới thú vị làm sao :D

Vì rằng thì là mà ... Ai cũng biết nếu xoay một mặt $4$ lần thì ô góc (thậm chí toàn bộ các ô) trở về vị trí cũ

Ấy thế mà $105$ đâu có phải là bội của $4$ đâu ? :))

_________________________

Vì đâu phát sinh mâu thuẫn? Mời bác chanhquocnghiem mua cục rubik về tự tìm hiểu :))

Không có mâu thuẫn ở đây !

Xét dãy lệnh $UL$ 

Nếu gọi mặt có viên giữa xanh là $a$, mặt có viên giữa vàng là $b$ thì theo quy ước của đề bài, dãy lệnh này viết là $L=\left \{ a_{-} ,b_{-}\right \}$

Gọi $A$ là đỉnh vàng-xanh-đỏ, $B$ là đỉnh trắng-xanh-đỏ (tự suy các đỉnh còn lại)

Các viên góc $\alpha ,\beta ,\gamma ,\delta ,\epsilon ,\varepsilon ,\zeta ,\eta$ có vị trí ban đầu lần lượt ở $A,B,C,D,A',B',C',D'$

Các viên cạnh $1,2,...,12$ có vị trí ban đầu lần lượt ở trên các cạnh $AB,BC,CD,DA,A'B',B'C',C'D',D'A',AA',BB',CC',DD'$

Bằng thực nghiệm có thể thấy :

$n_{\alpha }=3$

$n_{\beta }=n_{\gamma }=n_{\delta }=n_{\epsilon }=n_{\eta }=3.5=15$

$n_{\varepsilon }=n_{\zeta }=1$

$n_{1}=n_{2}=n_{3}=n_{4}=n_{8}=n_{9}=n_{12}=7$

$n_{5}=n_{6}=n_{7}=n_{10}=n_{11}=1$

$\Rightarrow$ số $n$ nhỏ nhất cần tìm chính là bội số chung khác $0$ nhỏ nhất của $3,15,7$, tức là số $105$


...

Ðêm nay tiễn đưa

Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...

 

http://www.wolframal...-15)(x^2-8x+12)


#18 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 07-07-2014 - 19:49

Trò chơi và bài toán về rubik

 

Hân cầm cục rubik đưa cho Kiên và khoe: "Xem này tớ xoay đủ 6 mặt hết chưa đầy một phút!".

 

Kiên cầm cục rubik đã hoàn thành 6 mặt ngắm nghía hồi lâu rồi nghĩ ra một "kế". Kiên lấy bút vẽ lên tất cả các mặt của rubik mỗi mặt gồm những mũi tên cùng chiều ở mỗi ô, duy nhất mặt màu đỏ thì Kiên vẽ mũi tên ở ô chính giữa vuông góc với các mũi tên ở xung quanh (Xem hình a) rồi đem đố Hân làm sao xoay lại cho đúng chiều.

 

attachicon.gifrubik.png

 

a) Hân có xoay rubik được theo yêu cầu của Kiên không? Vì sao?

 

b) Nếu Kiên vẽ mũi tên như hình b) thì Hân có xoay lại được không? Hãy chỉ cho Hân cách xoay rubik lại trong trường hợp này nếu bạn giải được!

 

c) Ta gọi các mặt rubik là $a,b,c,d,e,g$ mỗi phép xoay sẽ được ký hiệu là $+, - , 2$ và được viết như là chỉ số của mặt ("+" tương ứng với xoay $+90^{\circ}$, "-" là xoay $-90^{\circ}$ còn $2$ là xoay $180^{\circ}$). Ta được tập hợp mẫu $E$:

$$E=\{a_+,a_-,a_2,...,g_+,g_-,g_2\}$$

$L$ là một dãy hữu hạn các phần tử $L=\{x_1,x_2,...,x_k\}$ trong đó $x_i\in E, \forall i=\overline{1,k}$ được gọi là dãy lệnh

 

Chứng minh rằng tồn tại một số tự nhiên $n$ để sau khi áp dụng $n$ lần liên tiếp dãy lệnh $L$, rubik sẽ trở lại trạng thái ban đầu!

Mình xin tóm tắt lại lời giải câu a và b như sau. Câu c thì mọi người đều biết là dùng lý thuyết nhóm. Mình không hề CLAIM rằng đây là lời giải của minh.

Mình học được qua các thảo luận của các bạn phía trên (đặc biệt là bạn hxthanh).

 

Câu a: Không xoay được. Giả sử có một thuật toán $L=x_1x_2.....x_N$ trong đó $x_N\in E$ (và có thể trùng nhau) sao cho áp dụng $L$ vào Rubik hình a ta được Rubik chuẩn. Gọi $D$ là phép xoay mặt đỏ môt góc 90° và $k$ là số lần $D$ xuất hiện  trong $L$. 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. Từ đó suy ra $k$ cũng  phải là số chẵn (Nếu không thì $L$ là phép hoán vị lẻ). Nhưng nếu $k$ chẵn thì mũi tên không xoay được 90°. Điều mâu thuẫn này chứng tỏ không có cách xoay.

 

Câu b: Xoay đươc. Mình tò mò về lời comment của bạn hxthanh nên làm thử thì tìm ra thuật toán này (Nhắc lại là lời giải của mình lúc trước bị ...lạc đề). 

 

Hướng mặt đỏ lên trên và gọi là U (Up). Các mặt khác ký hiệu là R (right) L (Left) F (face, hướng vào mặt người xoay), B (back) D (down), giống như các ký hiệu trên trang web rubik http://eu.rubiks.com...solution-en.pdf. Áp dụng thuật toán sau đúng 3 lần: 

 

FFULRiFFLiRUFF

 

Ở đây Li là xoay mặt L theo hướng ngược chiều kim đồng hồ. 

 

Comment: Ở đây $U$ xuất hiện 2 lần nên mũi tên trên ô giữa màu đỏ xoay 2 x 90 =180 .


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


#19 hxthanh

hxthanh

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

Đã gửi 07-07-2014 - 22:17

Chính xác là $(UL)^{105}$ (210 động tác xoay)

 

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:


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!

#20 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:06

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:

Bạn hxthanh lại nói ... đúng. Thuật toán của bạn hxthanh rất đẹp và chuẩn! Mình đã xoay thử và thấy rằng cứ sau 5 lần thì các cạnh (edges) lại về vị trí cũ,ngoại trừ có hai cạnh cứ liên tục đổi chỗ cho nhau. Và cứ xoay 6 lần thì các gốc cũng về vị trí cũ. Như vậy thì xoay 30 lần là đúng rồi. Neu so minh tinh nham thi cu xoay 30 lan (hoi met) cung ra thoi.  Bravo ban hxthanh. Co ve bai toan da duoc giai tron ven roi nhi?







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

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

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