Agent 001's faulty delivery box

Question

There are 10 agents living at their respective homes. They used a secret mailing system that sends one box at a time, but it is now spoilt. Now, it functions as follows:

• It counts the number of deliveries to each agent.
• It always sends the box to the agent with the lowest delivery count.
• If there is more than one such agent, it will pick one of them randomly.
• Once the box reaches an agent, it will remain there until that agent decides to send it.
• For security, the box will never travel unless there is a lock on it.
• The time taken by the distribution system to deliver a box is variable and random and always non-negligible, so waiting for a fixed number of seconds/minutes/days before sending a box is not a viable way of sending information. The transmission system creates a queue if it receives boxes while it already has a box in the process of being transmitted. Only one box can be in the process of transmission at one point in time, the rest are all on hold in the queue.

Rules:

• Each agent has an unlimited supply of boxes of various sizes, and padlocks (each with a single key). The padlocks look identical, the keys do not. This supply is given to them after the pre-planning phase.
• Any number of locked padlocks can be put on any box.
• A box can contain open/locked padlocks, keys, papers, and boxes, each with/without its own locks. (Note the difference between putting a padlock on a box, i.e., locking it, and putting a padlock in a box, i.e., transporting it)
• A padlock can be opened or closed only with its key.
• Boxes cannot change size. If Box A was once placed in Box B, Box B can not be placed in Box A ever.
• Keys and locks cannot be duplicated. Papers can be photocopied.
• The agents can have a pre-arranged plan, before they start the mission. Once the mission has started, they can communicate with each other only through papers (which they can create) that are sent in the box.
• The box used for delivery can be changed by an agent who opens it and can transfer the contents to a larger (or maybe even smaller) box. However, the mailing system will treat it just like the old one. The mailing order remains unchanged. The size of the new box will be random and hence its dimensions cannot convey information.
• pre-arranged planning only involves strategy talk, no handing out/exchanging locks or keys.
• no writings are to be made on the outside of the box sent around, nor messages taped to the side. No unlocked padlocks, etc. can be sticking out of the box.
• the lock(s) that is/are to be on the box when the message is sent, is/are required to be in locked state.
• the 'box transfer count' isn't visible, but held by the agency that does the box transportation.
• a person can send multiple boxes one after the other, but there should be negligible time lag between the transmissions.

Mission

Agent 001 has received a top secret message on a sheet of paper. He needs to inform all the agents. What is the minimum number of transmissions it will take before he can guarantee that everyone has received it (or a copy of it)?

Answer 1

Well, I spent a lot of time to make this out. But now I have got the solution ready. It's not spoilerware, because it's too long (moderation, anyone?)

220 transmissions to win, 230 - to inform the Agent.

But first I will restate a bit simpler version of 270(269?) transmissions' solution, to get those of you, who didn't get it, into the parcel business.

I use term "delivery score" (ds) as amount of parcels a given agent gets. I also use "maximum delivery score" as a maximum ds among all agents (thus, starting at mds = 0). Due to Post Machine's nature, every ds at any given moment equals either mds, or mds-1. I also use 00X as "any agent except for 001", but that's obvious.

Now let us look at the first modelled situation: agent 00X got a box, and he wants to give it to agent 00Y. All the other agents know, that the package is intended for 00Y. 00X just throws a package in the mail, and all other agents resend it as soon as they get it. Then the pricnciple is: if mds=N at the beginning, then when 00Y gets the box, mds will be no higher then N+1 (guaranteed).

This fact is rather obvious. First, all the agents will get ds=N. Then, the box will travel among all of them, before ds becomes N+1 for all -- thus, it will reach 00Y in time.

Retrace of 270-solution

Original "270"-solution is overcomplicated with varying order of agents. Let's make it even simpler: what if we wanted the data (interchanging the boxes) travel in a predefined order: 001-002-001-002-003-002-003-004-003-004...(please refer to original solution for locking operations). Well, we CAN do that for the same price. It's 27 travels, thus making mds no more than 27, giving us 270 steps.

