6
$\begingroup$

$N$ Hyenas are standing on a plane region in a forest. At $t=-1$, they see dead meat nearby. Being selfish, at $t=0$, each Hyena attacks the Hyena which is closest to it. All pairwise distances between them are distinct.

Question:

At most how many Hyenas can remain unattacked?

Example:

$N=1$, answer is $1$ since there is no other Hyena to attack the first Hyena

$N=2$, answer is $0$ (both attack each other)

$N=3$, answer is $1$

$N=7$, answer is $5$

$N=10$, answer is $7$

Note:

1) The closest pair is always under attack for $N>1$.

2) For odd $N$, it is easy to see that there exists at least $1$ Hyena which is not under attack.

Reduced Version:

Solve for $N=100$

$\endgroup$
3
  • $\begingroup$ rot13(Cerggl fher gurl nyy unir gb or cynprq va urkntbaf, ohg pna'g or obgurerq gb evtbebhfyl cebir vg. Nz v pbeerpg?) $\endgroup$
    – DL33
    Mar 29, 2023 at 22:38
  • $\begingroup$ @Oray I’m interested in creating formula for N, for N > 14, upto which I’ve solved this problem. $\endgroup$
    – thisIs4d
    Mar 30, 2023 at 21:17
  • 1
    $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it. If not, some responses to the answerers to help steer them in the right direction would be helpful. $\endgroup$
    – Rubio
    Apr 14, 2023 at 22:18

2 Answers 2

4
$\begingroup$

We can slightly rephrase this question as "For a given number of attacked hyenas, what is the maximum number of unattacked hyenas we can have?"
Particularly, since hyenas can be divided into clusters such that attacks only occur within a cluster, how many unattacked hyenas can there be in a cluster containing a given number of attacked hyenas?

We start with the observation that

since distances must be distinct, we can't have any configuration that requires exactly identical distances (e.g. a hyena having some attacking relationship with six hyenas). However, by careful management of arbitrarily small differences, we can get arbitrarily close to such a configuration.
For instance, the circles from a pair of attacked hyenas can admit eight more circles of exactly the same radius, but since we can't have exact configurations only seven hyenas will fit.
What we can do, is to take this partial configuration with six unattacked hyenas: enter image description here
By shrinking our infinitesimals, we can make a circle that touches the blue attacked hyena and none of the others arbitrarily large - enough to fit up to four more unattacked hyenas, like so: enter image description here
However, the configuration functions as a virtual fifth hyena, so if we wish to repeat this construction we can only have added three hyenas (the end result would resemble what you'd have if you replaced A and its three attackers with a sufficiently small copy of the entire group of eight). This construction allows us to have $3a+1$ unattacked hyenas in a cluster of $a$ attacked hyenas.

To justify this incremental approach, we only need that the distinctness of distances means that every configuration of attacked hyena can be built up this way, and having interference between attacked hyenas can only decrease the possible numbers of unattacked hyenas.

Of course, maximizing the proportion of unattacked hyenas requires us to maximize the contribution of the $+1$, which is achieved by maximizing the number of clusters. By doing so, we can get $7a$ unattacked hyenas for every $2a$ attacked ones (or $9a$ total), and $7a+3$ unattacked hyenas for every $2a+1$ attacked ones (or $9a+4$ total). The sequence of unattacked hyenas threfore goes $7k, 7k, 7k+1, 7k+2, 7k+3, 7k+3, 7k+4, 7k+5, 7k+6$ for $N=9k+r$ hyenas with $k$ positive.

$\endgroup$
9
  • $\begingroup$ In the incremental approach, we can think about the convex hull of a cluster. Every vertex of the hull would necessarily have a free area greater than 180 degrees, which ensures 3 new Hyenas, with only +1 attacked Hyena. This works for 0,1,2,3 mod 9. But when N = 4 mod 9, I did not quite understand how are you placing the Hyenas. One more thing, aren't we getting a lower bound here? How is the induction working for the upper bound? $\endgroup$
    – thisIs4d
    Mar 31, 2023 at 14:01
  • 1
    $\begingroup$ We are getting a lower bound, but I don't immediately see why it wouldn't be sharp. I will continue to investigate. $\endgroup$ Mar 31, 2023 at 22:13
  • $\begingroup$ @thisIs4d for N=4 mod 9, e.g., 13, there will be more than 3 attacked Hyenas according to this construction (since with 3 attacked Hyenas max you have 12). So it's at least 4 attacked Hyenas, and with 4 attacked Hyenas, we can simply make two clusters, say, size 7 (2 attacked, 5 unattacked) and 6 (2 attacked, 4 unattacked). The idea when adding one more Hyena is to consider two options: add to existing cluster, potentially adding up to 3 attacked Hyenas in that cluster, or to create a new cluster (potentially reconfiguring other clusters). Pick the max unattacked Hyenas of the two options. $\endgroup$
    – justhalf
    Apr 5, 2023 at 6:24
  • $\begingroup$ Huh, you're right. The answer claims 10/13. My bad. Then I also don't know how this answer can make 10/13 configuration from the description. $\endgroup$
    – justhalf
    Apr 5, 2023 at 6:30
  • $\begingroup$ @justhalf I have constructed the 10/13 configuration. $\endgroup$ Apr 5, 2023 at 15:19
1
$\begingroup$

The following presents the maximum number of unattacked hyenas alongside their corresponding ratio:

$\frac{7}{9}$

and here is the representation of this;

enter image description here

and here is a better representation

enter image description here

with the right distances.

If you would like to add more hyenas after this point, you need to create a new attacked hyena including the red and blue ones shown above; such as;

enter image description here

let's put another 1 (11 hyenas) and the result becomes

enter image description here

but if we would like to add one more,

we cannot use that new hyena anymore, because no place is left to put to attack that green one. we need to find a better way to do that with 12 hyenas.

such as

enter image description here

which results as

$\frac{9}{12}$

so if N goes to a big number; you can have separate

"9 of hyenas" as this is

and at the end you will end up with

Assuming you possess N Hyenas, the maximum number of Hyenas that can stay unattacked is $\frac{7N}{9}$

and

Assuming you have 18 hyenas, you could create two distinct groups of 9 hyenas each, completely separated from one another. This arrangement would leave you with 14 hyenas that are not under attack, and you can have the same ratio with 18 or any 9N one.

$\endgroup$
9
  • $\begingroup$ actually if we have 9 Hyenas, we can save 7 Hyenas, which is correctly depicted by you. But when N=10, we can prove that atleast 3 will always be attacked in any configuration. So answer for N=10 is 7, and not 8. $\endgroup$
    – thisIs4d
    Mar 30, 2023 at 21:23
  • $\begingroup$ @thisIs4d i did not say the other way around. :) i said it remains the same which refers to 7 $\endgroup$
    – Oray
    Mar 31, 2023 at 5:06
  • $\begingroup$ oh, can you clarify the statement “To avoid this issue you should place…”? How can you ensure this…any proof? Also, please note this creates a lower bound, not a strict upper bound. That means, we can definitely save 7/9, but can we save more? $\endgroup$
    – thisIs4d
    Mar 31, 2023 at 6:51
  • $\begingroup$ Seperation of groups in ratio 7/9 does not necessarily lead to an optimal configuration. Here, you must also prove that 7/9 is the largest ratio we can get in any configuration. Suppose we get 11 for N=14, then 11/14 is a greater ratio. Moreover, having largest ratio also is insufficient to prove the cases when we have high remainders. $\endgroup$
    – thisIs4d
    Mar 31, 2023 at 6:52
  • $\begingroup$ I understand your perspective, @thisIs4d, and it is worth noting that the 7/9 ratio after 18 Hyena is a generally applicable principle. such as if you have 18/19 hyena, you will have 7+7 unattacked one etc. However, proving this in a specific case may be challenging. While I may not be fully proficient in proving cases, I can assure you that it serves as an upper bound. maybe someone else has a good way to show a proof. $\endgroup$
    – Oray
    Mar 31, 2023 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.