Ponder This Challenge - November 2012 - Lattice of trees blocks light

Ponder This Challenge:

Thanks to Adir Pridor for the following challenge:

A gardener plants a tree on every integer lattice point, except the origin, inside a circle with a radius of 9801. The trees are cylindrical in shape and all grow together at the same rate.

As the trees grow, more and more points outside the circle of trees stop having a direct line of sight with the origin. What will be the trees' radius when the origin first loses its line of sight with all the points outside the circle? Please give your answer as a decimal number with an accuracy of 13 digits (13 significant digits).

Here is a sketch of a forest of radius 5 and a light beam entering the origin (center of the forest).

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  The problem was originally proposed almost a century ago (see Polya, G., "Zahlentheoretisches und wahrscheinlichkeitstheoretisches uber die sichtweite im walde," Arch. Math. Phys., 27 (1918): 135-142).

  The answer is 1/sqrt(d), where d is the smallest integer satisfying d=a^2+b^2, where a is co-prime to b, and d>=R^2.

  Clearly, d<=R^2+1 by choosing a=R and b=1; and d can be R^2 if and only if all the prime factors of R are 1 modulo 4.

  In our case, R=9801=3^4*11^2, so the critical radius is 1/sqrt(R^2+1) which is 0.000102030404529629...

Solvers