Now why during "270"-solutions other agents won't take boxes for theirs? The author suggests playing with boxes' sizes. I think I have an easier solution: any agent can hang a corresponding amount of locks on a box (like, 1, 2, etc.) to mark to whom he is sending the box. Thus, agent 007 finding box with six padlocks will pass it further, and finding a box with 7 padlocks - will hang 10 more to make sure nobody else locks it and send back to 006.

So this is the 270-solution (I still don't get 269 part - I think it's a mistake or different interpretation of the problem). Remember two things from here - marking boxes with special amount of locks and common "resending a single box mechanics" (also, mds rule). It will come in handy, but not too soon.

I ALSO HAVE TO MENTION that, though 270 transmissions DO solve the problem, it is Agent 010, who will be informed that the problem has been solved. Agent 1 may still false-report that "problem's been solved" while the packages are still on the way (or vice versa). To complete the solution, agent 010 has to hand out a signal: 10 packages with "finished" written in locks, or, better, one package with "please resend this to 001 i am in good health and almost out of padlocks" written with locks). Thus, this solution is actually 280 transmissions.

That. Was. The warm-up. We're getting to the serious spy tricks. The following solution will take 220 transmissions for mailing system to be sure of mission completion and 230 transmissions to moreover inform the Agent 001 of mission completion.

220-solution

Phase (1) - Distribution.

Agent 001 gathers 10 packages with copies spy-data, locks each with a lock and sends them by mail. It is definite that every agent (including 001) will get a package. Agents 00X should hang their private padlocks on those packages as soon as they get 'em. Agent 001 opens the package he send to himself, reads the spy-data again and saves the padlock for a better use. Now the ds for every agent is 1, or mds=exact 1.

Also, every agent already got a double-locked parcel. Fast work!

Phase (2) - Chaotic retrieval.

Agent 001 gathers a blackbox (from here on "blackbox" is a box full of ink with exactly 666 locks on it. It is a common spy expression). Agent 001 sends a blackbox.

Now we have a little bit of ambiguity, as blackbox may be received by agent 00X or agent 001 himself. Let's look at the strategy of agents 00X for a minute.

Agent 00X is instructed to hold on to his first delivery and put a lock on it (see phase 1). He is also instructed: as soon as you get a second parcel please desperately try to send all parcels with two locks away.

Thus, as soon, as an agent gets a blackbox, he sends his original parcel away. Whenever he hits another agent 00Y with a two-locked parcel, he also resends these two. And etc., without any order.

But - you may think - what if agent 001 sends blackbox to 002, and 002 sends his parcel back to 001, without making contact with other agents, thus, without making them fall into chaos?

Well, exactly for that case, agent 001 will not only send blackbox, but send away his second delivery, and after that accept all the deliveries that come to him. As you can check this is enough to get "second parcel panic" signal to all of the agents (if agent 001 already got second delivery, others are guaranteed to get it before anything else gets sent to 001).

Outcome of phase 2 :

• Agent 001 has all the 9 agents' packages. We know they won't stop resending them until they get rid of them completely. Thus, the chaos will stop only after agent 001 gets all the goods.

• Agent 001 has exactly 11 delivery score. 1 is got during phase 1. 2 is the package he resent to get the gears running (also you might notice - delivery 2 could be his blackbox delivered back to him by the mail). Deliveries 3 to 11 are 9 packages he got from agents during the chaotic phase.

• Every other agent has 10 to 11 delivery score (read as: mds = 11).

Phase (3) - Housework.

Agent 001 has to find 9 keys and fit them to 9 locks. It's the most tedious phase, but it takes no transmissions.

Phase (4) - Rebalancing.

-- Oh 'e gods! - says agent 001 - I want to conduct distribution step again. But I realised, that some (maybe none) of the agents may have 10 delivery score and some - 11. I can't just send these nine boxes, for two may reach the same person! My plan is ruined! But what if... I were to make delivery score the same for every agent? Ho-ho-ho, delightlfully devilish, agent 001.

