เท่าไหร่ $3\times 3$ อาร์เรย์ที่มีตัวเลขจาก $1$ ถึง $9$ มีคำสั่งซื้อเพิ่มขึ้นไหม?

Aug 16 2020

รายการในไฟล์ $3 \times 3$ อาร์เรย์รวมตัวเลขทั้งหมดจาก $1$ ผ่าน $9$จัดเรียงเพื่อให้รายการในทุกแถวและคอลัมน์อยู่ในลำดับที่เพิ่มขึ้น อาร์เรย์ดังกล่าวมีจำนวนเท่าใด

นี่คือคำถามเกี่ยวกับ Combinatorics ฉันลองใช้ tableaus และใช้ hook numbers แต่ไม่เข้าใจหลังจากนั้นโปรดบอกวิธีแก้ปัญหานี้ มันจะง่ายกว่าสำหรับฉันถ้าแก้โดยใช้คอมบิเนเตอร์ปกติ แต่ไม่มีข้อ จำกัด เป็นทางเลือกของคุณ

คำตอบ

1 Moko19 Aug 16 2020 at 22:15

ใช้สัญกรณ์ $(A,B,C)$ เพื่ออธิบายจำนวน $C$ ตั้งอยู่ใน $A$ แถวและ $B$คอลัมน์. เนื่องจากความสมมาตรการเปลี่ยนแนว (การสะท้อนข้ามเส้นทแยงมุมหลัก) ของสารละลายใด ๆ จึงเป็นวิธีการแก้ปัญหาที่แตกต่างกันกล่าวคือถ้าเรามีวิธีแก้ปัญหา:$$\{(A_1,B_1,1), (A_2,B_2,2), (A_3,B_3,3), (A_4,B_4,4), (A_5,B_5,5), (A_6,B_6,6), (A_7,B_7,7), (A_8,B_8,8), (A_9,B_9,9)\}$$ จากนั้นเรายังมีวิธีแก้ไข: $$\{(B_1,A_1,1), (B_2,A_2,2), (B_3,A_3,3), (B_4,A_4,4), (B_5,A_5,5), (B_6,A_6,6), (B_7,A_7,7), (B_8,A_8,8), (B_9,A_9,9)\}$$

เนื่องจากทุกแถวและคอลัมน์จะต้องมีลำดับที่เพิ่มขึ้นเราจึงรู้ว่าโซลูชันของเราจะต้องรวมไว้ด้วย $(1,1,1)$ และ $(3,3,9)$.

เรามีสองทางเลือกสำหรับตำแหน่งที่จะใส่หมายเลข $8$. เนื่องจากสมมาตรเราจะพิจารณาเฉพาะคำตอบที่มี$(3,2,8)$และจะต้องเพิ่มจำนวนโซลูชันเป็นสองเท่า

ตอนนี้เรามีสองทางเลือกว่าจะใส่ที่ไหน $7$:

กรณีที่ 1: $(3,1,7)$

จำนวน $6$ ถูกล็อคเป็น $(2,3,6)$. จำนวน$5$ สามารถอยู่ใน $(2,2,5)$ หรือ $(1,3,5)$. ถ้า$(2,2,5)$แล้วก็ตัวเลข $2,3,4$ต้องอยู่ในสามจุดที่เหลือ ทันทีที่เราเลือกสิ่งที่อยู่ใน$(2,1,X)$จากนั้นส่วนที่เหลือจะถูกล็อคเข้าที่โดยให้สามวิธีด้วยกัน $(3,1,7)$ และ $(2,2,5)$. ถ้า$(1,3,5)$แล้วเราต้องมี $(2,2,4)$และมีเพียงอย่างใดอย่างหนึ่ง $(1,2,2)$ และ $(2,1,3)$ หรือ $(1,2,3)$ และ $(2,1,2)$ สำหรับอีกสองวิธี

กรณีที่ 2: $(2,3,7)$

