คณิตศาสตร์ที่เชื่อมโยงจุดที่เรากำลังจะไปที่ที่เราเคยไป | นิตยสารควอนต้า

สมมติว่าคุณอยู่ในงานปาร์ตี้กับคนอีก 9 คนและทุกคนก็จับมือคนอื่นเพียงครั้งเดียว มีการจับมือกันกี่ครั้ง?

นี่คือ “ปัญหาการจับมือกัน” และเป็นหนึ่งในปัญหาโปรดของฉัน ในฐานะครูสอนคณิตศาสตร์ ฉันชอบมันมากเพราะมีวิธีต่างๆ มากมายที่คุณสามารถหาวิธีแก้ปัญหาได้ และความหลากหลายและความเชื่อมโยงระหว่างกลยุทธ์เหล่านั้นก็แสดงให้เห็นอย่างสวยงามถึงพลังแห่งความคิดสร้างสรรค์ในวิชาคณิตศาสตร์

วิธีแก้ไขอย่างหนึ่งมีดังนี้: เริ่มต้นด้วยการที่แต่ละคนจับมือกันทุกคน คน 9 คน คนละ 10 ครั้ง จะมีการจับมือกัน 90 × 90 = ทั้งหมด 2 ครั้ง แต่วิธีนี้นับการจับมือกันทุกครั้งสองครั้ง — หนึ่งครั้งจากมุมมองของเชคเกอร์แต่ละคน — ดังนั้นจำนวนการจับมือที่แท้จริงคือ $latex frac{45}{XNUMX} = XNUMX$ อาร์กิวเมนต์การนับที่เรียบง่ายและน่ารักสำหรับการชนะ!

ยังมีวิธีแก้ไขปัญหาที่แตกต่างไปจากเดิมอย่างสิ้นเชิง ลองจินตนาการว่าแขกมาถึงทีละคน และเมื่อไปถึง พวกเขาก็จับมือกับทุกคนที่มาร่วมงาน คนแรกไม่มีมือให้สั่น ดังนั้นในงานปาร์ตี้แบบคนเดียวจึงไม่มีการจับมือกันทั้งหมด ตอนนี้คนที่สองเข้ามาจับมือกับคนแรก วิธีนี้จะบวกการจับมือกัน 0 ครั้งในจำนวนการจับมือทั้งหมด ดังนั้นในงานปาร์ตี้ที่มี 1 คน จึงจะมีการจับมือกัน 1 + XNUMX = XNUMX ครั้ง เมื่อบุคคลที่สามมาถึงและจับมือกับแขกสองคนแรก จะเป็นการจับมือกันเพิ่มอีกสองครั้ง การมาถึงของบุคคลที่สี่จะรวมการจับมือกันสามครั้ง และต่อๆ ไป

กลยุทธ์นี้จำลองลำดับของการจับมือแบบวนซ้ำ ซึ่งหมายความว่าแต่ละคำศัพท์ในลำดับจะได้รับการกำหนดโดยสัมพันธ์กับคำศัพท์ที่อยู่ก่อนหน้า คุณอาจคุ้นเคยกับลำดับฟีโบนัชชี ซึ่งเป็นลำดับแบบเรียกซ้ำที่มีชื่อเสียงที่สุด โดยเริ่มจาก 1, 1, 2, 3, 5, 8, 13, 21 และต่อด้วยเทอมต่อๆ ไปแต่ละเทอมเท่ากับผลรวมของสองเทอมก่อนหน้า

ดังที่เราจะเห็นด้านล่าง การเรียกซ้ำเป็นกรอบงานที่ยืดหยุ่นและมีประสิทธิภาพสำหรับการคิดเกี่ยวกับแนวคิดทางคณิตศาสตร์ที่หลากหลาย แม้ว่านักวิชาการอินเดียโบราณอย่างเฮมาจันทราจะได้รับการยกย่องว่ามีความรู้เกี่ยวกับลำดับประเภทนี้ย้อนกลับไปถึงปี 1150 แต่พวกเขาก็ยังคงมีความท้าทายที่น่าสนใจสำหรับนักคณิตศาสตร์ในปัจจุบัน