All other agents, who now got rid of the boxes, wait patiently for agent 001's move. Agent 001 creates a whitebox (it is the one with 1000 locks on it and filled with milk) and sends it throught the net. Now other agents act according to plan:

• If agent 00X with 10 delivery score gets the whitebox, he resends it.

• If agent 00X with 11 delivery score gets the whitebox (possibly: for the second time), he slams a new lock onto it and then resends it.

• When agent 001 receives the whitebox back, he counts the locks carefully. Suppose it is 1000+k. Then all the agents have at least 11 score and there is exactly k agents (besides 001) with exactly 12 score (they got +1 for box at eleven score, and each added a lock). Now...

Now agent 001 throws whitebox away (not to confuse agents), gets his supply of black boxes and sends (9-k) boxes. He is sure that they will get to remaining 11-ds agents. He is also sure, that the agents are instructed not to react to a blackbox of 12th delivery.

-- Phew! -- says agent 001. -- Now every agent (including myself) has a score of 12. I hope you're ready for more confusing steps.

Phase (5) - Distribution.

Agent 001 still got the boxes, each with a single lock. He adds a blackbox to them and sends all 10. Then he waits for the return. Every agent's ds is 13 now. 9 packages are distributed evenly - one for each, and one without a package. Maybe 001, maybe not.

Now we get back to the original method of solution - consequential single-box transmission.

Phase (6) - Order.

Let me assume that 001 got the blackbox, and then get to the case where he got a usual, one-locked box back.

Agent 001 packs the blackbox and sends it into the net. The following algorithm is pretty clear, and you might understand that it works, but the fact is: it works fast. Now any agent (including 001) reacts to a box as follows:

• If it is a blackbox and 00X has a locked box on hands - 00X takes the blackbox and sends the locked box.

• If it is a blackbox and 00X has got nothing - 00X just resends the blackbox.

