First Round of the 1988 Spaninsh Olympiad
 

เพิ่งได้ E-Book ของ Polya เล่มหนึ่ง เห็นโจทย์ดูแล้วน่าสนใจดี ลองทำสักข้อนะครับ :happy:

First Round of the 1988 Spaninsh Olympiad

จำนวนนับ $1 , 2 , 3 , \ldots , n^2$ ถูกนำมาเขียนในเมตริกซ์ขนาด $n \times n$ ดังนี้
\[A = \pmatrix{
1 & 2 & \cdots & n \\
n+1 & n+2 & \cdots & 2n \\
2n+1 & 2n+2 & \cdots & 3n \\
\vdots & \vdots & \ddots & \vdots \\
(n-1)n+1 & (n-1)n+2 & \cdots & n^2
}\]
ผลรวม $S$ หาได้ดังนี้

สมาชิกตัวแรก $x_1$ ที่จะนำมารวมใน $S$ จะเลือกแบบสุ่มจากสมาชิกของ $A$ หลังจากนั้นสมาชิกทุกตัวของ $A$ ที่เหลืออยู่ ที่อยู่ในแถวและคอลัมน์เดียวกับ $x_1$ จะถูกขีดฆ่าทิ้งทั้งหมด
สมาชิกตัวที่สอง $x_2$ ที่จะนำมารวมใน $S$ จะเลือกแบบสุ่มจากสมาชิกที่เหลือของ $A$ หลังจากนั้นสมาชิกทุกตัวของ $A$ ที่เหลืออยู่ ที่อยู่ในแถวและคอลัมน์เดียวกับ $x_2$ จะถูกขีดฆ่าทิ้งทั้งหมด
ทำแบบนี้ไปเรื่อยๆจนกระทั่ง ไม่เหลือสมาชิกของ $A$

จงพิสูจน์ว่า ผลรวม $S$ ที่ได้มีค่าเท่ากันเสมอ สำหรับทุกการสุ่มเลือก $x_1 , x_2 , \ldots$

แนวคิดของผม คร่าวๆ คือ ไม่ว่า่จะเลือกแบบไหนก็ตาม ในแต่ละหลัก(หรือแถว)ของ $A$ จะมีสมาชิกตัวเดียวเท่านั้นที่ถูกเลือก
เพราะ $a_{(i+1)j}-a_{ij}=1$ และ $a_{i(j+1)}-a_{ij}=n$ จึงไม่เสียนัยทั่วไปที่จะเลือกสมาชิกในแนวแทยงมุมทีละตัว
ผลรวมที่มีค่าคงที่คือ $(1+2+\cdots+n)+n(n-1)=\frac{n}2(3n-1)$

แนวทางเป็นอย่างที่คุณ nongtum บอกมา แต่ตอนท้ายอาจจะเขียนผิดไปนิดหน่อย

พิจารณาค่าของ $a_{s,t}$ ใดๆ จะพบว่า $a_{s,t} = (s-1)n + t$

การเลือกสมาชิกของ $A$ มารวมใน $S$ ตามวิธีข้างต้น จะได้สมาชิกของ $A$ มาแถวละตัว หรือคอลัมน์ละตัว
เราได้ $a_{s,t}$ มา $n$ ตัว โดยที่ $s$ ไม่ซ้ำกัน และ $t$ ไม่ซ้ำกันเลย
ดังนั้น ผลรวมที่ได้ หาได้จากการแทนค่า $s$ และ $t$ ตั้งแต่ $1$ ถึง $n$ จึงได้
$\begin{array}{rcl}
S & = & (n + 2n + 3n + \cdots + (n-1)) + (1 + 2 + 3 + \cdots + n) \\
& = & \frac{n^2(n-1)}{2} + \frac{n(n+1)}{2} \\
& = & \frac{n(n^2+1)}{2}
\end{array}$

ใช่ Polya Footsteps รึเปล่าครับพี่ TOP เพิ่งได้มาเหมือนกัน :D

ผมคิดแบบนี้ครับ:)
$\displaystyle{A=\bmatrix{0 & 0 & \cdots & 0 \\ n & n & \cdots & n \\ \vdots & \vdots & \ddots & \cdots \\ (n-1)n & (n-1)n & \cdots & (n-1)n}+\bmatrix{1 & 2 & \cdots & n \\ 1 & 2 & \cdots & n \\ \vdots & \vdots & \ddots & \cdots \\ 1 & 2 & \cdots & n}}$
เนื่องจากการเลือกสมาชิก n ตัวมาจาก A จะได้ว่าแต่ละตัวไม่อยู่ในแถวเดียวกับตัวอื่นละหลักเดียวกันตัวอื่น
ดังนั้นผลรวมมีค่าเป็น$\displaystyle{(0+n+\cdots +(n-1)n)+(1+2+\cdots +n)=\frac{n(n^{2}+1)}{2}}$
ทำไปทำมาคล้าย ๆ ของพี่ TOP เลยครับ:p

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

จริงๆ อยากได้เป็นเล่มๆ นะครับเนี่ย แต่กลัวไม่มีที่จะเก็บ :haha: