โจทย์เตรียมตัวเข้าค่าย

[Mastermander]

คุณ nithi_rung ตอบ ณ เวลาที่สวยงามมาก

[warut]

จริงๆด้วยครับ ผมลืมคิดจุดนั้นไปเลย ขอบคุณคุณ nithi_rung ที่มาช่วยแก้ไขให้ครับ

ผมทำข้อนี้ เพราะตอนนั้นผมกำลัง scan หาว่ามีคำถามไหนในกลุ่มปัญหาคณิตศาสตร์โอลิมปิก และ อุดมศึกษา ที่ยังไม่มีคนตอบ แล้วมาเจอที่น้อง gools ตอบข้อนี้ไว้ ซึ่งผมค่อนข้างมั่นใจว่าไม่ถูกต้อง ก็เลยตอบไปโดยคิดในใจ ไม่ได้ทดลงกระดาษให้ถี่ถ้วนก่อน ผลก็คือผิดครับ จะเห็นว่าความรอบคอบมีความสำคัญมากๆในการทำโจทย์คณิตศาสตร์ ดังนั้นปกติผมจึงทำในกระดาษทดเสมอ แล้ว double check โดยคิดอีกวิธีหนึ่ง (เช่นนับตรงๆเลย) หรือใช้คอมพ์เช็คครับ

[R-Tummykung de Lamar]

ข้อความเดิมของคุณ warut:
น่าจะเป็น $n(n-1)^{n-2}(n-2)$ เมื่อ $n>2$ นะครับ เพราะ $f(n)$ จะเลือกได้เพียง 2 ค่า เนื่องจาก $f(n)\ne f(n-1)$ และ $f(n)\ne f(1)$ ด้วย

ที่พี่ warut นับมาเป็นกรณีของ $f(n-1)\not=f(1)$
ก็ ถ้า $f(n-1)=f(1)$ มันจะคือ
$$f(1)\not=f(2)\not=...\not=f(n-2)\not=f(1)$$
ใช้แนวคิดแบบเดิมครับ มันคือ
$n(n-1)^{n-4}(n-2)$
ครับ นี่คือกรณีที่ $f(n-3)\not=f(1)$
ทำอย่างนี้ไปเรื่อยๆ จะได้

$\Huge \mathbf{ \text{กรณี n คี่}}$

กระจายไปตอนท้ายๆ
$f(1)\not=f(2)\not=f(3)\not=f(1)$
พอจะลด มันจะกลายเป็น กรณีที่ $f(1)=f(2)$ ซึ่งเกิดไม่ได้เพราะ $f(1)\not=f(2)$ นั่นคือ
$$n(X)=n(n-2)[(n-1)^1+(n-1)^3...+(n+1)^{n-4}+(n+1)^{n-2}]$$
$$=n(n-2)[\frac{(n-1)((n-1)^{2(\frac{n-1}{2})}-1)}{(n-1)^2-1}]$$
$$=(n-1)^n-(n-1)$$

$\Huge \mathbf{ \text{กรณี n คู่}}$

กระจายไปตอนท้ายๆ
$f(1)\not=f(2)\not=f(3)\not=f(4))\not=f(1)$
ยังเป็น $n(n-1)^{2}(n-2)$ อยู่
กรณี $f(3)=f(1)$
$f(1)\not=f(2)\not=f(1)$
ตรงนี้ ไม่ใช่ $n(n-1)^{0}(n-2)$ แล้วครับ แต่เป็น $n(n-1)$ นั่นคือ
$$n(X)=n(n-2)[(n-1)^2+(n-1)^4...+(n+1)^{n-4}+(n+1)^{n-2}]+n(n-1)$$
$$=n(n-2)[\frac{(n-1)^2((n-1)^{2(\frac{n-2}{2})}-1)}{(n-1)^2-1}]+n(n-1)$$
$$=(n-1)^n-(n-1)^2+n(n-1)$$
$$=(n-1)^n+(n-1)(1)$$


จากทั้งสองกรณีสรุปได้ว่า
$$(n-1)^{n}+(-1)^{n}(n-1)$$
ตรงตามที่พี่ nithi_rung ตอบมาเลยครับ ไม่ทราบพี่คิดวิธีไหนครับ

[warut]

ความเชี่ยวชาญด้าน combinatorics ของน้อง R-Tummykung de Lamar ล้ำหน้าผมไปไกล จนผมตามไม่ทันเลยครับ คือในกรณีที่ $f(n-1)=f(1)$ ทำไมได้ $n(n-1)^{n-4}(n-2)$ แบบล่ะครับ ทำไมเราไม่ต้องนับด้วยว่าเราสามารถเลือก $f(n)$ ได้อีก $n-1$ วิธี ซึ่งน่าจะทำให้ได้เป็น $n(n-1)^{n-3}(n-2)$ แบบ งงมากเลยครับตรงนี้

