The blackout game has been studied

The blackout game has been studied in the literature [1, 11, 12, 13] extensively.
When we toggle a square with a black or white color, it changes the color of
itself and other buttons. With this rule, we win the game when a squareboard
contains same colors after we click some of the buttons. This game of 3 × 3
squareboard has been popular in the electronic game machines and on the web
[10, 17].
Figure 1: Various forms of the blackout games
http://matrix.skku.ac.kr/bljava/Test.html
The 3×3 game always has a winnable solution. But in general, our m×n
blackout game on the squareboard may not have a winnable solution. The
winnable conditions depend on the size of the game and the initial conditions.
So, we have to investigate the conditions which makes this game winnable
for given m and n. Many attempts have been made to find out the conditions
which make the game winnable [1, 2]. We have given a linear algebraic solution
for 3 × 3 and n × n in [13]. In this paper, we will give a linear algebraic proof
for a winnable solution on the general rectangular size m × n blackout game.
Now, we start with a couple of definitions which we use in this paper.
Definition 1.1 [9] Let us assume m×n squareboard has squares with black
and white colors in it and assign a numbering of each squares in it as follows.
Figure 2: The numbering of the blackout game
Now we can consider a m × n squareboard as a m × n (0, 1)-matrix B
and its black square is 0 and its white square is 1. When the initial arbitrary
Fibonacci sequences and the winning conditions for the blackout game 1473
configuration with colors are given, we call the corresponding matrix B is an
Initial Configuration Matrix (ICM).
For example, the numbering of 3 × 4 blackout game and an ICM B are
given in Figure 3.
,
Figure 3: The numbering and an ICM B of size 3 × 4 blackout game.
When we toggle a button with a black or white color, it changes the colors
of itself and other buttons which it shares common edges. This action can
be represented by the corresponding (0, 1)-matrix which is filled with 1 when
their colors are changed. Now, we define a matrix that results in the action of
clicking a button. When we take an action on a given initial configuration it
can be considered as adding a new (0, 1)-matrix to the ICM in mod 2 addition.
We now define a (0, 1)-matrix of each action by clicking a button as below.
Definition 1.2 [9] Let Mk ∈ Mm×n(R) be a m × n matrix. (where 1 ≤
i ≤ mn). Mk is a (0, 1)-matrix whose k’s numbered position, top and bottom
positions and left and right positions are 1 and all the rest are 0. i.e. it can be
written as remaining mij = 0.
Mk = [mij ]m×n where k = n(i − 1) + j
with

mij = mi−1,j = mi+1,j = mi,j−1 = mi,j+1 = 1
otherwise mij = 0.
For example, two matrices M1 and M6 of the size 3 × 4 and its corresponding
matrix of action at (1,1) position(numbered as 1st) and (2,2) position(
numbered as 6th) are given in Figure 4.
,
Figure 4: Resulting matrices of a 3 × 4 blackout game after a click
1474 Duk-Sun Kim, Sang-Gu Lee and Faqir M. Bhatti
The process of playing the blackout game can be considered as an addition
of a linear combination of Mk’s and the ICM B to make a matrix of all 1’s or
all 0’s. It can be written in the following form to complete the game.
B + c1M1 + c2M2 + · · · + cmnMmn = O (1)
or
B + c1M1 + c2M2 + · · · + cmnMmn = J (2)
(where O is a zero matrix and J is a matrix with all entries 1.)
To make it simple, we can consider the matrices B, J and O as mn × 1
column vectors. For example, the ICM B3×4 in Figure 3 can be considered as
the following column vector.
(0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1,0)= [0 1 0 1 0 0 0 1 1 0 1 0]T (3)
This consideration can be taken to all Mk’s. We write the matrix Mk as a
column vector mk and the matrix B as a column vector b and the matrices J
and O as column vectors j and 0 respectively. Then the mathematical modeling
of the blackout game can be written as finding a solution for a simple linear
system of equations. We give the statement of the following theorem for later
uses.
Theorem 1.3 [9] Let the vectors mk be a column vector of the following
matrix A.
A =

m1 | m2 | · · · | mmn