ตัวเลข $5$ และ $6$จะต้องอยู่ในจุดสองในสามจุดของแนวแอนไดทแยงมุมหลัก (ด้านบนขวาสี่เหลี่ยมกลางและด้านล่างซ้าย) ดังนั้นจึงเป็น$3!=6$วิธีการกำหนด ในสองกรณีที่ไม่มีใครอยู่ในช่องว่างตรงกลางหมายเลข$4$ ต้องอยู่ในช่องว่างตรงกลางและมีการจัดเรียงตัวเลขที่เป็นไปได้สองแบบ $2$ และ $3$. ในแต่ละสี่กรณีอื่น ๆ มีสองกรณีที่หมายเลข$4$อยู่ในช่องว่างที่เหลืออยู่บนแนวต้านหลักและอีกส่วนหนึ่งที่ไม่มี ผลลัพธ์นี้จะมีทั้งหมด 16 ข้อหาก$(2,3,7)$.

ดังนั้นจำนวนการเตรียมการทั้งหมดคือ $2(3+2+2\cdot2+4\cdot3)=42$

1 BarryCipra Aug 31 2020 at 16:36

$1$ และ $9$ต้องไปที่มุมซ้ายบนและมุมขวาล่างอย่างชัดเจนตามลำดับ มันง่ายที่จะเห็นว่าไฟล์$5$ ไม่สามารถอยู่ติดกับทั้ง $1$ หรือ $9$ดังนั้นจึงต้องอยู่ในหนึ่งในสามจุดบนเส้นทแยงมุม "ต่อต้าน" การประดิษฐ์สัญกรณ์เล็กน้อยเราสามารถเขียนจำนวนความเป็นไปได้เป็น

$$\#\pmatrix{1&*&\\*&5&-\\&-&9}+2\times\#\pmatrix{1&*&5\\*&&-\\&-&9}$$

ที่ไหน "$\#$"ของ $3\times3$ อาร์เรย์แสดงถึงจำนวนโซลูชันด้วย $1$, $5$และ $9$ ในแต่ละจุดที่ได้รับมอบหมาย $*$ เข้าใจว่าเป็นตัวเลขระหว่าง $1$ และ $5$ และแต่ละ $-$ จำนวนระหว่าง $5$ และ $9$. "$2\times\,$"สำหรับความสมมาตรที่จะมี $5$ที่มุมล่างซ้ายมือ โดยสมมาตรเดียวกันเรามี

$$\#\pmatrix{1&*&\\*&5&-\\&-&9}=2\times\#\pmatrix{1&*&*\\*&5&-\\-&-&9}$$

และตอนนี้มันง่ายที่จะเห็นว่าทั้งสาม $*$สามารถกรอกตัวเลขได้ $2$, $3$และ $4$ ในเวลาเพียง $3$ วิธีต่างๆและเช่นเดียวกันสำหรับทั้งสาม $-$ด้วยตัวเลข $6$, $7$และ $8$, ดังนั้น

$$\#\pmatrix{1&*&\\*&5&-\\&-&9}=2\times3\times3$$

อาร์กิวเมนต์สมมาตรที่แตกต่างกันบอกเรา

$$\#\pmatrix{1&*&5\\*&&-\\&-&9}=2\times\#\pmatrix{1&*&5\\*&*&-\\-&-&9}$$

และในกรณีนี้คือ $4$ มีเพียงจุดเดียวที่สามารถเข้าไปได้:

$$\#\pmatrix{1&*&5\\*&*&-\\-&-&9}=\#\pmatrix{1&*&5\\*&4&-\\-&-&9}=2\times3$$

รวมทุกอย่างเข้าด้วยกันจำนวนการจัดเตรียมทั้งหมดคือ

$$(2\times3\times3)+(2\times2\times\times2\times3)=18+24=42$$

หมายเหตุ (เพิ่มในภายหลัง): เพื่อความชัดเจนและแม่นยำสมมาตร "ค่อนข้างแตกต่าง" ที่บอกเรา

$$\#\pmatrix{1&*&5\\*&*&-\\-&-&9}=\#\pmatrix{1&*&5\\*&-&-\\*&-&9}$$

คือการสะท้อนข้ามเส้นทแยงมุม "ต่อต้าน" ตาม (หรือนำหน้า) โดยการแทนที่ด้วยตัวเลข $k\to10-k$ แต่ละ $k\in\{1,2,3,4,5,6,7,8,9\}$.