# How many trees in a forest?

Some time ago I met a forester. He told that there are only larches and spruces in his forest. He also said that there are exactly $10$ spruces at the distance of exactly 1 km from each larch. Next, he argued that there are more larches than spruces in his forest. Can he be right?

-
A bit confused...If there are 10 spruces exactly 1km from $each$ larch, wouldn't the spruces lie along a circle with the $only$ larch at its center? – David Mitra Nov 11 '11 at 8:46
If you are the downvoter then you have no reason to. This question is perfectly well stated. If you cannot make sense out of it perhaps you should try thinking a little more instead of saying that OP is stupid by downvoting. This is a good question. – Patrick Da Silva Nov 11 '11 at 9:07
I think the comments are due to an ambiguity in the order of quantifiers. David applied what seems to me the literal reading, namely, there exist 10 spruces such that for each larch the spruces are 1 km from it, whereas I think the question is intended to say that for each larch there are 10 spruces that are 1 km from it. Martin, if that's what you meant, I think you should clarify the question. By the way, thanks for teaching me a new word -- I had no idea what the English word for a spruce is, and I wasn't even aware that I didn't know it :-) – joriki Nov 11 '11 at 9:27
Obviously this is a puzzle, not something that actually happened. Martin, do you know the answer? I note that there are simple examples with 10 replaced by 2; put spruces at $(-1,0),(0,0),(1,0)$ and larches at $(\pm1/2,\pm c)$ with $c$ chosen to make the distances 1; more larches than spruces. – Gerry Myerson Nov 11 '11 at 11:34
@alex: In that case, the question might be clarified to read: Some time ago, before the remaining $7$ or $22$ dimensions of space-time were compacted, I met a forester... – joriki Nov 11 '11 at 22:29

Nice number theoretic question in disguise! Not being much of a botanist I'll call larches X and spruces Y, or I won't be able to tell them apart. Also I take "argued" in the question to mean "asserted", since one can obviously not argue that there must be more larches than spruces, but there can be.

Here is a solution, or rather a method to construct a solution. I'll take the Y trees to form a large square grid, the distances between neigbours being 2 units (the unit of length is to be determined). In those units these trees therefore occupy the points with both coordinates even, filling a large region around the origin (we'll see about the boundary of the forest later).

There will be an X tree at $(2a+1,2b)$ and at $(2a,2b+1)$ for any integers $a,b$ for which this does not come too close to the limit of the Y trees.

    0 0 0 0 0 0 0 0

0 0*0*0*0*0*0 0
* * * * * *
0 0*0*0*0*0*0 0
* * * * * *
0 0*0*0*0*0*0 0
* * * * * *
0 0*0*0*0*0*0 0    X=*, Y=0
* * * * * *
0 0*0*0*0*0*0 0
* * * * * *
0 0*0*0*0*0*0 0

0 0 0 0 0 0 0 0


Within the area occupied by X trees they are twice as numerous as the Y trees, so we can make the X trees win out overall by making the forest large enough (the advantage for X increases with the area, while the boundary, where the X have stopped but not yet the Y, grows only with the circumference).

Now the challenge is to find a radius such that on a circle around each X there are exactly 10 Y trees. If this works for the X tree at $(1,0)$, it will work by translation and diagonal reflection symmetry for all X, provided we stop planting X when coming so close to the end of the forest that the circle protrudes outside.

Now we have our number theoretic question: for which integer $N$ (the square of the radius) are there exactly 10 integer solutions $(x,y)$ to the equation $(2x-1)^2+(2y)^2=N$ (giving a Y tree at $(2x,2y)$, at distance $\sqrt{N}$ of $(1,0)$)? Obviously $N$ must be odd, and it is easy to see that dropping the parity condition on the two squares summing to $N$ will double the amount of solutions, every (odd,even) solution giving an (even,odd) solution by interchange. So we need to have $N$ such that $k^2+l^2=N$ has exactly 20 integer solutions $(k,l)$. I claim the smallest such $N$ is $N=5^4=625$. That it is indeed a solution is easy to see, with 5 solutions in the positive quadrant (taken to include the the positive x-axis but not the y-axis): $(25,0)$, $(24,7)$, $(20,15)$, $(15,20)$ and $(7,24)$, and the remaining solutions are obtained from these by applying quarter turns.