แต่ว่าคำตอบ $(n-1)^{n}+(-1)^{n}(n-1)$ นี่คงถูกต้องไม่มีปัญหาแล้วล่ะ เพราะผมลองนับด้วยคอมพ์ดูจริงๆ ในกรณีที่ $n\le8$ แล้วได้เท่ากันครับ

ผมก็อยากเห็นวิธีคิดของคุณ nithi_rung เหมือนกัน อยากรู้ที่มาของโจทย์ด้วย ถ้าย้อนไปถึงต้นฉบับของฝรั่งได้ด้วยจะยิ่งดีมากเลยครับ

[R-Tummykung de Lamar]

ข้อความเดิมของคุณ warut:
ความเชี่ยวชาญด้าน combinatorics ของน้อง R-Tummykung de Lamar ล้ำหน้าผมไปไกล จนผมตามไม่ทันเลยครับ คือในกรณีที่ $f(n-1)=f(1)$ ทำไมได้ $n(n-1)^{n-4}(n-2)$ แบบล่ะครับ ทำไมเราไม่ต้องนับด้วยว่าเũ 9;าสามารถเลือก $f(n)$ ได้อีก $n-1$ วิธี ซึ่งน่าจะทำให้ได้เป็น $n(n-1)^{n-3}(n-2)$ แบบ งงมากเลยครับตรงนี้

แต่ว่าคำตอบ $(n-1)^{n}+(-1)^{n}(n-1)$ นี่คงถูกต้องไม่มีปัญหาแล้Ū 3;ล่ะ เพราะผมลองนับด้วยคอมพ์ดูจũ 9;ิงๆ ในกรณีที่ $n\le8$ แล้วได้เท่ากันครับ

ผมก็อยากเห็นวิธีคิดของคุณ nithi_rung เหมือนกัน อยากรู้ที่มาของโจทย์ด้วย ถ้าย้อนไปถึงต้นฉบับของฝรัŭ 6;งได้ด้วยจะยิ่งดีมากเลยครั 610;

อืม วิธีผมผิดจริงด้วย (แต่ไหงคำตอบออกมาเท่ากันหว$ 56;า) ไม่ได้ล้ำหน้าอะไรหรอกครับ ถ้าเป็น แสดงวิธีทำคงได้ 0 แล้ว
ผมลองคิดแบบนั้นอยู่

พี่ warut ครับ ไม่ทราบว่า ที่ $n=5$
ได้เท่าไหร่ครับ 1020 หรือ 1200

[nithi_rung]

แสดงวิธีคิดให้ดู 2 วิธี นะครับ โดยจะขอละรายละเอียดบางส่วนไว้

วิธีแรก ใช้หลักการนำเข้าตัดออก
กรณี $ n=1 $ จะได้ว่าไม่มีฟังก์ชัน มิฉะนั้น $ f(1)/not=f(n)=f(1) $
กรณี $ n=2 $ จะได้ว่ามี 2 ฟังก์ชัน คือ $ f(1)=1, f(2)=2 $ และ $ f(1)=2, f(2)=1 $

ต่อไปพิจารณากรณี $ n\ge3 $
สำหรับ $ i=1,2,...,n-1 $ ให้ $ B_{ i }=\{f\in U|f(i)=f(i+1)\} $
และให้ $ B_{ n }=\{f\in U|f(n)=f(1)\} $
จะเห็นว่า $ X=\bigcap_{i=1}^{n} B_{ i }\prime $
ดังนั้น $ n(X)=\sum_{i=0}^{n}(-1)^{i}S_{i} $
เมื่อ $ S_{ 0 }=n(U) $ และ $ S_{i}=\sum_{1\le j_{ 1 }\le ... \le j_{ i }\le n}n\left(\bigcap_{k=1}^{i} B_{ j_{ k } }\right) $ สำหรับ $ i=1,2,...,n $
จะเห็นว่า $ S_{0}=n^n, S_{i}={n \choose i}n^{n-i} $ เมื่อ $ i=1,2,...,n-1 $ และ $ S_{n}=n $ ดังนั้น
$$ n(X)=\sum_{i=0}^{n}(-1)^{i}S_{i}$$
$$=\sum_{i=0}^{n-1}{n \choose i}(-1)^{i}n^{n-i} + (-1)^n $$
$$ =\sum_{i=0}^{n}{n \choose i}(-1)^{i}n^{n-i} - (-1)^{n} + (-1)^n $$
$$ =(n-1)^n+(-1)^n(n-1) $$