• Kevin Sham (11/01/2012 12:36 AM EDT)
• Anders Kaseorg (11/01/2012 03:15 AM EDT)
• Lu Wang (11/01/2012 07:12 AM EDT)
• Peter de Rivaz (11/01/2012 08:07 AM EDT)
• Jan Fricke (11/01/2012 10:44 AM EDT)
• Joseph DeVincentis (11/01/2012 11:59 AM EDT)
• Stéphane Higueret (11/01/2012 12:35 PM EDT)
• Deane Stewart & Deron Stewart (11/01/2012 03:09 PM EDT)
• Frederik Kaster (11/01/2012 03:13 PM EDT)
• Dan Dima (11/01/2012 03:30 PM EDT)
• David Dodson & Don Dodson (11/01/2012 05:53 PM EDT)
• Walter Schmidt (11/01/2012 06:38 PM EDT)
• Daniel Bitin (11/01/2012 07:41 PM EDT)
• Hari MP (11/02/2012 01:13 AM EDT)
• Rastko Anicic (11/02/2012 01:16 AM EDT)
• Chuck Carroll (11/02/2012 04:24 AM EDT)
• Minxi Jiang (11/02/2012 12:56 PM EDT)
• Chris Becker (11/02/2012 01:40 PM EDT)
• Radu-Alexandru Todor (11/02/2012 02:58 PM EDT)
• Adrian Orzepowski (11/02/2012 03:50 PM EDT)
• Marten Precht (11/02/2012 05:13 PM EDT)
• Alex Stangl (11/02/2012 06:11 PM EDT)
• Simin Cheng (11/03/2012 06:42 AM EDT)
• Marcello Herreshoff (11/03/2012 02:07 PM EDT)
• Stefanie Homberger (11/03/2012 04:51 PM EDT)
• Øyvind Grotmol (11/03/2012 07:10 PM EDT)
• John Tromp (11/03/2012 08:11 PM EDT)
• Ashfaque Shaikh (11/04/2012 03:58 AM EDT)
• Fred Schalekamp (11/04/2012 07:37 AM EDT)
• Stanislav Grudnitskiy (11/04/2012 01:00 PM EDT)
• John Snyder (11/04/2012 02:55 PM EDT)
• Stancu Mihai (11/04/2012 04:58 PM EDT)
• Mathias Schenker (11/04/2012 06:30 PM EDT)
• Harald Bögeholz (11/04/2012 07:16 PM EDT)
• Peter Gerritson (11/04/2012 11:21 PM EDT)
• Simon Foster (11/05/2012 06:11 AM EDT)
• Kevin Bauer (11/05/2012 05:09 PM EDT)
• Lewei Weng (11/06/2012 07:07 AM EDT)
• Kurt Hectic (11/06/2012 12:30 PM EDT)
• Josh Small (11/06/2012 02:46 PM EDT)
• Tony Maric & Vicki Kysar (11/06/2012 04:15 PM EDT)
• Shilei Zang (11/07/2012 12:36 AM EDT)
• Movin Jain (11/07/2012 06:02 AM EDT)
• Kirill Bezmaternykh (11/07/2012 06:45 AM EDT)
• James Dow Allen (11/07/2012 06:51 PM EDT)
• José Eduardo Gaboardi de Carvalho (11/07/2012 11:04 PM EDT)
• Chhavi Gupta (11/08/2012 12:34 AM EDT)
• Oleksandr Pavlyk (11/08/2012 02:04 PM EDT)
• Todd Will (11/08/2012 04:06 PM EDT)
• Benjamin Raibaud (11/08/2012 06:48 PM EDT)
• Florian Fischer (11/08/2012 09:07 PM EDT)
• Qinghua Zhu (11/09/2012 01:28 AM EDT)
• Jintong Zheng (11/09/2012 01:30 AM EDT)
• Peter Holdsworth (11/09/2012 07:04 AM EDT)
• Alex Wagner (11/09/2012 05:12 PM EDT)
• Jay Joshi (11/10/2012 05:51 AM EDT)
• Lorenzo Gianferrari Pini (11/10/2012 10:31 AM EDT)
• Klaus Nagel (11/10/2012 11:08 AM EDT)
• Adam Kozdron (11/10/2012 01:41 PM EDT)
• Tengyuan Liang (11/10/2012 02:07 PM EDT)
• Maris Van Sprang (11/10/2012 07:09 PM EDT)
• Fletcher Dostie (11/11/2012 04:36 AM EDT)
• Nir Galili-Kedem (11/11/2012 05:56 AM EDT)
• Matej Mužila (11/11/2012 09:46 PM EDT)
• Tony Harrison (11/11/2012 11:23 PM EDT)
• Michael Rosola (11/12/2012 01:41 AM EDT)
• Abhishek Kumar (11/12/2012 01:54 AM EDT)
• Greg Bubnis (11/12/2012 08:22 AM EDT)
• Hannes Schenck (11/12/2012 11:15 AM EDT)
• Tomek Czajka (11/13/2012 03:18 AM EDT)
• Siva Dirisala (11/13/2012 09:34 PM EDT)
• Mark Pervovskiy (11/14/2012 04:19 PM EDT)
• Aaron Malachi (11/15/2012 10:01 AM EDT)
• Albert Stadler (11/15/2012 01:42 PM EDT)
• Michael Hallberg (11/15/2012 02:26 PM EDT)
• Armin Krauss (11/16/2012 10:30 AM EDT)
• Raúl Mora Pastor (11/16/2012 11:17 AM EDT)
• David Greer (11/16/2012 04:39 PM EDT)
• Wolfgang Laufer (11/16/2012 10:34 PM EDT)
• Zhichen Zhao (11/18/2012 12:02 AM EDT)
• Shouky Dan & Tamir Ganor (11/18/2012 06:00 AM EDT)
• Liubing Yu (11/19/2012 04:39 AM EDT)
• Balkrishna D Ketkar (11/19/2012 07:28 AM EDT)
• Joaquim Neves Carrapa (11/19/2012 01:38 PM EDT)
• Vivek Ranjan Nema (11/19/2012 09:44 PM EDT)
• Javier Rodriguez (11/19/2012 11:45 PM EDT)
• Avishalom Shalit (11/20/2012 10:08 AM EDT)
• Christian Pape (11/20/2012 04:54 PM EDT)
• Hossein Khodadad (11/20/2012 05:57 PM EDT)
• i (11/20/2012 05:57 PM EDT)
• Don Ryan (11/21/2012 02:40 AM EDT)
• Gale Greenlee (11/21/2012 12:46 PM EDT)
• Rudy Cortembert (11/22/2012 01:01 PM EDT)
• Daniel Lincke (11/22/2012 01:33 PM EDT)
• Brett Yost (11/22/2012 07:35 PM EDT)
• Philip Cerles (11/22/2012 08:16 PM EDT)
• Luis Ramada Pereira (11/23/2012 11:32 PM EDT)
• Gyorgy Gyomai (11/24/2012 04:17 PM EDT)
• Seongwoo Hong (11/24/2012 04:21 PM EDT)
• Nikhil Sheth (11/25/2012 12:13 AM EDT)
• Omid Motahed (11/25/2012 01:06 PM EDT)
• Brian Park (11/25/2012 01:50 PM EDT)
• Chris Shannon (11/27/2012 02:00 AM EDT)
• Jong Wook Kim (11/27/2012 02:19 AM EDT)
• Aditya Utturwar (11/27/2012 01:49 PM EDT)
• Hamidreza Bidar (11/27/2012 05:05 PM EDT)
• Franza Cavalcante Jr (11/27/2012 07:40 PM EDT)
• Ariel Flat (11/28/2012 04:51 AM EDT)
• Adam Daire (11/28/2012 02:53 PM EDT)
• Mike Seidel (11/28/2012 07:07 PM EDT)
• Shmuel Menachem Spiegel (11/30/2012 04:45 AM EDT)
• Husen Wang (11/30/2012 12:41 PM EDT)
• Edgardo Deza (11/30/2012 03:19 PM EDT)
• Sergey Grishaev (11/30/2012 07:49 PM EDT)
• Ben Andken (11/30/2012 11:50 PM EDT)
• Adriana Clerici (12/01/2012 06:21 AM EDT)
• Andrew Rochon (12/03/2012 05:07 AM EDT)