To explain the "smallest such $N$" part, I applied to following theorem 2.3.12 from the course on arithmetic I gave last year (in French; I have no other reference at hand for the full statement, but its first part is well known, and the rest is easy once you know enough about Gaussian integers to prove the first part):

Theorem. Let $N$ be a positive integer, and $N=p_1^{m_1}\ldots p_l^{m_l}$ its prime factorization. A necessary and sufficient condition for the existence of integers $a,b$ with $N=a^2+b^2$ is that for every $p_i$ that is congruent to $3$ modulo $4$ the corresponding exponent $m_i$ be even. Moreover the number of solutions is given by $$4 \prod_{\kern-14pt p_i\equiv1\pmod4\kern-14pt}(m_i+1).$$

So the number is always divisible by 4 (for obvious reasons) and for the other factors only primes that are 1 modulo 4 are useful; for a factor 5 one needs an exponent $m_1=4$, and the smallest appropriate prime is $p_1=5$, whence $N=5^4=625$. The actual solutions are easily constucted using Gaussian integer multiplication, from the elements $2\pm\mathbf{i}$ of norm $\sqrt5$.

All that remains is to choose the unit of measure to be $\frac1{25}\,\textrm{km}=40\,\textrm{m}$, and to find a size of the forest large enough that the X outnumber the Y even though they stop a kilometer before the the edge of the area planted with Y trees (left as exercise).

It may be argued that when trees are at least $40$ meters apart, one cannot reasonably talk about a forest. I would roughly guess a realistic distance between trees to be somewhere between $1$ and $5$ meters, which means we need $N$ to be larger, and in particular $\sqrt{N}$ (which is necessarily integer for a solution) in the range from $200$ to $1000$. This leaves us plenty of possibilities for $\sqrt{N}$, which can be any odd number whose set of prime factors $p$ with $p\equiv1\pmod4$ is a singleton, and which prime factor has multiplicity $2$. This leaves the possibilities $225$, $275$, $475$, $507$, $525$, $575$, $675$, $775$, $825$, $867$. Taking $867$ as an interesting value (giving a distance between trees of $\frac{1000}{867}\approx 1.15$ meter) the fundamental solutions of $k^2+l^2=N=867^2=751689$ are $(k,l)$ one of $(867,0)$, $(765,408)$ and $(720,483)$; the $17$ other solutions follow these by obvious symmetries.

-

Say there are exactly 10 spruces, all growing at the same point. And a million larches, all exactly 1 km from that point.

-
10 at exactly the same point.. I think that is not allowed. – picakhu Nov 11 '11 at 23:01
These are fermilarches. – joriki Nov 12 '11 at 6:13

Not an answer, but I think some top-level clarification is needed here. From the comments, it seems that the following interpretation is probably what was intended:

1. For each larch, the number of spruces that are exactly 1km from it is exactly 10.
2. There are more larches than spruces.

And the question is: Is this possible?

-

Yes, he could. 10 spruces are in the middle of a formation, each point one kilometer away from the spruces. Larches could be planted around them,so there could be 20 larches sharing 10 spruces. Also the spruces could be in one metre square.

-
Your description of the arrangement is somewhat ambiguous, but you seem to have the trees standing along two concentric circles. That wouldn't work. The larches are each supposed to be exactly 1 km away from exactly 10 spruces, i.e. there should be exactly 10 spruces along the circle of radius 1 km around each larch. – epimorphic Jan 31 at 4:38
Thanks,corrected – ezekiel Jan 31 at 23:55
I still can't quite understand your picture. Is there a larch at "each point one kilometer away from the [center / spruces]"? If so, your answer is basically a duplicate of GEdgar's. – epimorphic Feb 1 at 0:11
I didn't quite understand GEdgar's question. I thought I should edit it, but I don't have enough rep to do that. So I wrote my own answer, but I still do not know if it is a duplicate – ezekiel Feb 1 at 0:17
Did you mean that you didn't have enough rep to comment? If not: If you don't understand someone's post, or if you can't express yourself in clear English prose (which unfortunately seems to be the case here), then you shouldn't edit it. – epimorphic Feb 1 at 4:22