วิธีที่สอง อันนี้คงต้องให้ช่วยกันดูละครับ เพราะจัดรูปตอนท้ายไม่ได้ (หรือว่าเป็นไปไม่ได้ที่จะจัดรูป? หรือว่าผมคิดผิด )
(เราจะพิจารณากรณี $n\ge3$ โดยกรณี $n=1,2$ นั้นทำเหมือนกรณีแรก)
ขั้นแรกเลือกค่าของ $f(1)$ ก่อน เลือกได้ n วิธี
ต่อไปพิจารณาจำนวน $k\in A-\{1\}$ ซึ่ง $f(k)=f(1)$ (เห็นได้ชัดว่า $k\not=2$ ดังนั้นมีค่าที่เป็นไปได้อยู่ $n-2$ ค่า)
สมมติว่ามีอยู่ $m-1$ จำนวน (จะเห็นว่า $m-1\le\frac{n-2}{2}$)
จะได้ว่า มีจำนวนวิธีการเลือกตำแหน่งของ k ซึ่งมีอยู่ $m-1$ ที่ได้ {n-m-2 \choose m-1} วิธี (ค่อยๆ คิดตามนะครับ ลองนึกถึงการเรียงเลข 1 $m-1$ จำนวน และเลข 0 $n-m-2$ จำนวน โดยเลข 1 ห้ามอยู่ติดกัน)
ต่อไปเลือกค่าของ $f(k+1)$ สำหรับทุก $k\in A$ ซึ่ง $f(k)=f(1)$ (อันนี้รวม k=1 ด้วยนะครับ) จะเลือกได้ $n-1$ วิธี รวมแล้วเลือกได้ $(n-1)^m$ วิธี
ตอนนี้จะเหลือจำนวนอยู่ $n-2m$ ค่า ซึ่งเรายังไม่ได้เลือกค่าฟังก์ชันให้
จำนวนที่เหลือนี้เราเลือกค่าให้แต่ละตัวได้ $n-2$ วิธี คือไม่ให้เท่ากับ $f(1)$ และตัวก่อนหน้า (เช่น $f(k+2)\not=f(k+1)$) รวมเป็น $(n-2)^{n-2m}$ วิธี
ดังนั้น ในกรณีนี้ จะมีจำนวนฟังก์ชันทั้งหมด $n{n-m-2 \choose m-1}(n-1)^m(n-2)^{n-2m}$
เมื่อรวมทุกกรณี จะได้ว่า $n(X)=n\sum_{m=1}^{\lceil \frac{n}{2}\rceil}({n-m-2 \choose m-1}(n-1)^m(n-2)^{n-2m})$
ซึ่งตรงนี้ละครับ ที่ผมจัดรูปต่อไม่ได้

สำหรับวิธีของน้อง R-Tummykung de Lamar นี่อยากให้ดูใหม่นะครับ เพราะว่าจำนวนวิธีการเลือกในขั้นที่เลือก $f(n-1)$ ซึ่งได้ $n(n-1)^{n-2}$ วิธีนั้นมีสองกรณีรวมกันไปแล้ว คือ $f(n-1)=f(1)$ และ $f(n-1)\not=f(1)$

[warut]

ข้อความเดิมของคุณ R-Tummykung de Lamar:
อืม วิธีผมผิดจริงด้วย

อ้าว... ผิดเหรอครับ แล้วทำไมคำตอบมันใช้ได้ล่ะ ยิ่งงงหนัก

ข้อความเดิมของคุณ R-Tummykung de Lamar:
พี่ warut ครับ ไม่ทราบว่า ที่ $n=5$
ได้เท่าไหร่ครับ 1020 หรือ 1200

1020 ครับ

แล้วก็ขอบใจน้อง nithi_rung มากๆครับที่มาแสดงวิธีทำให้ดูถึง 2 แบบ ผมคงต้องใช้เวลาทำความเข้าใจอีกนาน แต่เรื่องจัดรูปนี่ ที่ผมดูคร่าวๆแล้วคิดว่าน่าจะพอทำได้นะ เสร็จแล้วจะมาโพสต์บอกครับ

[Tony]

Suppose that a function $f$ defined on the positive integers satisfies
$$f(1)=1,\ \ f(2)=2,$$
$$f(n+2)=f(n+2-f(n+1))+f(n+1-f(n)) \ \ \ \ (n\geq1).$$
(a) Show that
$(i)\ 0\leq f(n+1)-f(n) \leq 1$
$(ii)$ if $ f(n) $ is odd, then $ f(n+1)=f(n)+1$.
(b) Determine, with justification, all values of n for which
$$f(n)=2^{10}+1$$

[warut]

ตอบน้อง nithi_rung เรื่องจัดรูปน่ะครับ ผมลองเช็คด้วยคอมพ์ (โดยแทนค่า $n$ ด้วยตัวเลขต่างๆ) แล้วปรากฎว่า $$n \sum_{m=1}^ {\lceil \frac{n}{2}\rceil} {n-m-2 \choose m-1} (n-1)^m(n-2)^{n-2m} \ne (n-1)^n+ (-1)^n(n-1)$$ ครับ แต่ไม่ทราบเหมือนกันว่าปัญหามาจากจุดไหนในวิธีที่สอง