(4)
And the matrix B can be written as a column vector b and the matrices
J and O as column vectors j and 0 respectively. The previous equations (1.1)
and (1.2) can be written as
Ax = −b (5)
or
Ax = j − b (6)
where x = (c1, c2, . . . , cmn).
Fibonacci sequences and the winning conditions for the blackout game 1475
Therefore, if we find a solution for the linear system of equations (1.5)(or
(1.6)), then we can give a solution for the given blackout game of any size.
If we can find a solution of the linear system of equations, we can click only
squares which are chosen to make all squares with same color and it means
we win this lighout game from a given configuration. In this case, we say this
blackout game is winnable and winnable conditions depend on the consistency
of the linear system of equations. Now we investigate the properties of the
matrix A. In this paper, we analyze the matrix A to give answers for the
winnable conditions of the m × n blackout game.
2 Block Tridiagonal Matrices
Looking at the 3 × 4 blackout game, we can have twelve 12 × 1 vectors of mk
and a 12 × 12 matrix A whose columns mk are made from Mk as following.
⎡
⎢⎣
1 1 0 0
1 0 0 0
0 0 0 0
⎤
⎥⎦
,
⎡
⎢⎣
1 1 1 0
0 1 0 0
0 0 0 0
⎤
⎥⎦
,
⎡
⎢⎣
0 1 1 1
0 0 1 0
0 0 0 0
⎤
⎥⎦
,
⎡
⎢⎣
0 0 1 1
0 0 0 1
0 0 0 0
⎤
⎥⎦, (
7)
⎡
⎢⎣
1 0 0 0
1 1 0 0
1 0 0 0
⎤
⎥⎦
,
⎡
⎢⎣
0 1 0 0
1 1 1 0
0 1 0 0
⎤
⎥⎦
,
⎡
⎢⎣
0 0 1 0
0 1 1 1
0 0 1 0
⎤
⎥⎦
,
⎡
⎢⎣
0 0 0 1
0 0 1 1
0 0 0 1
⎤
⎥⎦
, (8)
⎡
⎢⎣
0 0 0 0
1 0 0 0
1 1 0 0
⎤
⎥⎦
,
⎡
⎢⎣
0 0 0 0
0 1 0 0
1 1 1 0
⎤
⎥⎦
,
⎡
⎢⎣
0 0 0 0
0 0 1 0
0 1 1 1
⎤
⎥⎦
,
⎡
⎢⎣
0 0 0 0
0 0 0 1
0 0 1 1
⎤
⎥⎦
. (9)
A =
⎡
⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣
1 1 0 0 1 0 0 0 0 0 0 0
1 1 1 0 0 1 0 0 0 0 0 0
0 1 1 1 0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 1 1 1 0 0 1 0 0
0 0 1 0 0 1 1 1 0 0 1 0
0 0 0 1 0 0 1 1 0 0 0 1
0 0 0 0 1 0 0 0 1 1 0 0
0 0 0 0 0 1 0 0 1 1 1 0
0 0 0 0 0 0 1 0 0 1 1 1
0 0 0 0 0 0 0 1 0 0 1 1
⎤
⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦
(10)
This matrix A is a block tridiagonal matrix as shown in Figure 5. In this
case, we have three tridiagonal matrices of size 4 × 4 in its main diagonal.
Since the game is a blackout game of size 3 × 4, the number of rows means
1476 Duk-Sun Kim, Sang-Gu Lee and Faqir M. Bhatti
the number of tridiagonal matrices in its main diagonal and its number of
columns means the size of the tridiagonal matrix. Furthermore we generalize
our observation to make a general rectangular size m × n blackout game.
Figure 5: Block structure of the corresponding matrix for the blackout game
of size 3 × 4
Figure 6: Block structure of the corresponding matrix for the blackout game
of size m × n
In general, an analysis of the existence of solutions on the linear system of
equation Ax = −b or Ax = j − b is based on the value det(A). If det(A) is
not zero, each of the system has a unique solution. In the blackout game, this
solution means the buttons that we click to make all buttons with the same
color. In other word, a basic knowledge of linear algebra is enough to handle
not only the 3 × 3 blackout game, but also the general rectangular size m× n
blackout game.
Fibonacci sequences and the winning conditions for the blackout game 1477
Here we give the statement of another theorem.
Theorem 2.1 [10] Suppose the matrix A is a block tridiagonal matrix corresponding
to the general rectangular size m×n blackout game. If det(A) = 0,
the given game is winnable. And the column vector b is from the ICM B
of the given initial condition, A−1b gives the unique solution for the general
rectangular size m × n blackout game.
Even for the case of det(A) = 0, we may find solutions for the general
rectangular size m × n blackout game. But in this case, the existence of the
solution depends on the vector b which is from the initial condition. The
analysis on this case was dealt in our previous work [10].
3 Fibonacci sequence and tiling on the blackout
game
In the previous section, we used the fact that the block triangular matrix
generated by the blackout game has important information which is related
with the decision of the winnability for the game. If the determinant of the
block tridiagonal matrix is not zero, then there exists a unique solution to win
the arbitrary given m × n blackout game. With these arguments, we gave a
list of all the determinants of the block triangular matrices A taken from 1×1
blackout game to 24 × 24 blackout game in [9].
Figure 7: Determinants Table from 1 × 1 blackout game to 24 × 24 blackout
game
1478 Duk-Sun Kim, Sang-Gu Lee and Faqir M. Bhatti
As we see in the table in Figure 7, there is an interesting tiling rule which
contains two patterns. The first pattern is a tiling by 6 × 6 blocks that we
will see in Figures 8 and 9, and the second pattern is a zero-filling rule at the
position 5k−1. (In Figure 9, some positions are filled with 2 for the distinction.
Moreover, all determinant are also zero). In [9], authors mentioned without
proofs this tiling can be applied for the large size blackout games. Now we
give a mathematical proof for the same.
Figure 8: First pattern : The tiling of 6 × 6 block
Figure 9: Two tiling patterns in the table of determinant on A
These results are obtained by using the properties of the determinant for
the block tridiagonal matrix. From the previous section, the block tridiagonal
matrix form a formula given in equation (3.1) where K is a tridiagonal matrix
whose position is on the main diagonal entries and I is an identity matrix.
Fibonacci sequences and the winning conditions for the blackout game 1479
A =
⎡
⎢⎢⎢⎢⎢⎢⎢⎣
K I O · · · O
I K I · · · O
O
. . .
. . .
. . . O
O O I K I
O O O I K
⎤
⎥⎥⎥⎥⎥⎥⎥⎦
mn×mn
, K=
⎡
⎢⎢⎢⎢⎢⎢⎢⎣
1 1 O · · · O

ผลลัพธ์ (ไทย) 1:

เกมไฟดับมีการศึกษาในวรรณคดี [1, 11, 12, 13] อย่างกว้างขวางเมื่อเราสลับสี่เหลี่ยม มีสีดำ หรือสีขาว เปลี่ยนสีของตัวเองและปุ่มอื่น ๆ กับกฎนี้ เราชนะเกมเมื่อเป็น squareboardประกอบด้วยสีเดียวกันหลังจากที่เราคลิกปุ่มบางปุ่ม เกมนี้ของ 3 × 3squareboard ได้รับความนิยม ในเครื่องเกมอิเล็กทรอนิกส์ และ บนเว็บ[10, 17]รูปที่ 1: แบบฟอร์มต่าง ๆ ของเกมแบล็กเอาต์http://matrix.skku.ac.kr/bljava/Test.html3 × 3 เกมมีปัญหา winnable เสมอ แต่โดยทั่ว ไป ของเรา m × nเกม squareboard ไฟดับอาจมีปัญหา winnable ที่winnable เงื่อนไขขึ้นอยู่กับขนาดของเกมและเงื่อนไขเริ่มต้นดังนั้น เรามีการตรวจสอบเงื่อนไขซึ่งทำให้เกมนี้ winnableสำหรับกำหนดให้ m และ n ได้ทำความพยายามมากเพื่อค้นหาเงื่อนไขซึ่งทำให้เกม winnable [1, 2] เราได้รับปัญหาพีชคณิตเชิงเส้นสำหรับ 3 × 3 และ n × n ใน [13] ในเอกสารนี้ เราจะให้หลักฐานพีชคณิตเชิงเส้นการแก้ไขปัญหา winnable กับเกมขนาดสี่เหลี่ยมทั่วไป m × n ไฟดับตอนนี้ เราเริ่มต้น ด้วยคู่ของคำศัพท์ที่เราใช้ในเอกสารนี้นิยาม 1.1 [9] ให้เราสมมติว่า m × n squareboard มีสี่เหลี่ยม มีสีดำและขาวสีใน และมอบหมายการกำหนดหมายเลขของแต่ละช่องในดังนี้รูปที่ 2: กำหนดหมายเลขเกมแบล็กเอาต์ตอนนี้เราสามารถพิจารณา m × n squareboard เป็น n การซื้อ m (0, 1) -เมตริกซ์ Bและสี่เหลี่ยมสีดำเป็น 0 และเป็นสี่เหลี่ยมสีขาวคือ 1 เมื่อเริ่มต้นกำหนดลำดับ Fibonacci และเงื่อนไขชนะสำหรับเกมแบล็คเอ้าท์ 1473ตั้งค่าคอนฟิก มีสีได้ เรียก B คือเมตริกซ์ที่สอดคล้องกันการกำหนดค่าเริ่มต้นเมตริกซ์ (ICM)ตัว เลข 3 × 4 ไฟดับเกมและ ICM B มีแสดงในรูปที่ 3,รูปที่ 3: กำหนดหมายเลขก B การ ICM ของเกมไฟดับขนาด 3 × 4เมื่อเราสลับปุ่มที่ มีสีดำ หรือสีขาว เปลี่ยนสีของตัวเองและปุ่มอื่นๆ ที่เป็นร่วมขอบทั่วไป สามารถดำเนินการนี้แสดง โดยให้สอดคล้องกับ (0, 1) -เมทริกซ์ซึ่งจะเติมเมื่อ 1มีการเปลี่ยนแปลงสีของพวกเขา ตอนนี้ เรากำหนดเมตริกซ์ที่มีผลการดำเนินการคลิกที่ปุ่ม เมื่อเราดำเนินการในการกำหนดค่าเริ่มต้นให้มันถือได้ว่าเป็นการเพิ่มใหม่ (0, 1) -สามารถ ICM นอกจาก mod 2เรากำหนดเป็น (0, 1) -เมตริกซ์ของแต่ละการดำเนินการดังนี้นิยาม 1.2 [9] ให้ Mk ∈ Mm×n(R) เป็นเมตริกซ์ n × m (ที่ 1 ≤ฉัน≤ mn) เอ็มเป็น (0, 1) -เมตริกซ์ k's มีเลขตำแหน่ง ด้านบน และด้านล่างตำแหน่งซ้าย และขวาที่ตำแหน่ง 1 และทั้งหมดเหลือเป็น 0 เช่นสามารถเขียนเป็น mij เหลือ = 0เอ็มเค = [mij] m × n ที่ k = n(i − 1) + jมีmij = mi−1, j = mi + 1, j = mi, j−1 = mi, j + 1 = 1มิฉะนั้น mij = 0ตัวอย่าง สองเมทริกซ์ M1 และ M6 ขนาด 3 × 4 และความสอดคล้องเมตริกซ์ของการกระทำในตำแหน่ง (ลำดับเลขเป็น 1) และ(ตำแหน่ง (2,2) (1,1)มีตัวเลขเป็น 6) แสดงไว้ในรูปที่ 4,รูปที่ 4: ผลเมทริกซ์ของเกมแบล็คเอ้าท์ 3 × 4 หลังจากคลิกคิมดุก 1474-อาทิตย์ ลีซางจู และ Bhatti เมตร Faqirกระบวนการในการเล่นเกมไฟดับถือได้ว่าเป็นการเพิ่มการรวมเชิงเส้นของเอ็มเคและบี ICM ให้เมทริกซ์ 1 ทั้งหมด หรือทั้งหมด 0 ของ สามารถจะเขียนในแบบฟอร์มต่อไปB + c1M1 + c2M2 + ··· + cmnMmn = O (1)หรือB + c1M1 + c2M2 + ··· + cmnMmn = J (2)(ซึ่ง O เป็นเมทริกซ์ศูนย์และ J เป็นเมทริกซ์กับรายการทั้งหมด 1)ทำง่าย เราสามารถพิจารณาเมทริกซ์ B, J และ O เป็น mn × 1คอลัมน์เวกเตอร์ ตัวอย่าง ICM B3 × 4 ในรูปที่ 3 ถือได้ว่าเป็นแบบเวกเตอร์คอลัมน์ต่อไปนี้(0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1.0) = [0 1 0 1 0 0 0 1 1 0 1 0] T (3)พิจารณานี้ในการทำทั้งหมดของเอ็มเค เราเขียนเมทริกซ์ Mk เป็นการคอลัมน์เวกเตอร์เอ็มเคและเมตริกซ์ B เป็น b เป็นเวกเตอร์คอลัมน์และเมทริกซ์ Jและ O เป็นคอลัมน์เวกเตอร์เจและ 0 ตามลำดับ สร้างโมเดลทางคณิตศาสตร์แล้วของไฟดับเกมสามารถเขียนเป็นการหาวิธีแก้ปัญหาง่ายเส้นระบบสมการ เราให้ยอดของทฤษฎีบทต่อไปนี้ในภายหลังใช้งานทฤษฎีบทที่ 1.3 [9] ให้เวกเตอร์เอ็มเคเป็นเวกเตอร์คอลัมน์ต่อไปนี้เมตริกซ์อ.=เป็นm1 | m2 | · · · | mmn(4)และสามารถเขียนเมตริกซ์ B b เป็นเวกเตอร์คอลัมน์และเมทริกซ์การเจและ O เป็นคอลัมน์เวกเตอร์เจและ 0 ตามลำดับ ก่อนหน้านี้สมการ (1.1)และ (1.2) สามารถเขียนเป็นAx = −b (5)หรือAx = b − j (6)ที่ x = (c1, c2,..., cmn)ลำดับ Fibonacci และเงื่อนไขชนะสำหรับเกมแบล็คเอ้าท์ 1475ดังนั้น ถ้าเราค้นหาโซลูชันระบบเชิงเส้นสมการ (1.5) (หรือ(1.6)), แล้วเราสามารถให้โซลูชันสำหรับเกมแบล็คเอ้าท์กำหนดขนาดใดก็ถ้าเราสามารถหาคำตอบของระบบสมการเชิงเส้น เราสามารถคลิกเท่านั้นหมายถึงช่องสี่เหลี่ยมที่เลือกเพื่อให้สี่เหลี่ยมทั้งหมดกับเดียวกันสีและเราชนะเกม lighout นี้จากการกำหนดค่าที่กำหนด ในกรณีนี้ เราพูดเกมแบล็คเอ้าท์เป็น winnable และ winnable เงื่อนไขขึ้นอยู่กับความสอดคล้องระบบเชิงเส้นสมการ ตอนนี้เราตรวจสอบคุณสมบัติของการเมตริกซ์อ. ในเอกสารนี้ เราวิเคราะห์เมตริกซ์ A จะให้คำตอบสำหรับการเงื่อนไข winnable ของเกม m × n ไฟดับเมทริกซ์การ Tridiagonal บล็อก 2ดูที่เกมแบล็คเอ้าท์ 3 × 4 เราสามารถมี 12 12 × 1 เวกเตอร์ของเอ็มเคและเมทริกซ์ 12 × 12 A คอลัมน์เอ็มเคทำจากเอ็มเคดังต่อไปนี้⎡⎢⎣1 1 0 01 0 0 00 0 0 0⎤⎥⎦,⎡⎢⎣1 1 1 00 1 0 00 0 0 0⎤⎥⎦,⎡⎢⎣0 1 1 10 0 1 00 0 0 0⎤⎥⎦,⎡⎢⎣0 0 1 10 0 0 10 0 0 0⎤⎥⎦, (7)⎡⎢⎣1 0 0 01 1 0 01 0 0 0⎤⎥⎦,⎡⎢⎣0 1 0 01 1 1 00 1 0 0⎤⎥⎦,⎡⎢⎣0 0 1 00 1 1 10 0 1 0⎤⎥⎦,⎡⎢⎣0 0 0 10 0 1 10 0 0 1⎤⎥⎦, (8)⎡⎢⎣0 0 0 01 0 0 01 1 0 0⎤⎥⎦,⎡⎢⎣0 0 0 00 1 0 01 1 1 0⎤⎥⎦,⎡⎢⎣0 0 0 00 0 1 00 1 1 1⎤⎥⎦,⎡⎢⎣0 0 0 00 0 0 10 0 1 1⎤⎥⎦. (9)=เป็น⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣1 1 0 0 1 0 0 0 0 0 0 01 1 1 0 0 1 0 0 0 0 0 00 1 1 1 0 0 1 0 0 0 0 00 0 1 1 0 0 0 1 0 0 0 01 0 0 0 1 1 0 0 1 0 0 00 1 0 0 1 1 1 0 0 1 0 00 0 1 0 0 1 1 1 0 0 1 00 0 0 1 0 0 1 1 0 0 0 10 0 0 0 1 0 0 0 1 1 0 00 0 0 0 0 1 0 0 1 1 1 00 0 0 0 0 0 1 0 0 1 1 10 0 0 0 0 0 0 1 0 0 1 1⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦(10)นี้เมทริกซ์ A คือ เมทริกซ์ tridiagonal บล็อกดังแสดงในรูปที่ 5 ในที่นี้กรณี เรามีสาม tridiagonal เมทริกซ์ขนาด 4 × 4 ในแนวทแยงของหลักเนื่องจากเกมเป็นเกมไฟดับขนาด 3 × 4 จำนวนแถวหมายความว่าคิมดุก 1476-อาทิตย์ ลีซางจู และ Bhatti เมตร Faqirจำนวน tridiagonal เมทริกซ์ทแยงมุมของหลักและจำนวนของคอลัมน์หมายถึง ขนาดของเมตริกซ์ tridiagonal นอกจากนี้ เราทั่วไปเก็บข้อมูลของเราให้เป็นขนาดสี่เหลี่ยมทั่วไป m × n ไฟดับเกมรูปที่ 5: โครงสร้างบล็อกของเมตริกซ์ที่สอดคล้องกันสำหรับเกมไฟดับขนาด 3 × 4รูปที่ 6: โครงสร้างบล็อกของเมตริกซ์ที่สอดคล้องกันสำหรับเกมไฟดับของขนาด m × nโดยทั่วไป การวิเคราะห์ของการดำรงอยู่ของโซลูชั่นระบบเชิงเส้นของสมการ Ax = −b หรือ Ax = j − b ตาม det(A) ค่า ถ้า det(A)ศูนย์ไม่ แต่ละระบบมีปัญหาเฉพาะ ในเกมแบล็คเอ้าท์ นี้โซลูชั่นหมายถึง ปุ่มที่เราต้องทำปุ่มทั้งหมด ด้วยเหมือนกันสี ในคำอื่น ๆ ความรู้พื้นฐานของพีชคณิตเชิงเส้นคือพอที่จะจัดการไม่เพียงแต่เกมแบล็คเอ้าท์ 3 × 3 แต่ยังทั่วไปสี่เหลี่ยมขนาด m × nเกมแบล็กเอาต์ลำดับ Fibonacci และเงื่อนไขชนะสำหรับเกมแบล็คเอ้าท์ 1477ที่นี่เราให้ยอดของทฤษฎีบทอื่นทฤษฎีบท 2.1 [10] สมมติว่า เมทริกซ์ A มีบล็อก tridiagonal เมตริกซ์ที่สอดคล้องการขนาดสี่เหลี่ยมทั่วไป m × n ไฟดับเกม ถ้า det(A) = 0เกมกำหนดเป็น winnable และ b เวกเตอร์คอลัมน์จาก ICM Bกำหนดเงื่อนไขเริ่มต้น A−1b ให้โซลูชันเฉพาะสำหรับทั่วไปเกมสี่เหลี่ยมขนาด m × n ไฟดับสำหรับกรณีของ det(A) = 0 เราอาจค้นหาวิธีแก้ไขปัญหาทั่วไปเกมสี่เหลี่ยมขนาด m × n ไฟดับ แต่ ใน กรณีนี้ การดำรงอยู่ของการโซลูชันที่ขึ้นอยู่กับ b เวกเตอร์ซึ่งเป็นเงื่อนไขเริ่มต้น ที่วิเคราะห์กรณีนี้ถูกแจกในงานก่อนหน้านี้ [10]ลำดับ Fibonacci และเรียงบนไฟดับ 3เกมในส่วนก่อนหน้านี้ เราใช้ความจริงที่เมตริกซ์สามเหลี่ยมบล็อกสร้าง โดยไฟดับเกมมีข้อมูลสำคัญที่เกี่ยวข้องกับการตัดสินใจของ winnability สำหรับเกม ถ้าดีเทอร์มิแนนต์ของเมทริกซ์แบบบล็อก tridiagonal ไม่เท่ากับศูนย์ แล้วมีปัญหาเฉพาะจะชนะการกำหนดให้ m × n ไฟดับเกม มีอาร์กิวเมนต์เหล่านี้ เราให้การรายการทั้งหมดดีเทอร์มิแนนต์ของเมทริกซ์สามเหลี่ยมของบล็อก A ที่มาจาก 1 × 1เกมแบล็คเอ้าท์ 24 × 24 เกมไฟดับใน [9]รูปที่ 7: ดีเทอร์มิแนนต์ตารางจาก 1 × 1 เกมไฟดับไฟดับ 24 × 24เกมคิมดุก 1478-อาทิตย์ ลีซางจู และ Bhatti เมตร Faqirเราดูในตารางในรูปที่ 7 มีกฎที่มันน่าสนใจที่ประกอบด้วยสองรูปแบบ รูปแบบแรกเป็นการเรียง โดย 6 × 6 บล็อกที่เราจะเห็นเลข 8 และ 9 และรูปแบบที่สองคือ กฎศูนย์ถมที่ตำแหน่ง 5k−1 (ในรูปที่ 9 ตำแหน่งบางเต็มไป ด้วย 2 สำหรับแตกนอกจากนี้ ทั้งหมดดีเทอร์มิแนนต์ได้ยังศูนย์) [9], ผู้เขียนกล่าวโดยหลักฐานนี้มันสามารถใช้ได้สำหรับเกมไฟดับขนาดใหญ่ ตอนนี้เราให้หลักฐานทางคณิตศาสตร์สำหรับเดียวกันรูปที่ 8: รูปแบบแรก: เรียงของ 6 × 6 บล็อกรูปที่ 9: สองเรียงรูปในตารางของดีเทอร์มิแนนต์บน Aผลลัพธ์เหล่านี้จะได้รับ โดยใช้สมบัติของดีเทอร์มิแนนต์สำหรับบล็อก tridiagonal เมตริกซ์ จากส่วนก่อนหน้า tridiagonal บล็อกแบบฟอร์มเมตริกซ์สูตรให้ในสมการ (3.1) โดยที่ K คือ เมทริกซ์ tridiagonalตำแหน่งที่อยู่บนรายการเส้นทแยงมุมหลัก และฉันจะเป็นเมทริกซ์เอกลักษณ์ลำดับ Fibonacci และเงื่อนไขชนะสำหรับเกมแบล็คเอ้าท์ 1479=เป็น⎡⎢⎢⎢⎢⎢⎢⎢⎣K O ฉัน··· Oผม K ฉัน··· OO. . .. . .. . . OO O K ฉันฉันO O O K ฉัน⎤⎥⎥⎥⎥⎥⎥⎥⎦mn × mn, K =⎡⎢⎢⎢⎢⎢⎢⎢⎣1 1 O ··· O

ผลลัพธ์ (ไทย) 2:

เกมผ้าได้รับการศึกษาในวรรณคดี [1, 11, 12, 13] อย่างกว้างขวาง.
เมื่อเราสลับตารางที่มีสีดำหรือสีขาวจะเปลี่ยนสีของ
ตัวเองและปุ่มอื่น ๆ ด้วยกฎนี้เราชนะเกมเมื่อ squareboard
มีสีเดียวกันหลังจากที่เราคลิกปุ่มบางปุ่ม เกม 3 × 3 นี้
squareboard ได้รับความนิยมในเครื่องเกมอิเล็กทรอนิกส์และบนเว็บ
[10 17].
รูปที่ 1: รูปแบบต่างๆของเกมผ้า
http://matrix.skku.ac.kr/bljava/Test html
3 × 3 เกมมักจะมีวิธีการแก้ปัญหาชัย แต่โดยทั่วไปเราม. × n
เกมบนผ้า squareboard อาจไม่ได้แก้ปัญหาชัย
เงื่อนไขชัยขึ้นอยู่กับขนาดของเกมและเงื่อนไขเริ่มต้น.
ดังนั้นเรามีการตรวจสอบเงื่อนไขที่ทำให้เกมนี้มีชัย
ในการรับเมตรและ n ความพยายามหลายคนได้รับการทำเพื่อหาเงื่อนไข
ที่ทำให้เกมมีชัย [1, 2] เราได้ให้การแก้ปัญหาเกี่ยวกับพีชคณิตเชิงเส้น
3 × 3 × n และ n ใน [13] ในบทความนี้เราจะให้หลักฐานเกี่ยวกับพีชคณิตเชิงเส้น
สำหรับการแก้ปัญหาชัยกับขนาดสี่เหลี่ยมทั่วไปม. ×เกม n ผ้า.
ตอนนี้เราเริ่มต้นด้วยคู่ของคำนิยามที่เราใช้ในบทความนี้.
ความละเอียด 1.1 [9] ให้เราคิด ม. × squareboard n มีสี่เหลี่ยมที่มีสีดำ
สีขาวและสีดำในนั้นและกำหนดหมายเลขของช่องสี่เหลี่ยมในแต่ละดังนี้.
รูปที่ 2: หมายเลขของเกมผ้า
ตอนนี้เราสามารถพิจารณาน× squareboard n เป็นน× n (0, 1 ) B -matrix
และสี่เหลี่ยมสีดำของมันคือ 0 และสี่เหลี่ยมสีขาวของมันคือ 1. เมื่อเริ่มต้นโดยพล
ลำดับฟีโบนักชีและเงื่อนไขชนะสำหรับเกมผ้า 1473
การกำหนดค่าที่มีสีจะได้รับที่เราเรียกว่าเมทริกซ์ B ที่สอดคล้องกันคือ
เมทริกซ์การตั้งค่าเริ่มต้น ( . ICM)
ตัวอย่างเช่นหมายเลข 3 × 4 เกมผ้าและ ICM B จะ
ได้รับในรูปที่ 3
,
รูปที่ 3: เลขและ ICM B ขนาด 3 × 4 เกมผ้า.
เมื่อเราสลับปุ่มที่มีสีดำ หรือสีขาวจะเปลี่ยนสี
ของตัวเองและปุ่มอื่น ๆ ที่หุ้นมันขอบที่พบบ่อย การดำเนินการนี้สามารถ
เป็นตัวแทนที่สอดคล้องกัน (0, 1) -matrix ซึ่งเต็มไปด้วย 1 เมื่อ
สีของพวกเขามีการเปลี่ยนแปลง ตอนนี้เรากำหนดเมทริกซ์ที่ส่งผลในการดำเนินการของการ
คลิกที่ปุ่ม เมื่อเราดำเนินการเกี่ยวกับการกำหนดค่าเริ่มต้นที่กำหนดก็จะ
ได้รับการพิจารณาการเพิ่มใหม่ (0, 1) -matrix เพื่อ ICM ในสมัยที่ 2 นอกจากนี้.
ตอนนี้เรากำหนด (0, 1) -matrix ของการดำเนินการในแต่ละโดยการคลิกที่ ปุ่มด้านล่าง.
ความละเอียด 1.2 [9] ขอ Mk ∈มิลลิเมตร× n (R) เป็นน× n เมทริกซ์ (ที่ 1 ≤
≤ฉันล้านบาท) Mk คือ (0, 1) -matrix มีตำแหน่งเลข k ของด้านบนและด้านล่าง
และด้านซ้ายตำแหน่งและตำแหน่งที่เหมาะสมคือ 1 และส่วนที่เหลือเป็น 0 คือมันสามารถ
เขียนเป็นเหลือ MIJ = 0
Mk = [MIJ] ม. × n ที่ k = n (i - 1) + เจ
ด้วย
?
MIJ = 1 ไมล์เจไมล์ = + 1 = ญไมล์ J-1 = ไมล์เจ + 1 = 1
อื่น MIJ = 0
ตัวอย่างเช่น สองการฝึกอบรม M1 และ M6 ขนาด 3 × 4 และสอดคล้องกัน
เมทริกซ์ของการดำเนินการที่ (1,1) ตำแหน่ง (เลข 1) และ (2,2) ตำแหน่ง (
เลข 6) จะได้รับในรูปที่ 4
,
รูปที่ 4 : ผลการฝึกอบรมของ 3 × 4 เกมหลังผ้าคลิก
ดุก 1474 อาทิตย์คิมซาง-Gu ลีและ Faqir เมตร Bhatti
กระบวนการของการเล่นเกมผ้าถือได้ว่าเป็นนอกจากนี้
จากการรวมเชิงเส้นของ Mk และ ICM B เพื่อให้เมทริกซ์ของทั้งหมด 1 หรือ
ทั้งหมด 0 มันสามารถเขียนในรูปแบบต่อไปนี้เพื่อจบเกม.
B + c1M1 c2M2 + + ··· + cmnMmn = O (1)
หรือ
B + c1M1 c2M2 + + ··· + cmnMmn = J (2)
(ที่ O คือ ศูนย์เมทริกซ์และเจเป็นเมทริกซ์ที่มีรายการทั้งหมด 1. )
ที่จะทำให้มันง่ายเราสามารถพิจารณาเมทริกซ์ B, J และ O เป็นล้าน× 1
เวกเตอร์คอลัมน์ ตัวอย่างเช่น ICM B3 × 4 ในรูปที่ 3 ถือได้ว่าเป็น
เวกเตอร์คอลัมน์ต่อไป.
(0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1,0) = [0 1 0 1 0 0 0 1 1 0 1 0] T (3)
พิจารณานี้สามารถนำไป Mk ทั้งหมดของ เราเขียนเมทริกซ์ Mk เป็น
mk เวกเตอร์คอลัมน์ B และเมทริกซ์เป็นเวกเตอร์คอลัมน์ขและการฝึกอบรม J
และ O เป็นเวกเตอร์คอลัมน์เจและ 0 ตามลำดับ แล้วแบบจำลองทางคณิตศาสตร์
ของเกมผ้าสามารถเขียนเป็นการแก้ปัญหาสำหรับการเชิงเส้นอย่างง่าย
ระบบสมการ เราจะให้งบทฤษฎีบทต่อไปในภายหลัง
ใช้.
ทฤษฎีบท 1.3 [9] ขอเวกเตอร์ mk เป็นเวกเตอร์คอลัมน์ต่อไปนี้
เมทริกซ์เอ
=
?
m1 | m2 | ··· | MMN
?
(4)
และเมทริกซ์ B สามารถเขียนเป็นคอลัมน์ขเวกเตอร์และการฝึกอบรม
J และ O เป็นคอลัมน์เวกเตอร์เจและ 0 ตามลำดับ ก่อนหน้านี้สมการ (1.1)
และ (1.2) สามารถเขียนเป็น
Ax = -b (5)
หรือ
Ax = เจ - ข (6)
ที่ x = (c1, c2, CMN....)
ลำดับฟีโบนักชีและชนะ เงื่อนไขสำหรับเกมผ้า 1475
ดังนั้นถ้าเราหาทางออกสำหรับระบบเชิงเส้นของสมการ (1.5) (หรือ
(1.6)) แล้วเราสามารถให้การแก้ปัญหาสำหรับเกมรับผ้าที่มีขนาดใด.
ถ้าเราสามารถหาทางแก้ปัญหา ของระบบสมการเชิงเส้นของเราสามารถคลิกเพียง
สแควร์ซึ่งได้รับการแต่งตั้งเพื่อให้สี่เหลี่ยมทั้งหมดที่มีสีเดียวกันและมันหมายถึงการ
ที่เราชนะเกมนี้ lighout จากการกำหนดค่าที่กำหนด ในกรณีนี้เราพูดแบบนี้
เกมเป็นผ้าชัยชัยและเงื่อนไขขึ้นอยู่กับความมั่นคง
ของระบบสมการเชิงเส้นของ ตอนนี้เราจะตรวจสอบคุณสมบัติของ
เมทริกซ์เอในบทความนี้เราจะวิเคราะห์เมทริกซ์จะให้คำตอบสำหรับ
เงื่อนไขของชัยม. ×เกม n ผ้า.
2 บล็อก tridiagonal เมทริกซ์
มองไปที่ 3 × 4 เกมผ้าเราสามารถมี สิบสอง 12 × 1 เวกเตอร์ของ mk
และ 12 × 12 เมทริกซ์ที่มีคอลัมน์ mk ที่ทำจาก Mk ดังต่อไปนี้.
⎡
⎢⎣
1 1 0 0
1 0 0 0
0 0 0 0
⎤
⎥⎦
,
⎡
⎢⎣
1 1 1 0
0 1 0 0
0 0 0 0
⎤
⎥⎦
,
⎡
⎢⎣
0 1 1 1
0 0 1 0
0 0 0 0
⎤
⎥⎦
,
⎡
⎢⎣
0 0 1 1
0 0 0 1
0 0 0 0
⎤
⎥⎦, (
7)
⎡
⎢⎣
1 0 0 0
1 1 0 0
1 0 0 0
⎤
⎥⎦
,
⎡
⎢⎣
0 1 0 0
1 1 1 0
0 1 0 0
⎤
⎥⎦
,
⎡
⎢⎣
0 0 1 0
0 1 1 1
0 0 1 0
⎤
⎥⎦
,
⎡
⎢⎣
0 0 0 1
0 0 1 1
0 0 0 1
⎤
⎥⎦
(8)
⎡
⎢⎣
0 0 0 0
1 0 0 0
1 1 0 0
⎤
⎥⎦
,
⎡
⎢⎣
0 0 0 0
0 1 0 0
1 1 1 0
⎤
⎥⎦
,
⎡
⎢⎣
0 0 0 0
0 0 1 0
0 1 1 1
⎤
⎥⎦
,
⎡
⎢⎣
0 0 0 0
0 0 0 1
0 0 1 1
⎤
⎥⎦
(9)
=
⎡
⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣
1 1 0 0 1 0 0 0 0 0 0 0
1 1 1 0 0 1 0 0 0 0 0 0
0 1 1 1 0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 1 1 1 0 0 1 0 0
0 0 1 0 0 1 1 1 0 0 1 0
0 0 0 1 0 0 1 1 0 0 0 1
0 0 0 0 1 0 0 0 1 1 0 0
0 0 0 0 0 1 0 0 1 1 1 0
0 0 0 0 0 0 1 0 0 1 1 1
0 0 0 0 0 0 0 1 0 0 1 1
⎤
⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦
( 10)
เมทริกซ์นี้เป็นบล็อกเมทริกซ์ tridiagonal ดังแสดงในรูปที่ 5 นี้ใน
กรณีที่เรามีสาม tridiagonal เมทริกซ์ที่มีขนาด 4 × 4 หลักในแนวทแยง.
นับตั้งแต่เกมที่เป็นเกมผ้าขนาด 3 × 4 จำนวน แถวหมายถึง
1476 ดุกอาทิตย์คิมซาง-Gu ลีและ Faqir เมตร Bhatti
จำนวน tridiagonal การฝึกอบรมในแนวทแยงหลักและจำนวนของ
คอลัมน์หมายความว่าขนาดของเมทริกซ์ tridiagonal นอกจากนี้เราคุย
สังเกตของเราเพื่อให้เป็นรูปสี่เหลี่ยมผืนผ้าขนาดทั่วไปม. ×เกม n ผ้า.
รูปที่ 5: โครงสร้างบล็อกของเมทริกซ์ที่สอดคล้องกันสำหรับเกมผ้า
ขนาด 3 × 4
รูปที่ 6: โครงสร้างบล็อกของเมทริกซ์ที่สอดคล้องกันสำหรับเกมผ้า
ขนาด ม. × n
โดยทั่วไปการวิเคราะห์ของการดำรงอยู่ของการแก้ปัญหาในระบบเชิงเส้นของ
สมการ Ax = -b หรือ Ax = เจ - ขจะขึ้นอยู่กับค่า det (A) หาก det (A) คือ
ไม่เป็นศูนย์แต่ละระบบมีวิธีการแก้ปัญหาที่ไม่ซ้ำกัน ในเกมผ้านี้
หมายถึงวิธีการแก้ปัญหาปุ่มที่เราคลิกเพื่อทำให้ทุกปุ่มเดียวกับ
สี ในคำอื่น ๆ ที่มีความรู้พื้นฐานของพีชคณิตเชิงเส้นคือพอที่จะจัดการ
ไม่เพียง 3 × 3 เกมผ้า แต่ยังเป็นรูปสี่เหลี่ยมผืนผ้าขนาดทั่วไปม. × n
เกมผ้า.
ลำดับฟีโบนักชีและเงื่อนไขชนะสำหรับเกมผ้า 1477
ที่นี่เราให้ งบทฤษฎีบทอื่น.
ทฤษฎีบท 2.1 [10] สมมติว่าเมทริกซ์เป็นบล็อก tridiagonal เมทริกซ์ที่สอดคล้องกัน
ให้มีขนาดสี่เหลี่ยมทั่วไปม. × n เกมผ้า หาก det (A)? = 0
เกมรับเป็นชัย และเวกเตอร์คอลัมน์ขจาก B ICM
สภาพเริ่มต้นที่กำหนด-1b ช่วยให้การแก้ปัญหาที่ไม่ซ้ำกันสำหรับทั่วไป
ขนาดสี่เหลี่ยมม. ×เกม n ผ้า.
แม้สำหรับกรณีของ det (A) = 0 เราอาจจะหาทางแก้ไขปัญหา สำหรับทั่วไป
ขนาดสี่เหลี่ยมม. × n เกมผ้า แต่ในกรณีนี้การดำรงอยู่ของ
การแก้ปัญหาขึ้นอยู่กับขเวกเตอร์ที่มาจากสภาวะเริ่มต้น
การวิเคราะห์เกี่ยวกับกรณีนี้ได้รับการจัดการในการทำงานของเราก่อนหน้านี้ [10].
3 ลำดับฟีโบนักชีและปูกระเบื้องบนผ้า
เกม
ในส่วนก่อนหน้านี้เราใช้ความจริงที่ว่าบล็อกเมทริกซ์สามเหลี่ยม
ที่สร้างขึ้นโดยเกมผ้ามีข้อมูลสำคัญที่เกี่ยวข้อง
กับ การตัดสินใจของ winnability สำหรับการเล่นเกม หากปัจจัยของ
เมทริกซ์บล็อก tridiagonal ไม่เป็นศูนย์นั้นมีอยู่วิธีการแก้ปัญหาที่ไม่ซ้ำกันที่จะชนะ
ม. ที่กำหนดโดยพล× n เกมผ้า กับการขัดแย้งเหล่านี้เราได้ให้
รายชื่อของปัจจัยทั้งหมดของบล็อกเมทริกซ์สามเหลี่ยมที่นำมาจาก 1 × 1
เกมผ้า 24 × 24 เกมในผ้า [9].
รูปที่ 7: ปัจจัยจากตารางที่ 1 × 1 เกมผ้า 24 × ผ้า 24
เกม
1478 ดุกอาทิตย์คิมซาง-Gu ลีและ Faqir Bhatti เมตร
ในขณะที่เราเห็นในตารางในรูปที่ 7 มีกฎการปูกระเบื้องที่น่าสนใจที่
มีสองรูปแบบ รูปแบบแรกคือการปูกระเบื้องโดย 6 × 6 บล็อกที่เรา
จะเห็นในรูปที่ 8 และ 9 และรูปแบบที่สองคือกฎศูนย์การบรรจุใน
ตำแหน่ง 5k-1 (ในรูปที่ 9 บางตำแหน่งจะเต็มไปด้วยความแตกต่าง 2.
นอกจากนี้ปัจจัยทั้งหมดนอกจากนี้ยังมีศูนย์) ใน [9] ผู้เขียนกล่าวถึงโดยไม่ต้อง
พิสูจน์ปูกระเบื้องนี้สามารถนำมาใช้สำหรับขนาดใหญ่เกมผ้า ตอนนี้เรา
ให้พิสูจน์ทางคณิตศาสตร์สำหรับเดียวกัน.
รูปที่ 8: รูปแบบครั้งแรก: ปูกระเบื้องของ 6 × 6 บล็อก
รูปที่ 9: สองรูปแบบการปูกระเบื้องในตารางของปัจจัยใน
ผลลัพธ์เหล่านี้จะได้รับโดยใช้คุณสมบัติของปัจจัยสำหรับ
บล็อก เมทริกซ์ tridiagonal จากส่วนก่อนหน้านี้บล็อก tridiagonal
รูปแบบเมทริกซ์สูตรที่กำหนดไว้ในสมการ (3.1) ในกรณีที่ K คือเมทริกซ์ tridiagonal
ที่มีตำแหน่งอยู่ในรายการเส้นทแยงมุมหลักและ I เป็นเมทริกซ์เอกลักษณ์.
ลำดับฟีโบนักชีและเงื่อนไขชนะสำหรับเกมผ้า 1479
=
⎡
⎢⎢⎢⎢⎢⎢⎢⎣
KIO ··· O
ฉัน KI ··· O
O
. . .
. .
. O
O OIKI
OOOIK
⎤
⎥⎥⎥⎥⎥⎥⎥⎦
ล้านล้าน×
, K =
⎡
⎢⎢⎢⎢⎢⎢⎢⎣
1 1 โอ··· O