Post your proofs: Given five points on a sphere, four of them lie on a closed hemisphere. | Hacker News Reader

Post your proofs: Given five points on a sphere, four of them lie on a closed hemisphere.

This question comes from the Putnam math exam I took as an undergrad as part of our college team. Just to give you a sense of what taking the exam is like, it has ten questions worth ten points each with the median exam taker scoring 0 or 1 point depending on the year. This was my favorite question from the first exam I took (partly because it was one of the few I felt like actually had a shot at getting right).

View on HN

Answer ROT13ed, see http://www.rot13.com/ to translate:

Gnxr nal gjb bs gur svir cbvagf, naq pnyy gurz N naq O. Pnyy gur bgure guerr cbvagf P, Q, naq R.

Abj pbafgehpg n cynar K cnffvat guebhtu N, O, naq gur pragre bs gur fcurer (vs N naq O ner rdhny, gurer ner vasvavgryl znal fhpu cynarf; bgurejvfr gurer vf cerpvfryl bar). Gur cynar K qvivqrf gur fcurer F vagb gjb bcra urzvfcurerf F_1 naq F_2, naq gur pvepyr F_3 juvpu vf gur vagrefrpgvba bs F naq K. Abgr gung F_3 pbagnvaf obgu N naq O.

Abj qrsvar G_1 = F_1 H F_3 naq G_2 = F_2 H F_3; ol vafcrpgvba, gurfr ner obgu pybfrq urzvfcurerf. Fvapr F_3 pbagnvaf obgu N naq O, G_1 naq G_2 obgu pbagnva obgu N naq O. Shegurezber, G_1 H G_2 = F_1 H F_2 H F_3 = F, naq gurersber gur cbvagf P, Q, naq R rnpu yvr ba bar be zber bs G_1 naq G_2.

Ol gur cvtrbaubyr cevapvcyr, ng yrnfg bar bs G_1 naq G_2 pbagnvaf ng yrnfg gjb bhg bs gur guerr cbvagf P, Q, naq R. Pnyy guvf bar G. Fvapr jr nyernql xabj gung G pbagnvaf obgu N naq O, jr pbapyhqr gung G vf n pybfrq urzvfcurer pbagnvavat ng yrnfg sbhe bhg bs gur svir cbvagf N, O, P, Q, naq R.

Qbrf guvf cebbs nyfb jbex gb fubj gung nal A-1 bs A cbvagf qenja ba n fcurer jvyy funer n urzvfcurer?

Ab, sbe 6 cbvagf guvf cebbs jbhyq fgvyy bayl cebir 4 bs gurz gb or va gur fnzr urzvfcurer.

The leet key Firefox extension is fun.

Ab, vg cebirf gung bhg bs 2A-1 cbvagf ba n fcurer, A+2 jvyy funer n urzvfcurer.

Oh right, I'm an idiot.

Ab ohg vg pna or hfrq gb cebir gung sbe sbhe cbvagf ba n pvepyr, guerr bs gurfr cbvagf zhfg or va gur fnzr frzvpvepyr.

Zl uhapu vf gung sbe rnpu qvzrafvba lbh nqq, lbh pna vapernfr a ol bar, gung vf gb fnl lbh pbhyq unir 6 cbvagf va gur 4 qvzrafvba. Guvf vf onfrq ba gur vqrn gung vg gnxrf a cbvagf gb znxr na a qvzrafvbany cynar, fb lbh pna cynpr 4 cbvagf va gur pragre sbe gur frzvsvther va gur 4gu qvzrafvba.

Gura vg vf snveyl fvzcyr gb ernyvfr gung cynpvat 2a+1 vgrzf vagb 2 tebhcf zrnaf gung ng yrnfg bar tebhc zhfg unir ng yrnfg a+1 vgrzf.

Gb hfr guvf onfvf sbe gur agu qvzrafvba, lbh zhfg erzbir a cbvagf yrnivat bayl 3 cbvagf. Vs nalobql pna znxr n cebbs guvf gubhtu V jbhyq ybir gb frr vg.

Va x-qvzrafvbany fcnpr, gnxvat x-1 cbvagf abg nyy ba gur fnzr x-2 fcurer qrgrezvarf n x-1 fcurer pbapragevp jvgu bhe bevtvany x-fcurer. Fhpu n x-1 fcurer qvivqrf bhe bevtvany x-fcurer vagb gjb x-urzvfcurerf (vs lbh qba'g oryvrir guvf, fvzcyl er-bevrag lbhe onfvf fb gung bar qverpgvba vf begubtbany gb gur x-1 fcurer; gur gjb x urzvfcurerf ner gura gur cbvagf ba gur x-fcurer jurer guvf pbbeqvangr vf abaartngvir, naq gur cbvagf ba gur x-fcurer jurer guvf pbbeqvangr vf abacbfvgvir. Ohg gura vs jr jnag y cbvagf va bhe x-urzvfcurer, jr pna thnenagrr gurve cerfrapr vs jr unir 2(y-(x-1)-1 = 2y-2x+1 cbvagf yrsg. Ohg guvf vf gur fnzr nf fgnegvat jvgu 2y-x cbvagf ba gur fhesnpr bs gur fcurer va x-qvzrafvbany fcnpr, fb gung vf gur zvavzhz ahzore jr arrq gb thnenagrr (hfvat guvf nethzrag) y bs gurz ba n pybfrq x-qvzrafvbany urzvfcurer. Abgr gung guvf erfhyg zngpurf gung bs gur 3-qvzrafvbany pnfr.

Gur vagrerfgvat cneg bs guvf erfhyg vf abg qverpgyl jung vg fnlf, ohg jung vg fnlf nobhg fcnprf jr pna rzorq va gur fhesnpr bs n x-qvzrafvbany fcurer...gung 2y-x cbvagf va fhpu n fcnpr ner pbirerq ol gur cer-vzntr (haqre gur rzorqqvat) bs n urzvfcurer--sbe rzorqqvatf jvgu avpr-ybbxvat cer-vzntrf bs urzvfcurerf, guvf pbhyq pbaprvinoyl npghnyyl or n hfrshy erfhyg.

Edit: Vs lbh pna'g pubbfr fhpu n frg bs x-1 cbvagf, gura nyy lbhe cbvagf snyy ba gur fnzr x-2 fcurer, juvpu pna or rkgraqrq gb n x-1 fcurer gung vf hfrq nf n obhaqnel orgjrra gjb x-urzvfcurerf; nyy lbhe cbvagf ner ba gur obhaqnel bs obgu.

You guys keep going like this and I'm going to be able to read rot13 without needing the translator...

rot13.com also:

Cvpx nal gjb bs gur cbvagf naq pbafgehpg gur terng pvepyr gung pbagnvaf gurz. Guvf terng pvepyr qvivqrf gur fcurer vagb gjb urzvfcurerf, yrg'f pnyy gurz N naq O.

Jurer (n,o) vf gur ahzore bs gubfr bgure cbvagf ylvat va gur erfcrpgvir urzvfcurerf, (n,o) zhfg or bar bs: (0,3), (1,2), (2,1), be (3,0).

Nqqvat gur 2 cbvagf gung yvr ba gur terng pvepyr (naq gurersber va N naq O), gur ahzore bs gbgny cbvagf va gur erfcrpgvir urzvfcurerf zhfg or: (2,5), (3,4), (4,3) be (5,2). Nyy bs gurfr srngher bar pybfrq urzvfcurer pbagnvavat 4 be zber bs gur cbvagf.

(Arrqf gb or nppbzcnavrq jvgu fvzvyne cebbsf, be trarenyvfrq gb nppbhag sbe, fpranevbf jurer 3, 4 be 5 bs gur bevtvany cbvagf yvr ba gur fnzr terng pvepyr).

My attempt was similar, but I didn't zragvba gur rqtr pnfrf so I may not have received full credit from the grader (they don't tell you which question your points come from).

I don't have the math chops to prove it, but there is an intuitive answer:

The farthest any two points can be is on a line passing through the center of the sphere. There are three such point-pairs for the x,y, and z axes. Given at least 5 points, four must lie on the same plane. That plane defines the border between hemispheres. Voila.

Three non-collinear points determine a plane.

A counterexample to your proof would be to draw a plane through three points, say near the top of the sphere, then distribute the remaining points on the bottom. Then you don't get a proper division by taking your plane as the dividing line, since a working version would require more than a hemisphere of volume.

Thinking in terms of x, y, and z axes is a red herring. The symmetry of the sphere makes them irrelevant.

12 questions, not 10, and this one seems relatively easy; I immediately saw the construction for andrewf's answer, which is actually the same as cperciva's answer because gur cynar cnffvat guebhtu gjb cbvagf naq gur pragre bs gur fcurer zrrgf gur fcurer ng gur terng pvepyr bs naqerjs'f pbafgehpgvba.

rot13

Gnxr n cynar guebhtu gjb bs gur svir cbvagf ba gur fcurer naq gur pragre bs gur fcurer. Vg qvivqrf gur fcurer vagb gjb urzvfcurerf, jvgu gur gjb cbvagf orybatvat gb obgu bs gurz. Gurer ner guerr erznvavat cbvagf, naq gjb urzvfcurerf, fb va bar bs gur urzvfcurerf gurer zhfg or ng yrfg gjb bs gur guerr erznvavat cbvagf (cvtrbaubyr cevapvcyr). Gung fcurer pbagnvaf sbhe cbvagf.

I doubt I could do a proper rigorous proof, but pigeonhole principle comes to mind.

Reply on news.ycombinator.com