• If it is a usual box (with one key), 00X tries to open it. In case of failure -- he resends it. In case of success -- he either sends another usual box (if he's got one) or a blackbox.

I tell you, that agents will all get the data in +9 mds. They wouldn't know it though, but that's another question.

Why is so?

Well. Any permutation (and we're dealing with permutation here) is a combination of cycles. I'm telling that, if the traveling box is a blackbox, then for every cycle either every person in it knows the data, either every person doesn't. It's called induction - check it for starting position (nobody, except for lucky one-cyclers, know the data) and continue to check further.

Imagine the box is black and has been just sent. Mds is N (13, for instanse). Who will replace it with a usual box? A person from 'unsatisfied cycle' will (call him Carl). Moreover, Carl will do it before other people of the cycle get the box and ds-increase - because, if they had a box, they would also replace it.

And who needs Carl's box? Well, someone from his cycle - the one that didn't get the blackbox. It means that he (...Bert?) will also increase ds by one, but only when he gets Carl's box. Two operations - sending a blackbox, swapping it, and delivering Carl's box to Bert - take +1 mds alltogether. It's... hard to comprehend, at least for me.

What happens after Bert gets the box is easy - he replaces it, and it needs to be delivered to next person from the cycle. And we already know - it takes +1 mds at most (and nobody will open the box, because it's locked with a unique key). And so on, until Carl gets the box back and whole cycle is satisfied.

• If agent 001 got a usual box returned, he just sends the usual box. You can see for yourself, that the strategy will work just as fast.

Phase (7) Conclusion

Almost done. No, actually - done. mds = 13+9 is 220, we know for sure, that after 220 transmissions we'll get the data to everyone. Almost seems like a cheap trick to me. But why stop there?

221 transmissions are enough to stop. The one, who gets ds=22 may realise, that all is done and stop resending black box for eternity. 230 transmissions are enough to inform the 001 of success -- same stuff, but 001 stops resending after his ds is 22.

Also I'm 99% sure there are more tricks to make better solutions. Just looking "outside the box" (pun intended), I managed to find three completely perverted ideas to improve the answer. There must be more.

Cheers.

Answer 2

Before you read on, know the answer is made with the following assumptions:

• pre-arranged planning only involves strategy talk, no handing out/exchanging locks or keys.
• no writings are to be made on the outside of the box sent around, nor messages taped to the side.
• the lock that is to be on the box when the message is sent, is assumed to be required to be in locked state.
• the 'box transfer count' isn't visible, but held by the agency that does the box transportation.

First attempt: (establishing upper boundary)

Person A adds lock A, sends to person B. (1 move) B receives, adds lock B. We know that 9 more moves are needed to ensure everyone has received it at least once.

Now if we want to ensure B can read it, it needs to pass by person A to remove the lock, and end up with B again. Worst case A is the last person to go from 'received once' to 'received twice', and B is the last person in the third cycle to receive it, open, and read the message.

So one person knowing it requires 0 moves (the one locking it in), two people requires a maximum of 29 moves. (no move required from 'nobody' to 'agent A', as pointed out by Gordon K in comments).

For each additional person, the same cycle is required: Locking it with lock B, sending it to a person C who adds lock C, cycling back to person B to remove lock B, and then end up with C again who can read the message. Given there now is a return action to the first agent in a new cycle, a cycle consists of 30 moves.

Given the principle is the same, we end up at 0 + 29 + 8x30 = 269 moves for 10 people to know the contents.

Now to elaborate on a few of the 'mechanisms':
1. Once an agent has added his lock, on the next delivery with two locks he removes his own lock. After that he only passes the box onwards without further action
2. How do you know there's a full cycle completed? Well, here come the different sized boxes into play. Each time one of the recipients has learnt the contents and he passes it on, he changes the box size. If you see a new box appear for the first time, with a single lock on it, you can consider yourself the next to learn the contents and add a second lock. All others will first see it pass with TWO locks on it, and know the new box isn't for them yet. This also means that knowing this, they will not get tempted to consider themselves the new recipient if that box passes a second time with a single lock on it, untill the box size changes again. By the number of box size changes, all of them know how many people know the contents already.

I'll try and see if any mechanisms could work to reduce upper boundary, which as it is, is a rather negative outlook.

Answer 3

270 transmissions

This answer builds on the algorithm f" mentioned in his comment to the question. While this answer is similar to that by Tim Couwelier, the main difference is simplicity: no boxes are used other than the delivery box, and protocol state is determined by the number of times an agent receives the box. This answer allows (but does not rely on) the assumption that "the" delivery box in the question is a single, fixed box that cannot be substituted for any other box.

The counting mechanism requires every agent to handle the box exactly once before getting the box again. Agents count the number of times they receive the box and follow the protocol, then pass the box on. If no protocol is specified for that agent, the box is just passed on.

The process starts after agent 001 puts the message into the box, locks it and sends it off. Agent 001 is designated 00X initially.

Protocol for each agent:

1. If there is 1 lock on the box and you haven't read the message yet, add your own lock. The box ends this round with 2 locks.

2. Agent 00X: remove your lock; you are no longer designated 00X. The box ends this round with 1 lock.

3. If the lock remaining on the box is yours: remove it and read the message, then re-lock the box; you are now designated 00X. The box ends this round with 1 lock.

For all agents to read the message, the protocol runs 9 times with 10 transmissions per round. Total number of transmissions is therefore 9x10x3 = 270.

---

As an aside, there is an interesting pair of properties for this algorithm:

• each person's locking and subsequent unlocking have to occur in different rounds due to the delivery box's counting mechanism, so cycling through completely back to the same state (e.g. 1 to 2 to 3 to 1) must occupy at least 2 rounds; but

• any pair of consecutive states (1 to 2, 2 to 3, 3 to 1) can conceivably be optimised to a single round, given a suitably cooperative order of delivery.

Answer 4

Here's a more efficient solution that I think should work in practice, but maybe not fit for the puzzle.

Agent 000 sends a box with lock L0 on it. Agent 001, that receives it, puts his lock L1 on L0, agent 002 puts his lock L2 on L1, and so on, forming a chain of 10 locks when agent 009 sends it.
Here we wait for agent 000 to receive back the box, could take up to transmission 20...
Now agent 000 unlocks L0, and create a circle of locks that he uses as a "masterlock" to lock the box containing the message, and broadcasts it. The point of the masterlock is that anybody that has a key to one of the 10 locks can unlock it by opening the relevant lock.
Each of the agents now receive the box, unlocks the masterlock and read the message before broadcasting it, and by round 30, everybody read it.

Now this might not be applicable in all scenarios described because

it might not be possible to use the masterlock created as a lock.

However, there is nothing describing that we can't do that.

Answer 5

A solution in worst-case 200 transmissions, best-case 92, and typical-case around 150ish.

Step 1, Distribution: Agent #1 sends out 10 boxes (all at once), all with his own lock and the secret information inside. Each agent receives a box (agent #1 discards the one they get back). I'm going to call whichever box agent N received "their" box, or "box N".

10 worst-case transmissions total (10 best-case also)

Step 2, Permutation: Agent 2 (by pre-agreement) puts one additional lock on their own box, and sends it out. Note that even if they send it "too early", it will still be queued up behind the original 10 packages from Step 1. Agent 2 will resend the next box they receive, and Agent 1 will resend any box until they receive one with 10 padlocks. All other agents know that the second time they receive a box (i.e. when they receive a box during this step), they add n additional padlocks to their own box and send it, where n is the number of padlocks on the box they received.

I am now going to relabel all agents (except #1) by the number of padlocks on the box they sent in step 2 (which is one more than the number of padlocks they added). Note that agent 2 is already correctly labelled. Each agent N > 2 is holding on to box N-1, and box #10 is being sent around.

20 worst-case transmissions total (19 in the unlikely best-case that #1 was the last to receive this round)

Step 3, Unwinding: Agent 1, upon receiving a box with 10 padlocks, will remove their own padlock from the box and resend it. From now on, whenever agent 1 receives a box, they remove their own padlock from it if that padlock is on it, and in either case resend the box. All other agents resend every box they receive, unless it is their own box with only their own padlocks on it. In that case, they unlock it, read the information, and send the other box which they are holding.

Following these rules, what happens? Well, in at most 10 additional transmissions, agent #1 receives box #10, unlocks their padlock from it, and sends it. In at most 10 additional transmissions, agent #10 receives their box back, reads the information in it, and sends box #9. In at most 10 transmissions, agent #1 receives box #9, unlocks their padlock from it, and sends it. And so on, down to agent #2 receiving their own box, unlocking it, reading it, and the process finishes.

Analysis:

This takes worst case 9 * 2 * 10 = 180 transmissions, for 200 worst-case transmissions total.

In the best case, agent 1 receives box #10 on the 20th transmission (effectively skipping a whole round). On the 21st transmission agent 10 receives the unlockable #10, and sends #9. On the 22nd transmission, agent #1 receives box #9, and on the 23rd transmission agent #9 receives the unlockable box #9. We then need to wait until at least transmission 31 for agent 1 to receive box #8, 41 to receive #7 and so on down to 91 to receive box #2. Agent #2 can then receive their own box back as early as transmission 92.

For the typical case, steps 1 and 2 will take 20 transmissions. Agent #1 will receive box n before agent n half the time for an averave of 13.5 sets of 10 transmissions in step 3, with the final round also finishing in 5 rather than 10 transmissions on average giving a typical case total of around 150. It's slightly more because the last round might be a "short" round (one where #1 receives #2's box in time for #2 to get it back the same round) in which case it will be more than 5 transmissions on average before both those things can occur. But it's slightly less because of the potential shortcut in Step 2, so I'll stick with saying 150 typical case.

The solution might work without the multiple-lock shenanigans in step 2, but I think without them there's a corner-case risk of Agent 1 sending "box 10" and at best missing the shortcut and at worst possibly totally sending things into a spin.

Answer 6

Minium trans 171

NOTE :
1. + sign shows that a new lock is added by respective agent
for example at first + sign agent 002 will add its LOCK 02 and at second + sign agent 003 will add its LOCK 03
2. - sign shows that a lock has been removed by agent 001

This flow is for minimun deliveries unless it would take 400 trans.
3. sequence of trans left -> right
4. In each step trans starts from agent 001

Following table shows the trans sequence for minimum deliveries.

-------------------------------Agents-----------------------------------------
001     002     003     004     005     006     007     008     009      010
STEP-1-------------------------SIZE 02----------------------------------------
        [01+]##at this point agent 002 will add its LOCK 02##
[01-,02]##at this point agent 001 removes its lock and forward the box##
                [02]    [02]    [02]    [02]    [02]    [02]    [02]    [02]
        [02]
[02*]##at this point agent 001 will keep the box knowing that agent 002 received the message##
STEP-2-------------------------SIZE 03----------------------------------------
                [01+]
                        [01,03] [01,03] [01,03] [01,03] [01,03] [01,03] [01,03]
[01-,03]##at this point agent 001 will remove its LOCK 01##
                [03]
        [03]            [03]    [03]    [03]    [03]    [03]    [03]    [03]
[03*]
STEP-3-------------------------SIZE 04----------------------------------------
                        [01+]
        [01,04] [01,04]         [01,04] [01,04] [01,04] [01,04] [01,04] [01,04]
[01-,04]
                        [04]
        [04]    [04]            [04]    [04]    [04]    [04]    [04]    [04]
[04*]
STEP-4-------------------------SIZE 05----------------------------------------
                                [01+]
        [01,05] [01,05] [01,05]         [01,05] [01,05] [01,05] [01,05] [01,05]
[01-,05]
                                [05]
        [05]    [05]    [05]            [05]    [05]    [05]    [05]    [05]    
[05*]
STEP-5-------------------------SIZE 06----------------------------------------
                                        [01+]
        [01,06] [01,06] [01,06] [01,06]         [01,06] [01,06] [01,06] [01,06]
[01-,06]
                                        [06]
        [06]    [06]    [06]    [06]            [06]    [06]    [06]    [06]    
[06*]
STEP-6-------------------------SIZE 07----------------------------------------
                                                [01+]
        [01,07] [01,07] [01,07] [01,07] [01,07]         [01,07] [01,07] [01,07]
[01-,07]
                                                [07]
        [07]    [07]    [07]    [07]    [07]            [07]    [07]    [07]
[07*]
STEP-7-------------------------SIZE 08----------------------------------------
                                                        [01+]
        [01,08] [01,08] [01,08] [01,08] [01,08] [01,08]         [01,08] [01,08]
[01-,08]
                                                        [08]
        [08]    [08]    [08]    [08]    [08]    [08]            [08]    [08]    
[08*]
STEP-8-------------------------SIZE 09----------------------------------------
                                                                [01+]
        [01,09] [01,09] [01,09] [01,09] [01,09] [01,09] [01,09]         [01,09]
[01-,09]
                                                                [09]
        [09]    [09]    [09]    [09]    [09]    [09]    [09]            [09]
[09*]
STEP-9-------------------------SIZE 10----------------------------------------
                                                                        [01+]
        [01,10] [01,10] [01,10] [01,10] [01,10] [01,10] [01,10] [01,10]
[01-,10]
                                                                        [10]
        [10]    [10]    [10]    [10]    [10]    [10]    [10]    [10]
[10*]
-------------------------------------------------------------------------------

At step 1 agent 001 will send a box with SIZE 2, LOCK 01 and is received by agent 002 (for minimum trans required it should be received by agent 002 first) Agent 002 adds its lock and send the box with SIZE 2, LOCK 01,02 and is received by agent 001 and agent 001 removes it's lock (for minimum trans required it should be received by agent 001) Agent 001 send the box with SIZE 2, LOCK 02 and is received by agent 003, 004, 005, 006, 007, 008, 009, 010 and finaly by agent 002

Now agent 002 removes it's lock finds the message, locks it again and send it and is received by agent 001 as agent 001 receives the box with SIZE 2, LOCK 02, agent 001 will know that message is received by agent 002 and agent 001 will keep the box

at this point agent with deliveries (001=>2, 002=>2, 003=>1, 004=>1, 005=>1, 006=>1, 007=>1, 008=>1, 009=>1, 010=>1) as you can see here 12 trans took place in step 1

Now in step 2 agent 001 will send a new box with SIZE 3, LOCK 01 and is received by agent 003 (for minimum trans required) Agent 003 adds its lock and send the box with SIZE 3, LOCK 01,03 and is received by agent 004, 005, 006, 007, 008, 009, 010 and finaly by agent 001 and agent 001 removes it's lock Agent 001 send the box with SIZE 3, LOCK 03 and is received by agent 003 Now agent 003 removes it's lock finds the message, locks it again and send it and is received by agent 004, 005, 006, 007, 008, 009, 010, 002 and finaly by agent 001 as agent 001 receives the box with SIZE 3, LOCK 03, agent 001 will know that message is received by agent 003 and agent 001 will keep the box

at this point agent with deliveries (001=>4, 002=>3, 003=>3, 004=>3, 005=>3, 006=>3, 007=>3, 008=>3, 009=>3, 010=>3) as you can see here 19 trans took place in step 1

and so on as shown in table after step 2 each step will take 20 trans counting the trans it would take 7*20 + 19 + 12 = 171

minium trans to inform all agents will be 171

That's all I could think of, let's see if am I close to cheapest solution.

Answer 7

I have 3 solutions(this question stole my lunch break)...

Zeroth solution:

Assume that you can put a padlock on a box and keep it unlocked, but for the box to be mailed it needs atleast one lock, locked. Also assume that each agent has a unique number identity. Then consider that only one box will be used, and 10 locks. Then it would take at worse case 110 iterations. Agent 01 put 1 locked padlock on the box and 9 unlocked padlocks on the box and ship it out. As it goes out each agent would replace the x numbered lock with an unlocked padlock of theirs. For example Agent 03 would replace padlock number three with his own padlock. In worse case it would take 20 iterations to make it through every agent so every agent is able to replace the lock and for the box to return to agent 01. After it comes back to Agent 01 and he sees the first padlock is locked and the other 9 are unlocked, he unlocks padlock 01, and locks padlock 02 and ships it out. At worst case it would take 10 iterations to get to Agent 02, who unlocks padlock 2, reads the note, and locks padlock 3 and ships the box out. Again worst case for Agent 03. Rinse and repeat until Agent 10. So worst case: 20 + (10 x 9 ) = 110 iterations.

Fist solution:

Assume: That during the prearrangement period they can trade padlocks. That during the prearrangement they mark themselves as agent 01 to agent 10. And finally the kicker: Agent 01 receives 2 padlocks from Agent 02, 3 padlocks from Agent 03... and so on and so forth until 10 padlocks from Agent 10. (All of them are unlocked)

---

Then it would only take 90 iterations at worse case.

---

Agent 01 takes the message, 3 padlocks from agent 03, 4 padlocks from agent 04... etc. and puts it inside a box. He then uses 2 of Agent 02 padlocks to lock the box. Sends it out. Worse case it would take 10 iterations until Agent 02 receives the box. Agent 02 then unlocks the box, reads the message, takes out Agent 03's 3 padlocks, puts message back in box(along with the other padlocks) and uses Agent 03's padlocks. The agent then sends out the box again, and like before hand it will take 10 iterations to get to Agent 03.So... 10 iterations for Agent 02 + 10 for Agent 03 + ... + 10 for Agent 10 = 90.

---

Second Solution

Assume: All the assumptions of the first solution. Each agent receives 10 padlock from Agent 01, 20 padlocks from Agent 02, 30 padlocks from Agent 03... and so on and so forth until 100 padlocks from Agent 10. In the instructions it says"secret mailing system that sends one box at a time, but it is now spoilt", and that by spoilt it meant that now you can send more than one box at a time.

---

Agent 01 makes 11 photocopies of the message, and then puts 10 of them into 10 boxes and lock each box with 2 padlocks. Then sends out all 10 boxes simultaneously(because since the mailing system is spoilt it is not limited to one box at a time). Sending it out 10 simultaneously makes sure that every Agent receives a box. Agent 2 unlocks the box, makes 9 photocopies and put each into a box, and put 3 padlocks of agent 03 onto each box. And you can probably guess where this is going. So all in all it would only take 10 iterations.

Answer 8

The question asks:

What is the minimum number of passes it will take before he can guarantee that everyone has received it (or a copy of it)?

---

Agent A puts a copy of the message in the box and sends it away. It will go to a random agent since all have 0 deliveries. It may return to A or another agent at random. I suppose that we will count this for 2 passes to guarantee it goes to another agent. When another agent receives it he adds his lock, we will call this agent B, and sends it back. A will not be guaranteed to see it again until it has been past all 8 other agents, then a random chance again. This will take an additional 18 passes to guarantee that A sees it again to remove his lock before sending it away. Since in the worst case all agents have the same number of deliveries again we count another 2+8 passes to guarantee that B has the box and can remove his lock to make a copy of the message befoer locking it again and sending it away. B is now A. 3 passes are the minimum to guarantee another agent we will call C receives the box and adds his lock, and another 7+10 to ensure the new A receives it to remove his. We have established that in each cycle there are 30 moves. Apart from the original A, 9 additional agents need a copy of the message. 9 cycles x 30 moves to make the guarantee is 270 cycles in order to guarantee that all 10 agents have a copy of the message.

Answer 9

So here is my attempt at:

Step 1

Agent 1 Gets 9 boxes with secret message and adds a lock to each and sends them all out If an agent gets two or more boxes they keep one and send the others on

Step 2

Agents 2 - 10 add one lock to one box and Agent 1 - sends out one large unlocked box - nothing inside so nothing to be stolen.

Step 3

Agents 2 - 10 add their boxes to the unlocked box. As each smaller boxes are locked nothing can be stolen.

Step 4

When Agent 1 gets the large box back he unpacks it takes his locks off and sends the small boxes back out.

Step 4a

Agent 1 unpacks the large box takes his lock off, repacks the large box and send is back out.

Transmission Count

This is where my maths may let me down. I calculate step 1 would be a max of 54 transmissions (depending on how the delivery count works). I think the worse case scenario is Agent 1 gets all 9 boxes then agent 2 gets all 9 boxes but keeps 1, so and so forth. The large box would go round each agent once so 10 transmissions. Then another 10 to guarantee it comes back to agent 1. Each small box then needs to be sent out but this is the worst part of the solution, each box could go to every agent, 9 boxes and 10 agents would be 90 transmissions. This totals 164 transmissions. The step 4a, the large box would go out 10 times reducing the transmissions.

Unknowns

Points I was not clear on. What delivery order would take precedent when the smaller boxes are in the large box, though not sure it would matter. When the first 9 boxes are sent do they take into the delivery count of each other. In theory all delivery counts are 0 so all agents could get 1 box, decreasing the total delivery count to 120 (i think). Or do all boxes check at the same time and then randomly decide which agent to go to at the same time?

Possibly

So depending on how the rules are implemented I think this could come down to 30 transmissions. If in step 1 the delivery count is calculated one box at a time.