8
$\begingroup$

It is known that spiders of the species L. Latrunculorum Cannibalis build immense (virtually unlimited) communities where members arrange in huge chessboard-like webs with black males and white females each surrounded by four individuals of the opposite sex.

At the beginning of the mating season, males randomly approach and court one of the neighboring females. Females only pair with one male, which is eaten after copulation. If approached by two or more males, females will choose one with no particular preference, and reject the other ones. Rejected males go back to their home locations where they have a chance to approach and court another uncoupled neighboring female, as long as there are any. The process continues until all mating possibilities are exhausted.

What is the highest possible percentage of male spiders who surivive the mating season?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
12
$\begingroup$

Another way to look at this is we want the fewest number of pairings ($2\times1$ or $1\times2$ collections of adjacent squares) that fit into the area, subject to the constraint that no two adjacent squares can be un-paired: a "loosest packing" of pairs. Borrowing PrisonMonkeys's idea of a repeatable $6\times6$ grid, I have constructed the following:

M f M f M f
F M F M F M
m F m F m F
F m F m F m
M F M F M F
f M f M f M

where each capital letter is paired with the capital letter directly above/below it. I believe this is optimal because each pair here is adjacent to exactly two other pairs, and any pair which is adjacent to only one other pair would break the rule against unpaired adjacent squares.

This spares 6 of 18 males, or exactly 1/3.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very nice. I was looking for a pattern with more symmetry or something more regular, but couldn't quite find it. This indeed seems optimal. $\endgroup$
    – PrisonMonkeys
    Apr 1, 2015 at 0:54
  • 1
    $\begingroup$ This is pretty regular, but you can do it in a way that may be more aesthetically pleasing (though they're really quite equivalent) with everyone on a diagonal sharing the same fate, with diagonals M-F-m-F-M-f repeating, again with the same surviving percentage. $\endgroup$
    – aes
    Apr 1, 2015 at 6:19
5
$\begingroup$

EDIT: dmitch's solution is superior to my own with a survival rate of 1/3 instead of 1/5.

The highest surviving percentage is

20%

For every male that lives, the 4 females around him must have mated. Therefore, at least 4 males must die for every 1 that survives so the highest possible survival rate is 20%. There is a solution for this condition (as shown below) so we've achieved the max. In the diagram, the two cells of the same color show a mating pair. Essentially, each male surrounding the surviving male (M0) tries to mate with a female surrounding M0. M0 also approaches one of the females but is rejected. Diagram Note that this will leave as many females without mates as it leaves males alive as denoted by F0.

EDIT: If we're allowed to pick the matrix size, then I pick a matrix size of 1. The only spider is a male. 100% of the males survive. If there is required to be a female, then I pick a matrix of 5 with a single female surrounded by 4 males. 75% of the males survive.

Improve this answer
$\endgroup$
8
  • $\begingroup$ You are averaging over an infinite set. Wouldn't it be theoretically possible that there are other ways of assigning dead males to surviving males that yield other percentages? (Note that the same dead male might be assigned to two different surviving males.) $\endgroup$
    – Haobin
    Mar 31, 2015 at 17:06
  • 2
    $\begingroup$ Your illustration has males and females next to each other. I think you just need to shift each "row" over by 1. So, you'd have your surviving males, but you'd also have the same rate of non-mating females. $\endgroup$
    – JonTheMon
    Mar 31, 2015 at 17:09
  • $\begingroup$ @Haobin I'm averaging over an infinite set because the question did not specify a boundary. The only guidance is that the communities are "virtually unlimited" so I went with an infinite approximation. Except for very special cases like a web with 3 tiles (2 M, 1 F), you're not going to get a significantly better survival rate. $\endgroup$
    – Engineer Toast
    Mar 31, 2015 at 17:40
  • $\begingroup$ @JonTheMon You are completely correct. I have changed the diagram and noticed that this also creates F0 (females that do note mate). Of course, it makes sense that there will be an equal number of surviving males and females that do not mate as the two are complementary. $\endgroup$
    – Engineer Toast
    Mar 31, 2015 at 19:57
  • $\begingroup$ The argument for why 20% is optimal is not correct. You say that every male corresponds to 4 females all of whom eat males, but this need not be the case; an uneaten male only needs one female next to it who has eaten a different male. Moreover, it is not true true that two males must correspond to disjoint sets of 4 females. $\endgroup$
    – Caleb Stanford
    Mar 31, 2015 at 22:47
3
$\begingroup$

I found a solution on a repeatable 6x6 matrix which saves 4 males. On a 6x6 matrix, there would be 18 males, so this gives a survival rate of 22,22%.

My solution

Improve this answer
$\endgroup$
3
$\begingroup$

Another way to get to the solution:

Imagine a "safe" male: He is only safe if all 4 females around him have killed someone else. Since we are in an infinite grid, we can ignore the initial setup and just have to ask us: To get another male safe, how many nee to sacrifice their lives? Imagine the Safe Spider as (M) The sacrificed Males are connected to the respective females. - Uninteresting Spiders are represented by dots.

.  .  M  .  .
      |
.  M  F  .  .
   |
.  F (M) F--M

.  .  F--M  .

To get the spider lower left from him safe too, we need to satisfy two new Females and have to sacrifice two more Males.

.  .  .  M  .  .
         |
.  .  M  F  .  .
      |
.  M  F (M) F--M
   #
.  F [M] F--M  .

.  .  F==M  .  .

And we can repeat this pattern to infinity. And we can also place several of these survival-diagonals of males next to each other, each with the same rule:

.  .  .  M  F (M) F--M [F] M  F (M) F--M
         |                 |
.  .  M  F (M) F--M [F] M  F (M) F--M  .
      |                 |
.  M  F (M) F--M [F] M  F (M) F--M  .  .
   |                 |
M  F (M) F--M [F] M  F (M) F--M  .  .  .
|                 |
F (M) F--M [F] M  F (M) F--M  .  .  .  .

sacrifice two, to save one -> Which leads to a maximum survival rate of 1/3

Improve this answer
$\endgroup$

Your Answer

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

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