|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
|||
|
|||
ขอเเนวทางการพิสูจน์หน่อยครับ
ขอเเนวทางการพิสูจน์เเบบอุปนัยเชิงคณิตศาสตร์หน่อยครับ
ปล. ผมสมมติ ให้ m=6 จะได้ n_1=4 , m=8 จะได้n_1=7 ตรงขั้นตอนเเสดงว่า P(n_1,6) เป็นจริง เเล้วมาติดตรง P(n_1,k)->P(n_1,k+1) เป็นจริง ยังไปต่อไม่ถูกครับ ขอคำเเนะนำด้วยครับ ขอบคุณครับ |
#2
|
|||
|
|||
รบกวนขอ Hint หน่อยครับ ผมติดมาหลายวันเเล้วครับ .:T_T:.
|
#3
|
|||
|
|||
โจทย์มันอยากได้ความสัมพันธ์ของ "ค่าเลขชี้กำลังสูงสุด" (ที่เจอใน $m!$)
กับ "จำนวน $m$" จริงป่าวครับ เพราะฉะนั้นพยายามหาเครื่องมือมา "เปรียบเทียบ" ค่าของเลขชี้กำลังสูงสุดกับค่าของ value $m$ พิสูจน์ให้ได้ก่อนว่าค่ามากที่สุดของเลขชี้กำลัง มันจะเจอใน $p_{1}=2$ ครับ แล้วใช้เครื่องมือบางอย่าง "โยง" ข้อมูลของ $n_{1}$ (ในตำแหน่ง $p=2$) เข้าไปเปรียบเทียบกับค่าของ $m$ ครับ หรือง่ายๆคือ สร้างความสัมพันธ์ของเลขชี้กำลัง $n_{1}-1$ กับ $m$ ให้เปรียบเทียบค่ากันให้ได้ ผมทดจนสุดๆดูแล้วมันไม่ได้ใช้อุปนัยเชิงคณิตศาสตร์ได้ตรงๆครับ ต้องทอนโจทย์ลงมาก่อน ถ้าไม่ได้จริงๆ แล้ววิธีผมไม่มีปัญหาเดี๋ยวมาพิมพ์ไว้ให้ทีหลังครับ สู้ๆนะครับ ปล. ปัญหาข้อนี้จริงๆมันอยู่ที่ ความลำบากในการเปรียบเทียบปริมาณครับ เลือกเครื่องมือดีๆครับ |
#4
|
|||
|
|||
อ้างอิง:
ขอบคุณมากครับผม. อยากเห็นวิธีคิดสักหน่อยครับ. ^^ |
#5
|
|||
|
|||
ทำไปถึงตรงไหนแล้วครับ ? อยากให้ลอง crack ให้ได้เองก่อนอะครับ
ผมว่ามันเป็นโจทย์ที่ดีมากข้อนึงนะครับ หรือผมหลงไปเองว่าวิธีผมมันถูก |
#6
|
|||
|
|||
ผมทวน proof ของตัวเองดูแล้วระบบ induction ของผมยังไม่ cover โดเมนครับ
ไอเดียที่ผมทดไว้คือสร้างเครื่องมือโยงค่า max บนเลขชี้กำลัง ในที่นี้คือ $n_{1}$ ในตำแหน่งที่ $p=2$ (ใช้เลอจองด์พิสูจน์ออกมาว่า max ที่ 2) จากนั้นก็ใช้ข้อเท็จจริงที่ว่า $n_{1}=\frac{m-\sum a_{i}}{p_{1}-1}$ $0 \leq i \leq k$ (เลอจองด์อีกฟอร์ม) แต่ prove ไปแล้วว่า max $p$ มันเกิดที่ $p_{1}=2$ เลยได้ว่าต้อง prove $2^{m-\sum a_{i}-1} > m$ โดยที่ $m=a_{k}2^{k}+a_{k-1}2^{k-1}+...+a_{1}2+a_{0}$ เป็น base 2 representation ของ $m$ เพราะงั้น $a_{i}$ เป็นได้แค่ $0,1$ จากนั้นใช้ความรู้อสมการมาหยิบขอบของค่า $\sum a_{i}$ ที่เป็นไปได้ เอาเข้าไปเปรียบเทียบกับค่าของ $m-1$ บนเลขชี้กำลังครับ แต่เวลาเปรียบเทียบค่ามันเอาไปเทียบ $m$ ตรงๆลำบาก ผมเลยเลือกวิธีตัดเซทของ $m$ ออกเป็นช่วงๆ ด้วยค่าของจำนวนเป็นคู่ๆ (ที่เลือกมาให้เปรียบเทียบค่าของ $\sum a_{i}$ ได้ ) ก็เท่ากับว่าใช้จำนวนนั้นเป็นเส้นแบ่งโดนเมนของ $\mathbb{N}$ แล้วพิสูจน์ข้อความ for all ใช้ช่วงที่แบ่ง ตรงนั้นแหละที่ใช้ induction เล็กๆครับ จากนั้นใช้ผลของ subset ของ $\mathbb{N}$ ที่แบ่งไว้ มา union กันให้ cover $\mathbb{N}$ ตามที่โจทย์บอกคือ $m \geq 6$ ก็จบครับ แต่ขั้นสุดท้าย ผมมาเจอปัญหาซะก่อน ถ้าหากซีเรียสมาก ไว้มีเวลาเดี๋ยวผมมาจัดการให้ครับ ปล. ขั้นสุดท้ายคือ prove ให้คลุมโดเมนที่โจทย์อยากได้ ผมมีไอเดียเรื่อง Cauchy induction, Strong induction กับเหตุผลเรื่อง bijection ที่ส่งโดเมนที่แบ่งออกให้สมมูลกับระบบของ induction แต่ยังไม่หลุดครับ |
#7
|
|||
|
|||
อ้างอิง:
ต้องขอคำเเนะนำด้วยครับ. จะพยายามทำความเข้าใจครับ. |
#8
|
|||
|
|||
อ้างอิง:
อาจจะมีวิธีดีๆกว่านี้ก็ได้ครับ อีกอย่างวิธีของผมมันเป็น induction ย่อยๆอีกที ลองเปิดแหล่งโจทย์ดูครับ โจทย์ข้อนี้มาจากไหน อาจจะมีวิธีทีมองๆข้ามไปที่ง่ายกว่าก็ได้ครับ ปล. induction ไม่ได้มีแค่แบบเดียวครับ induction แบบแบ่งช่วงก็มีครับ ผมขอเบรคไว้ตรงนี้ก่อน ตอนนี้ติดภาระเกี่ยวพันครับ ลองดูข้างล่างครับ insight เรื่อง induction ดีๆ เพื่อได้ไอเดียอะไรใหม่ๆ http://math.stackexchange.com/questi...edirect=1&lq=1 |
#9
|
|||
|
|||
อ้างอิง:
ขอบคุณมากครับ. ผมจะพยายามศึกษาครับ ^^ |
#10
|
|||
|
|||
โดย Legendre's theorem, $ v_p(m!) = \lfloor\frac{m}{p}\rfloor + \lfloor\frac{m}{p^2}\rfloor + ... $ ดังนั้น $ v_2(m!) = \lfloor\frac{m}{2}\rfloor + \lfloor\frac{m}{4}\rfloor + ... $ จาก $ \lfloor\frac{m}{2^k}\rfloor \geq \lfloor\frac{m}{p^k}\rfloor , \forall k \in \unicode{8469} $ ทำให้ $ \lfloor\frac{m}{2}\rfloor + \lfloor\frac{m}{4}\rfloor + ... \geq \lfloor\frac{m}{p}\rfloor + \lfloor\frac{m}{p^2}\rfloor + ... \forall p \in \unicode{8473} $ จะได้ว่า $ p_1 = 2 $ และ $ n_1 = v_2(m!) = \lfloor\frac{m}{2}\rfloor + \lfloor\frac{m}{4}\rfloor + ... $ ดังนั้น $ 2^{n_1 - 1} = 2^{\lfloor\frac{m}{2}\rfloor + \lfloor\frac{m}{4}\rfloor + ...-1} $ ต่อไปจะแสดงว่า $ 2^{\lfloor\frac{m}{2}\rfloor + \lfloor\frac{m}{4}\rfloor + ...-1} > m$ โดย Strong induction บนตัวแปร $m$ ให้ P(m) แทนข้อความ $2^{\lfloor\frac{m}{2}\rfloor + \lfloor\frac{m}{4}\rfloor + ...-1} > m , \forall m \in \unicode{8469} \geq 6$ ขั้นฐาน : P(6), $2^{\lfloor\frac{6}{2}\rfloor + \lfloor\frac{6}{4}\rfloor + ...-1} > 6 $ เป็นจริง ขั้นอุปนัย : สมมุติว่า P(7), P(8), ..., P(m) เป็นจริง 1. กรณี $m$ เป็นเลขคี่ จะได้ว่า $\lfloor\frac{m+1}{2}\rfloor = \lfloor\frac{m}{2}\rfloor +1$ และจาก P(m) เป็นจริง, $2^{\lfloor\frac{m}{2}\rfloor + \lfloor\frac{m}{4}\rfloor + ...-1} > m$ ทำให้ $2^{\lfloor\frac{m+1}{2}\rfloor + \lfloor\frac{m+1}{4}\rfloor + ...-1} \geq 2\cdot 2^{\lfloor\frac{m}{2}\rfloor + \lfloor\frac{m}{4}\rfloor + ...-1} \geq 2m > m+1$ (จาก $m \geq 6$) ดังนั้น P(m+1) เป็นจริง 2. กรณี $m$ เป็นเลขคู่ จะได้ว่า $\lfloor\frac{m+1}{2}\rfloor = \lfloor\frac{m-1}{2}\rfloor +1$ และจาก P(m-1) เป็นจริง, $2^{\lfloor\frac{m-1}{2}\rfloor + \lfloor\frac{m-1}{4}\rfloor + ...-1} > m-1$ ทำให้ $2^{\lfloor\frac{m+1}{2}\rfloor + \lfloor\frac{m+1}{4}\rfloor + ...-1} \geq 2\cdot 2^{\lfloor\frac{m-1}{2}\rfloor + \lfloor\frac{m-1}{4}\rfloor + ...-1} \geq 2(m-1) > m+1 (จาก m \geq 6)$ ดังนั้น P(m+1) เป็นจริง จากทั้ง 2 กรณี, P(m+1) เป็นจริง ดังนั้น $2^{\lfloor\frac{m}{2}\rfloor + \lfloor\frac{m}{4}\rfloor + ...-1} > m$ นั่นคือ $2^{n_1 - 1} > m$ |
#11
|
|||
|
|||
อ้างอิง:
|
#12
|
|||
|
|||
อ้างอิง:
ขอบคุณครับผม ^^ |
#13
|
|||
|
|||
ไปคิดมาให้แล้วแบบจริงๆจังๆครับ ข้อนี้ไม่ยากเท่าไร อสมการ weak เลยทำได้หลายวิธี
ทดไว้ประมาณ 5-6 วิธีแต่เอาแค่ 4 ก่อน ผิดตรงไหนหรือมีวิธีแปลกๆก็รบกวนด้วยนะครับ เริ่มที่ Lemma ที่ผมใช้ไปก่อน Legendre's Lemma ให้ $p \in \mathbb{P}$ และ $m \in \mathbb{N}$ จะได้ว่าจำนวนเต็มบวก $e$ ที่ใหญ่สุดที่ทำให้ $p^e$ fully divide $m!$ คือ $e=v_{p}(m!)=\sum_{i = 1}^{\infty} \left\lfloor\,\frac{m}{p^i}\right\rfloor$ Lemma 1 จาก Lemma บนจะได้ว่า ถ้า $\sum_{i = 1}^{\infty} \left\lfloor\,\frac{m}{p^i}\right\rfloor =\sum_{i = 1}^{j} \left\lfloor\,\frac{m}{p^i}\right\rfloor$ แล้ว $j=\left\lfloor\,\log_p{m}\right\rfloor$ สมมติให้ $j$ เป็นจำนวนเต็มบวกใหญ่สุดที่ทำให้ $\left\lfloor\,\frac{m}{p^j}\right\rfloor$ ไม่เป็น $0$ และ $\left\lfloor\,\frac{m}{p^{j+1}}\right\rfloor=0$ ทุกค่าเลขชี้กำลังที่ใหญ่กว่า และจากการที่ $ \left\lfloor\,x\right\rfloor \leq x \leq \left\lfloor\,x\right\rfloor +1 $ ใช้อสมการมาวิเคราะห์ข้างในจะพิสูจน์ได้ว่า $\left\lfloor\,\log_p{m}\right\rfloor -1 \leq \log_p{m} -1 < j < \log_p{m} < \left\lfloor\,\log_p{m}\right\rfloor +1$ จากอสมการคู่ซ้ายและขวาสุด ต้องบีบได้เป็น $j=\left\lfloor\,\log_p{m}\right\rfloor$ Lemma 2 $v_{p}(m!)=u+ v_{p}(u!)$ โดยที่ $u= \left\lfloor\,\frac{m}{p}\right\rfloor$ สมมติให้ $u$ เป็นจำนวนเต็มบวกใหญ่ที่สุดที่ทำให้ $up \leq m$ แต่ $(u+1)p > m$ ให้ $m!=p^u u! u'$ โดยที่ $(p,u')=1$ จะได้ว่า $v_{p}(m!)=u+v_{p}(u!)$ แต่จากอสมการชุดบนทำให้ $u \leq \frac{m}{p} < u+1$ จะได้ว่า $\left\lfloor\,\frac{m}{p}\right\rfloor = u$ ------------------------------------------------------------------------ note ต่อจากนี้ ให้ระวังแต่ละวิธีด้วย ว่าบทพิสูจน์นั้นๆ cover ตั้งแต่ $m$ เป็นเท่าไร อันนี้เขียนให้เหตุผลแยกเอาได้ครับ ผมขี้เกียจเพราะมันเยอะ ที่ทดไว้มันไม่ได้เริ่มที่ $m \geq 6$ แต่มันสามารถแยกเชคได้ง่ายๆครับ เริ่มเลย ต้องพิสูจน์ก่อนว่าค่า $n_{i}$ ใหญ่สุดที่ดึงเอาจาก $m!$ คือเกิดขึ้นที่ $p=2$ ตามความเห็นบน ต่อจากนี้ก็แล้วแต่คน จะทำได้หลายๆวิธี ----------------------------------------------------------------------- วิธีที่ 1 พิสูจน์โดยอุปนัยเชิงคณิตศาสตร์ได้ไม่ยากว่า ถ้า $n \geq 3$ แล้ว $2^n \geq 2n+2$ เป็นการเพียงพอที่จะพิสูจน์ว่า $2^{n_{1}-1} \geq 2(n_{1}-1)+2 \geq m+1$ หรือ $2n_{1} \geq m+1$ จาก Lemma และที่พิสูจน์ไปแล้ว จะได้ว่า $n_{1}=\left\lfloor\,\frac{m}{2}\right\rfloor + v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor !)$ ดังนั้นต้องพิสูจน์ว่า $2n_{1}=2\left\lfloor\,\frac{m}{2}\right\rfloor +2v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!) \geq m+1$ จากอสมการ $\left\lfloor\,x\right\rfloor \leq x < \left\lfloor\,x \right\rfloor +1 $ และจากการที่ $ v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!) \geq v_{2}(\left\lfloor\,\frac{6}{2}\right\rfloor!) = v_{2}(3!)=1$ จะได้ว่า $2\left\lfloor\,\frac{m}{2}\right\rfloor +2v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!) > 2(\frac{m}{2}-1)+2\cdot 1 \geq m+1 > m$ ตามต้องการ ---------------------------------------------------------------------------------- วิธีที่ 2 จะพิสูจน์อสมการที่แข็งกว่าวิธีที่ 1 ดังนี้ $2^n \geq n^2 \geq 2n+2 \geq m+1$ จริงเมื่อ $n \geq ... m \geq ...$ (อันนี้ define ได้) ...เวลาจะเขียนอีก 1 solution... พิสูจน์โดยไม่ยากว่า $2^n \geq n^2$ ดังนั้นเป็นการเพียงพอจะ prove $2^{n_{1}-1} \geq (n_{1}-1)^2 \geq 2n_{1} \geq m+1$ (เลือกเอา $(n_{1}-1)^2 \geq m+1$ ไปใช้เลย) กระจายแล้วจัดรูปจะได้ว่า $n_{1} \geq 1+\log \sqrt{m+1}$ หรือ $10^{\left\lfloor\,\frac{m}{2}\right\rfloor +2v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!)-1} \geq \log \sqrt{m+1}$ แต่จาก AM-GM จะได้ $\log \sqrt{m+1} < 1+\frac{m}{2}$ และจาก Bernoulli's จะได้ $(1+9)^{\left\lfloor\,\frac{m}{2}\right\rfloor +v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!)-1} \geq 1+9(\left\lfloor\,\frac{m}{2}\right\rfloor +v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!)-1)$ ดังนั้นเหลือแค่โชว์ $9\left\lfloor\,\frac{m}{2}\right\rfloor +9v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!) > 9 +\frac{m}{2} = 9+\left\lfloor\,\frac{m}{2}\right\rfloor +f(\frac{m}{2})$ โดยที่ $f(x)$ คือเลขทศนิยมของ $x$ อสมการบนสุดจริงชัดเจนเพราะ $f(\frac{m}{2}) < 1$ ----------------------------------------------------------------------------------- วิธีที่ 3 จากวิธีอื่นๆ $2^{n_{1}-1} \geq 2n_{1} \geq m+1$ จะ bound ค่าของ $m+1$ กับ $2n_{1}$ มาชนกัน โดยใช้ $\left\lfloor\,x \right\rfloor +\left\lfloor\,y \right\rfloor \leq \left\lfloor\, x+y \right\rfloor \leq \left\lfloor\, x+y \right\rfloor +1 $ $m+1=\frac{m-1}{2}+\frac{m+3}{2} < \left\lfloor\, \frac{m-1}{2}+\frac{m+3}{2} \right\rfloor +1 \leq \left\lfloor\,\frac{m-1}{2}\right\rfloor +\left\lfloor\,\frac{m+3}{2}\right\rfloor +2 = \left\lfloor\,\frac{m-1}{2}\right\rfloor +\left\lfloor\,\frac{m+1}{2}\right\rfloor +3$ อีกข้างก็ทำคล้ายๆกัน $2n_{1}=2\left\lfloor\,\frac{m}{2} \right\rfloor + v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!) \geq 2\left\lfloor\,\frac{m+1}{2}\right\rfloor + 2\left\lfloor\, \frac{m-1}{2}\right\rfloor + v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!) \geq \left\lfloor\,\frac{m+1}{2}\right\rfloor + \left\lfloor\, \frac{m-1}{2}\right\rfloor +3$ ดูอสมการสุดท้าย $\left\lfloor\,\frac{m+1}{2}\right\rfloor + \left\lfloor\, \frac{m-1}{2}\right\rfloor + v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!) \geq 3$ ซึ่งก็ได้ว่าจริง ---------------------------------------------------------------------------------- วิธีที่ 4 ให้ $y=2^x$ พิสูจน์ได้ไม่ยากว่า $f(\frac{x+y}{2}) \geq \frac{f(x)+f(y)}{2}$ เลือกให้ $x=2\left\lfloor\, \frac{m}{2} \right\rfloor -1$ และ $y=2v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!) -1$ จะได้ $2^{n_{1}-1}=2^{\frac{x+y}{2}} \geq 2^{2\left\lfloor\, \frac{m}{2} \right\rfloor -2}+2^{2v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!)-2}$ ใช้ Bernoulli's เทอมขวาล่าสุดจะได้ว่าต้องพิสูจน์ $2\left\lfloor\,\frac{m}{2}\right\rfloor +2v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!) \geq m+3$ ซึ่งจริงจาก $\left\lfloor\,\frac{m}{2}\right\rfloor \geq \frac{m}{2}-\frac{1}{2}$ และ $v_{2}(\left\lfloor\,\frac{m}{2}\right\rfloor!) \geq 2$ อสมการแรกเขียนใหม่ได้เป็น $f(\frac{m}{2}) \leq \frac{1}{2}$ ซึ่งก็จริงนั่นแหละ ปล.วิธีที่ 5 มันซับซ้อนขึ้นไปอีกหน่อย ใช้แบ่ง set แบบ $2^k+r$ กับ Lemma 1 เดี๋ยวมาโชว์ให้ดูทีหลังครับ เหนื่อย |
#14
|
|||
|
|||
สมาคมคณิตศาสตร์อเมริกา เฉลยสูครจำนวนเฉพาะ แล้วครับ ไม่ต้องรันคอมพิวเตอร์หาจำนวนเฉพาะ ก็ได้ !!!
|
#15
|
|||
|
|||
น่ากลัวอยู่ ถ้าวิชา และ ตำราที่เกี่ยวกับ Number Theory ในโลกนี้จะหายไป ...
คงเหลือแต่ Data Set Disk ขายกัน เหมือนๆ แบบบ้าน ร้านค้า แบบโรงงาน |
|
|