AHA

Two people are guaranteed to carry the message.

On the first night, you assign the person to your left as the second message carrier.

(This might run into the same problem as before)

Er, hm.

I'm just going to add that to the fact repository for now. If two people have a message, it is guaranteed to be able to get to a third person.

In general, if $n$ people are carrying a message, you can guarantee that you can get it to $n+1$ people simply by having all $n$ broadcast it.

Hmmm.

There's no way for the warden to stop $n$ people from attaining a $+1$th person.

That's important. What if everybody who has a number $m$ broadcasts at the same time?

sorry, I'm being unclear

$m$ starts at zero since nobody has heard any number

Except you; you start by broadcasting $1$.

if he's heard a number before, he broadcasts 1; otherwise, he broadcasts 2

ah, nevermind, same trap as before

the counting method I'm going for is: everyone starts at zero; if you hear a number for the first time, add one to it

that's the basic solution to counting problems

so it's probably a good place to start, but yeah, how do we know if everyone has heard a number...

oh that's easy

oh nevermind, it's easy if you know $n$.

>__>

$2^n$ might be more identifying

hm, yeah

how do nodes learn their number?

ahhhhh

each node can be given an identifying prime number

ohh

okay, so each node broadcasts the products of all the primes it's heard (only one of each) up to this point

so let's say you've seeded 2, 3, and 5

you broadcast 7, and 3 hears it

now, 3 broadcasts 21

hold on a sec, I'm not sure I follow the propagation method

let's say you've heard a set $p_i$ of primes, and hear a prime set $p_o$

that gives you a new node ID, and you broadcast $\Pi \{p_i...p_o\}$?

in other words, if you are $2*3*7*11$ with node ID 11, and you hear $5*7*13$, you become $2*3*5*7*11*13$?

ahh, I see

by broadcasting 6, you're saying "I am node ID 3, and node ID 2 has passed through here."

then you take on whatever ID was passed to you, and tack it onto your current product

when node A broadcasts it, does node A give up that ID?

in other words, node A receives $p_1$. on the next iteration, node A broadcasts $p_1$ and receives nothing; what does node A broadcast after that?

but that means multiple people could take on the same node ID

it's possible to indicate which position is your current ID using powers of two, but for large $n$ you're going to end up with $2^{2n}$ iterations

hmm

how about this: 2 is reserved to indicate whether the maximum number is your current ID?

in other words, if you receive $3*7$, you know that the node before you has seen 3 and 7, but doesn't currently have an ID

but if you see $2*3*7$, then you know that the node before you had ID 7, so you're now ID 7

sure does

someone can't become a node without the person behind them telling them to become that node

and only one person has that power at a time

warden can't trap who's been seen

ah, but on the next step, both you and A are broadcasting that you've seen 11

it doesn't matter who 11 actually is, just that you've both seen it

I thought only the first person could create new prime IDs?

?

nope!

wait hm

shoot, yep

hrrrrrng, we're so close

okay, so we might be able to solve this by introducing a checksum step

which might be necessary anyway in order to detect if the puzzle is solved

there is an algorithm to generate the highest prime

hrrrrrng

periodically, you send out a stop signal

Someone who does not have an ID must hear it after $q$ iterations, where $q$ is the number of primes currently out in the wild

If they hear it, they issue an abort command, which must come back to you in.... dammit, you don't know how many iterations

GOT IT I think

On prime-sending steps, follow the above rules

Wait $k$ days after sending out the $k$th prime. (i.e. let $p_1$ out for one day, so that at most one person knows about it)

After that, enter a checksum step.

During the checksum, everyone broadcasts the number of primes they've seen.

If they receive a number different from their own, then they instead broadcast an abort signal.

Because there are $k+1$ days in the checksum step, the abort signal must come back to you if it is going to at all.

However, if the abort signal doesn't come back, then $k$ is the number of other people in the circle.

If it does come back, broadcast $p_{k+1}$ and start over.

Boom. Solved.

Er, wait, crap.

Okay, here's the core of the problem: ensure that $k$ people have heard a number on day $k$. It doesn't even matter what that number is; it could just be 3.

Hell, it doesn't even have to be a specific number.

I have the verification algorithm down; you just need to know how many people should have heard something, and let one more than that quantity tell you what they've heard. If someone tells you "crap, this thing is screwed up," you jump onto the next iteration.

It's ensuring $k$ on iteration $k$ that's the problem.

I passed out >_>

there is still room! it's a random solution

How does it work?

Ahhhh, of course.

Magic. I should have known!

$\lceil\log_2 k\rceil$, yeah

hm