มาดูกันว่าการคิดแบบวนซ้ำช่วยแก้ปัญหาการจับมือกันได้อย่างไร ถ้าเราปล่อยให้ $latex a_n$ เท่ากับจำนวนการจับมือกันที่ an n-person party เราสามารถแสดงความสัมพันธ์แบบเรียกซ้ำนี้ได้ด้วยสูตรต่อไปนี้:

$ลาเท็กซ์ a_n = a_{n-1} + n–1$

นี่บอกเราว่าจำนวนการจับมือกันที่ n-person party ($latex a_n$) เท่ากับจำนวนการจับมือกันที่ (n − 1)-บุคคลปาร์ตี้ ($latex a_{n-1}$) บวก n − การจับมือกันอีก 1 ครั้ง โดยจับความคิดที่ว่าเมื่อมีคนใหม่มาถึง จะมีการจับมือใหม่จำนวนหนึ่งให้กับการจับมือที่เกิดขึ้นแล้ว

ในปัญหาการจับมือเวอร์ชันเฉพาะของเรา เราต้องการทราบ $latex a_{10}$ ซึ่งเป็นจำนวนการจับมือกันในงานปาร์ตี้ที่มีคน 10 คน เพื่อที่จะพบว่าเราใช้ความสัมพันธ์แบบเรียกซ้ำ

$ลาเท็กซ์ a_{10} = a_9 + 9$

ในการหาค่าของ $latex a_{10}$ เราเพียงแค่ต้องทราบค่าของ $latex a_9$ แล้วบวก 9 ลงไป เราจะหาค่าของ $latex a_9$ ได้อย่างไร? โดยใช้การเรียกซ้ำแน่นอน!

$ลาเท็กซ์ a_9 = a_8 + 8$

ตอนนี้ ในการหาค่าของ $latex a_8$ เราจำเป็นต้องค้นหาค่าของ $latex a_7$ ซึ่งต้องรู้ $latex a_6$ และอื่นๆ ณ จุดนี้ คุณอาจกังวลว่าสิ่งนี้จะดำเนินต่อไปตลอดกาลในลักษณะของการสืบเชื้อสายไม่มีที่สิ้นสุด แต่เมื่อเราไปถึง $latex a_1$ เราก็เสร็จแล้ว เพราะเรารู้ว่าไม่มีการจับมือกันทั้งหมดในงานปาร์ตี้ที่มีคนเดียว

$ลาเท็กซ์ a_1 = 0$

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

$ลาเท็กซ์ a_1 = 0$

$ลาเท็กซ์ a_2 = a_1 + 1 = 0 + 1 = 1$

$ลาเท็กซ์ a_3 = a_2 + 2 = 1 + 2 = 3$

$ลาเท็กซ์ a_4 = a_3 + 3 = 3 + 3 = 6$

$ลาเท็กซ์ cdots$

$ลาเท็กซ์ a_{10} = a_9 + 9 = 36 + 9 = 45$

จากการตรวจสอบรายชื่อ เราจะพบว่ามีการจับมือกันทั้งหมด 45 ครั้งในงานปาร์ตี้ที่มีผู้เข้าร่วม 10 คน ซึ่งเห็นด้วยกับการคำนวณเบื้องต้นของเรา หากคุณเป็นเหมือนนักเรียนของฉัน คุณอาจถามว่าทำไมเราถึงต้องการวิธีอื่นในการแก้ปัญหานี้เมื่อเรารู้คำตอบแล้ว โดยเฉพาะอย่างยิ่งเมื่อแนวทางที่สองนี้ดูเหมือนจะใช้เวลานานกว่า

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

โดยเฉพาะอย่างยิ่ง การเรียกซ้ำมีประโยชน์เพราะมีอยู่ทุกที่ในวิชาคณิตศาสตร์ ตัวอย่างเช่น มันเกิดขึ้นในความสัมพันธ์เชิงเส้นที่ทุกคนเรียนรู้ในชั้นเรียนคณิตศาสตร์ ซึ่งเป็นความสัมพันธ์ที่มีอัตราการเปลี่ยนแปลงคงที่และแสดงด้วยเส้นในระนาบ ฟังก์ชันเชิงเส้นเช่น $latex f(x) = 3x + 5$ สามารถถือเป็นสูตรเกิดซ้ำได้:

$ลาเท็กซ์ a_0 = 5$

$ลาเท็กซ์ a_n = a_{n-1} + 3$

