"This guy doesn't like your leadership, he's decided to start a rebellion." says Bengt.
"What? No he hasn't."
"Has too."
"Well, he can't do anything about it, because the other orcs will blow his head off if they find out."
"Aren't the orcs supposed to be some kind of fantasy monster kind of guys? You mean they have guns?"
"They sure do, and they don't like traitors."
"But they're also not happy with the way that guy in black is pushing them around. In fact, out of the n soldiers, I believe a fraction k (so k*n soldiers) would like to join the rebellion."
"Oh really. But in that case, there are also p*n soldiers who would kill those rebels if they knew about it."
"Why p?"
"I don't know, p for… peace? No, I know: Police."
"Haha, yeah, okay."
"What, why did you pick k?"
"K for constant, duh. Anyway, that leaves a fraction 1-p-k, let's call it… r, for remaining. A total of r*n soldiers who couldn't care less."
"Or at least they don't care very much. It might be that they care slightly, but not enough."
"True. So, each of the instigators of the rebellion…"
"…who are infinitesimally few compared to n…"
"…but many compared to 1/k, he asks one other orc at a time whether he would like to join the revolution. If it's a k-type guy, he joins, and goes on to ask other random guys. If it's a p-type, he shoots the guy for asking. If it's an r-type, he just says no."
"And how does it end?"
"Well, the rebels keep track of the opinions of all the guys they have previously asked, so they don't ask them again. When they have asked everyone, they start the rebellion."
"Do you think they can win?"
"That's not part of the question."
- What conditions must p and k satisfy for the rebellion to spread?
- Suppose the potential rebels (the k-guys) are not so keen on getting shot, so they only agree to asking two other random guys. What are the conditions?
- As in a, but suppose when a rebel asks a p-guy, they both have equal chances of shooting the other guy.
- As in c, but as in b, not as in a.
- As in d, but now suppose if the asking guy gets shot, the rebels don't know who the askee was, so they will eventually ask him again.
- Sort of like in a, but now the rebels are a little more cautious: The instigators all know each other, but each new rebel knows only the identity of his recruiter (and recruitees). Each day, each rebel who has not already asked q people ask one more. They might therefore ask a guy who has actually already joined, in which case that guy thus effectively has another recruiter. If a rebel asks a p-guy, they both get shot. If a rebel has no recruiters still alive, he loses contact with the group and reverts to the same state as before he joined (also resetting his asking quota). When the instigators determine that half the soldiers have been asked, they start the rebellion. What should q be in order to make the rebellion likely to happen?
(This one might be more difficult. You can solve it next month, if you like.)
Posts
