Not really hard questions from Germany: Part1

[nongtum]

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

1. The integers a have the properties, that 3a can be expressed in the form \(x^2+2y^2\) with integers x,y.
Show that a can also expressed in this form.
(Aufgabe 2., Bundeswettbewerb 2005 Runde 1.)

2. The lengths a,b,c of a triangle are integers. One of the height of this triangle is the sum of its rest two heights.
Show that \(a^2+b^2+c^2\) is a square.
(Aufgabe 2., Bundeswettbewerb 2004 Runde 1.)

And the last question this round...

3. ธนาคารสำหรับนักคณิตศาสตร์แห่งหนึ่งออกเลขบัญชีให้ลูกค้าเป็นเลขสิบหลัก ลูกค้าส่วนมากมีความเห็นพ้องและต้องการตรงกันว่าอยากให้เลขบัญชีแต่ละหลักเป็นจำนวนเฉพาะ จากนั้นธนาคารจึงดำเนินการออกเลขบัญชี และยังทราบอีกว่านักคณิตศาสตร์ใจลอยเป็นบางครั้งบางคราวและสับสนกับตัวเลข ดังนั้นเลขบัญชีสองบัญชีใดจึงควรต่างกันอย่างน้อยห้าหลัก
จงแสดงว่า ธนาคารออกบัญชีดังกล่าวได้อย่างมากที่สุด 2404 บัญชี
(Aufgabeblatt 41, 3.Aufgabe, Mathematischer Korrespondenzzirkel Göttingen)

ไว้ว่างๆจะมาโพสต์โจทย์เพิ่ม และคำตอบครับ

[gools]

ข้อ 1 ก่อนนะครับ

คลิกที่นี่เพื่อดูข้อความที่ซ่อนไว้

ให้ x² บ n mod 3 จะได้ว่า 2y² บ -n mod 3
เนื่องจาก x² บ 0,1 mod 3 และ 2y² บ 0,2 mod 3 จะได้ว่า n=0
ให้ 3p=x และ 3q=y จะได้ว่า a=3p²+6q²=(3p²+4q²)+2q²
ให้ p=2q จะได้ว่า a=16q²+2q²=(4q)²+2q²
ทำให้ได้ว่า a สามารถเขียนให้อยู่ในรูป a=m²+2n² ได้

[passer-by]

สำหรับข้อ 2. ครับ
กำหนดให้ a,b,c เป็นด้านตรงข้ามมุม A,B,C ของสามเหลี่ยม และ h_a, h_bและ h_c เป็นส่วนสูงที่ลากมาตั้งฉากกับ a,b,c ตามลำดับ
ถ้า h_a =h_b +h_c ตามที่โจทย์บอก
และเพราะ sin(B)=\(\huge\frac{h_{a}}{c}=\frac{h_{c}}{a} \) ,sin(C)=\(\huge\frac{h_{a}}{b}=\frac{h_{b}}{a} \)
ดังนั้น sin(B)+sin(C)= \(\large h_{a}(\frac{1}{b}+\frac{1}{c}) \)=\( \huge \frac{h_{b}+h_{c}}{a} \)
แต่ h_a =h_b +h_c เมื่อแทนค่าในสมการบรรทัดก่อน และจัดรูปใหม่ จะได้ a= \(\large \frac{bc}{b+c} \)
เพราะฉะนั้น a²+b²+c²=\(\large \frac{b^{2}c^{2}}{(b+c)^{2}} +b^{2}+c^{2} =\frac{(b^{2}+bc+c^{2})^{2}}{(b+c)^{2}}=(b+c-a)^{2}\)

[nongtum]

น้อง gools ครับ พี่ว่าน้องลืมคิดกรณี \(x\equiv1\ mod\ 3\), \(y\equiv-1\ mod\ 3\) หรือกลับกัน (เพราะ \(2\equiv-1\) ใน congruence modulo 3) แต่หลังจากนั้นก็อย่างที่น้องทำมาแหละครับ

another solution

ข้อนี้อาจทำได้อีกแบบ โดยเริ่มจาก \(3(a-y^2)=x^2-y^2=(x-y)(x+y)\) แล้วคิดในทำนองเดียวกับที่น้องคิดแหละครับ

[nooonuii]

ข้อ 2. ครับ

สมมติว่า \( \Large{ h_a,h_b,h_c } \) เป็นส่วนสูงของสามเหลี่ยมที่ลากไปตั้งฉากด้าน a,b,c ตามลำดับ ดังนั้นโดยสูตรพื้นที่ของสามเหลี่ยมจะได้ว่า
\[ \Large{ ah_a = bh_b = ch_c } \]
โดยไม่เสียนัยทั่วไปสมมติว่า \( \Large{ h_a = h_b + h_c } \)
ดังนั้นจะได้ความสัมพันธ์
\[ \Large{ 1 = \frac{a}{b} + \frac{a}{c} } \]
ซึ่งจะได้ว่า bc = ab + ac ดังนั้น
\[ \Large{ a^2 + b^2 + c^2 = (-a+b+c)^2 } \]


อ้าวมีคนตอบซะแหล่ว

[nongtum]

ข้อสองคิดแบบคุณ nooonuii ง่ายที่สุดครับ ข้อนี้อาจคิดโดยใช้ทฤษฎีบทของ Pythagoras ช่วยก็ได้ครับ แต่วิธีทำจะซับซ้อนยุ่งยากกว่านี้หน่อย

เอารางวัลไปอีกสามข้อละกันครับ

4. ให้ k เป็นจำนวนเต็มบวก จำนวนนับ a เรียกว่า k-typisch เมื่อตัวประกอบทุกตัวของ a หารด้วย k ได้เศษเป็น 1
จงแสดงว่า
a) เมื่อจำนวนตัวประกอบของจำนวนเต็มบวก n (รวม 1 และ n) k-typisch จะได้ว่า \(n=b^k\) เมื่อ b เป็นจำนวนเต็ม
b) บทกลับของ a) ไม่เป็นจริงเมื่อ k มากกว่า 2
(Aufgabe 2, Bundeswettbewerb 2004 Runde 2.)

5. Show that there are infinite different pairs (x,y) of positive rational numbers, for which \(\sqrt{x^2+y^3}\) and \(\sqrt{x^3+y^2}\) are rational.
(Aufgabe 4, Bundeswettbewerb 2004 Runde 2.)

6. ให้ n,n+1,...,n+5 เป็นจำนวนเต็มบวก จงแสดงว่ามีจำนวนเฉพาะที่เป็นตัวหารของเลขเพียงตัวเดียวจากเลขชุดนี้
(Aufgabe 1, Bundeswettbewerb 2003 Runde 1.)

[nooonuii]

[nongtum]

Upps! สงสัยโจทย์โหดเกินไป งั้นให้คำใบ้นิดหน่อยดีกว่า แล้วหากผ่านไปนานๆยังไม่มีใครคิดออก จะมา Post เฉลยครับ

คำใบ้ หากยังอยากลองทำเอง อย่าคลิก

3. เริ่มจาก เลขหกหลักแรกของสองบัญชีใดต้องไม่ตรงกัน ...
4. ให้ \(n=\prod_{i=1}^{k}p_i^{k_i}\) และ d(n) เป็นจำนวนตัวหารของ n แล้วหา d(n)
5. ให้ y=kx หรือ ยกตัวอย่างลำดับที่สอดคล้องเงื่อนไข
6. mod 5

เรามาทดสอบดูกันดีกว่า ว่าเข้าใจ Euklid's Algorithm กับ ห.ร.ม. กันดีแค่ไหนนะครับ สองข้อนี้เจอกับตัวตอนเข้ากลุ่มแบบฝึกหัด เห็นเฉลยตอนท้ายแทบบ้า (ทำไมตอนคิดเองคิดไม่ออก...)

7.1 เริ่มจาก (1,0) เราป้อนคู่อันดับนี้เข้ากล่องดำสามใบ(ไม่จำเป็นต้องตามลำดับ) โดยที่
Machine่ A: \((m,n)\mapsto(n,m)\)
Machine่ ฺB: \((m,n)\mapsto(m,m+n)\)
Machine่ ฺC: \((m,n)\mapsto(m,m-n)\)
เราสามารถสร้าง (13,39) และ (19,99) จากกล่องทั้งสามใบได้หรือไม่ เพราะเหตุใด
ใบ้: อย่าคิดลึกครับ

7.2 (ข้อนี้ที่จริงแค่คำนวณตรงๆ แต่เทคนิคในการคิดในบางขั้นตอนน่าสนใจ เลยเอาลองมาให้ทำดู)
Let \(a_n:=n^3+3\). True or false: \((a_n,a_{n+1})=1\).

[warut]

ข้อ 7.1 ให้สังเกตดังนี้ครับ

1. ไม่ว่าจะ process ด้วย machine ใด สิ่งหนึ่งที่ไม่เคยเปลี่ยนคือ ห.ร.ม. เพราะ
gcd(m, n) = gcd(n, m) = gcd(m, m + n) = gcd(m, m - n)
จากข้อสังเกตนี้อย่างเดียวเราก็สามารถสรุปได้แล้วว่า เราไม่สามารถสร้าง (13, 39) จาก (1, 0) ได้เพราะ
gcd(1, 0) = 1 น 13 = gcd(13, 39)


2. machine A เป็น inverse ของตัวมันเอง ส่วน machine B กับ C เป็น inverse ของกันและกัน
ดังนั้นถ้าเราสามารถสร้าง (a, b) จาก (c, d) ได้ เราก็จะสามารถสร้าง (c, d) จาก (a, b) ได้เช่นกัน

3. machine A กับ C สามารถใช้ในการคำนวณหา gcd(m, n) ได้ตามหลักของ Euclid's algorithm

จากข้อสังเกตทั้ง 3 เราจึงสรุปได้ว่าเราสามารถสร้าง (a, b) จาก (c, d) ได้ก็ต่อเมื่อ gcd(a, b) = gcd(c, d) เช่น ถ้าเราอยากรู้ว่าจะสร้าง (19, 99) จาก (1, 0) อย่างไร ก็เริ่มจากการคิดวิธีแปลง (19, 99) เป็น (1, 0) ด้วย machine A กับ C ตามหลักของ Euclid's algorithm ก่อน เสร็จแล้วก็คิดย้อนกลับครับ

คิดลึกไปไหมเนี่ย

[nongtum]

คำตอบข้อ 7.1 ของคุณ warut ถูกต้องครบถ้วนแล้วครับ (get กว่าตอนที่เขาเฉลยในห้องซะอีก ) คงไม่ต้องเพิ่มอะไรอีกแล้ว
ส่วนข้อ 7.2 หากว่างๆจะลองคิดก็ได้ครับ เพราะเทคนิคที่ว่าไม่ได้มีอะไรมากเลย

[warut]

แต่ผมเห็นที่ผิดของตัวเองแล้วล่ะ ข้อสังเกตที่ 2 และ 3 ของผมยังไม่ถูกต้องสมบูรณ์ครับ และการแปลงจริงๆก็ยุ่งยากกว่าที่คิดมาก เพราะไม่มี process ที่แปลง (m, n) เป็น (n, m - n) ได้โดยตรง เลยยังหาคำอธิบายที่ดีๆไม่ได้เลยครับ