แม้ว่าวิธีคิดที่ชัดเจนกว่าเกี่ยวกับ $latex f(2)$ อาจเป็นได้ว่า $latex f(2) = 3 คูณ 2 + 5 = 11$ แต่อีกวิธีหนึ่งก็คือ $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. การสร้างแบบจำลองลักษณะพื้นฐานของฟังก์ชันเชิงเส้นแบบวนซ้ำ — อัตราการเปลี่ยนแปลงคงที่ — ทำให้เรามีวิธีคิดเกี่ยวกับความสัมพันธ์นี้อีกวิธีหนึ่ง เช่นเดียวกันสามารถทำได้กับฟังก์ชันเอ็กซ์โปเนนเชียลที่มีลักษณะเฉพาะด้วยการเปลี่ยนแปลงการคูณคงที่

การคิดแบบวนซ้ำยังทำงานนอกเหนือจากลำดับของตัวเลขอีกด้วย หากคุณเคยแก้ระบบสมการ คุณอาจใช้วิธีเรียกซ้ำ เพื่อแก้ปัญหาระบบ

$ลาเท็กซ์ 2x + y = 10$

$ลาเท็กซ์ 3x – y = 5$

ก่อนอื่นคุณสามารถเพิ่มสมการทั้งสองเข้าด้วยกันเพื่อกำจัด y ตัวแปร ซึ่งให้ผลลัพธ์เป็นสมการ $latex 5x = 15$ แก้สมการนี้เพื่อให้ได้ $latex x =$ 3 แทนการหา $latex y = 4$ เท่านี้ก็เสร็จเรียบร้อย แนวทางนี้ใช้อัลกอริธึมแบบเรียกซ้ำ โดยที่โซลูชันของระบบถูกสร้างขึ้นจากโซลูชันไปยังระบบที่เล็กกว่าและเกี่ยวข้องกัน ตัวอย่างเช่น ในการแก้ระบบ 3 × 3 คุณต้องกำจัดตัวแปรหนึ่งตัวเพื่อเปลี่ยนให้เป็นระบบ 2 × 2 และอีกครั้งเพื่อเปลี่ยนให้เป็นระบบ 1 × 1 สมการเดี่ยวที่แก้ง่ายนี้เหมือนกับค่าเริ่มต้นของกระบวนการเกิดซ้ำนี้ มันส่งสัญญาณถึงจุดสิ้นสุดของการย้อนรอย และจากนั้นคุณก็ดำเนินการสำรองห่วงโซ่สมการ เช่นเดียวกับในลำดับแบบเรียกซ้ำ

มีแม้กระทั่งเทคนิคการพิสูจน์แบบเรียกซ้ำ ตัวอย่างเช่น สูตรที่มีชื่อเสียงในเรขาคณิตคือสูตรผลรวมมุมรูปหลายเหลี่ยม ซึ่งบอกว่าผลรวมของการวัดมุมภายในของ nรูปหลายเหลี่ยมด้านคือ $latex (n-2) คูณ 180^{circ}$ วิธีหนึ่งในการพิสูจน์ผลลัพธ์นี้คือการเริ่มต้นด้วย n-ลองจินตนาการดูว่าจะเกิดอะไรขึ้นถ้าคุณเอาสามเหลี่ยมออก

การเอารูปสามเหลี่ยมออกจะเป็นการ n-gon เข้าสู่ (n − 1)-gon และยังลบการวัดมุมภายใน 180 องศาอีกด้วย นี่คือความสัมพันธ์แบบเรียกซ้ำ: ผลรวมของมุมภายในสำหรับ n-gon มากกว่าผลบวกของมุมภายใน 180 องศาสำหรับ (n − 1)-กอน หากต้องการสร้างผลลัพธ์ทั่วไป ให้ลบรูปสามเหลี่ยมออกเรื่อยๆ จนกว่าจะถึงค่าเริ่มต้น ซึ่งในสถานการณ์นี้จะเกิดขึ้นเมื่อคุณลบรูปสามเหลี่ยมทั้งหมดยกเว้นสามรูป n-จุดยอดของกอน ณ จุดนี้ รูปหลายเหลี่ยมเริ่มต้นถูกย่อให้เป็นรูปสามเหลี่ยม ซึ่งผลรวมของมุมภายในทราบว่าเป็น 180 องศา ตอนนี้หาทางกลับขึ้นมา โดยบวก 180 องศาในแต่ละขั้นตอน แล้วคุณจะได้สูตร

เมื่อกลับมาที่งานปาร์ตี้ของเรา ปัญหาการจับมือแสดงให้เราเห็นว่าอะไรเป็นไปได้เมื่อเราคิดอย่างสร้างสรรค์ จากนั้นจึงเชื่อมโยงมุมมองต่างๆ ของปัญหาเข้าด้วยกัน หากเราเล่นกับโมเดลแบบเรียกซ้ำสำหรับลำดับการจับมือของเรา:

$ลาเท็กซ์ a_1 = 0$

$ลาเท็กซ์ a_n = a_{n-1} + n – 1$

มีรูปแบบที่สวยงามเกิดขึ้น:

$ลาเท็กซ์ a_2 = a_1 + 1 = 0 + 1$

$ลาเท็กซ์ a_3 = a_2 + 2 = 0 + 1 + 2$

$ลาเท็กซ์ a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$ลาเท็กซ์ cdots$

$ลาเท็กซ์ a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

ตอนนี้เรามีวิธีคิดทั่วไปเกี่ยวกับปัญหาแบบใหม่: จำนวนการจับมือกันใน n-บุคคลฝ่ายเท่ากับผลรวมของฝ่ายแรก n − 1 จำนวนเต็มบวก

คิดย้อนกลับไปสู่แนวทางเดิมของเรา ใน n-บุคคลปาร์ตี้ แต่ละคนจะจับมือกัน n − 1 คน ผลิตภัณฑ์ $latex n (n-1)$ นับทุกการจับมือกันสองครั้ง ดังนั้นจำนวนการจับมือทั้งหมดคือ $latex frac{n(n-1)}{2}$ แต่เนื่องจากวิธีการที่แตกต่างกันของเรานับสิ่งเดียวกัน พวกเขาจึงต้องให้ผลลัพธ์ที่เหมือนกัน โดยเฉพาะอย่างยิ่ง นี่หมายถึง:

$ลาเท็กซ์ 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

ด้วยการเชื่อมโยงแนวทางต่างๆ เข้ากับปัญหาการจับมือ เราจะได้สูตรปิดสำหรับผลรวมของวิธีแรก n − 1 จำนวนเต็มบวก แต่เราได้รับมากกว่านั้น: นิพจน์ $latex frac{n(n-1)}{2}$ เกี่ยวข้องกับเศษส่วน แต่เนื่องจากมันเท่ากับผลรวมของจำนวนเต็ม มันจึงต้องเป็นจำนวนเต็มด้วย นี่เป็นการพิสูจน์ข้อเท็จจริงง่ายๆ ของทฤษฎีจำนวน: สำหรับจำนวนเต็มทุกจำนวน n, $latex frac{n(n-1)}{2}$ เป็นจำนวนเต็ม

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

การออกกำลังกาย

1. ค้นหาสูตรปิดสำหรับลำดับที่กำหนดแบบเรียกซ้ำเป็น
$ลาเท็กซ์ a_1 = 1$
$ลาเท็กซ์ a_n = a_{n-1} + 2n – 1$

2. ที่ส่วนท้ายของคอลัมน์ นิพจน์ $latex frac{n(n-1)}{2}$ ถูกแสดงเป็นจำนวนเต็ม แม้ว่านิพจน์นั้นจะเกี่ยวข้องกับเศษส่วนก็ตาม เพราะ $latex frac{n(n-1 )}{2}$ คือผลลัพธ์ของการนับบางสิ่ง นอกจากนี้ยังมีข้อโต้แย้งทางทฤษฎีจำนวนที่แสดงว่านิพจน์นี้ต้องเป็นจำนวนเต็ม มันคืออะไร?

3. ค้นหาคำศัพท์สองสามคำแรกของลำดับการเรียกซ้ำ
$ลาเท็กซ์ a_1 = 1$
$ลาเท็กซ์ a_n = frac{1}{1+a_{n-1}}$

4. ค้นหาคำศัพท์สองสามคำแรกของลำดับการเรียกซ้ำ
$ลาเท็กซ์ a_1 = 1$
$ลาเท็กซ์ a_2 = 1$
$ลาเท็กซ์ a_n = a_{n-1} – a_{n-2}$