

Title: Odd memo distribution Post by Mike_V on Oct 5^{th}, 2003, 11:25pm Your boss hands you 1000 memos and says to place them in employees' mailboxes. "But," you say, "there's only 100 people working here, including myself, why so many memos?" "I want to be sure that each employee gets one." "Oh." "In fact, since I don't really trust you, and because I like to make things unreasonably confusing, I've come up with a system that you must follow." "I hate you." "I've labeled each memo with a number: 000,001...,999. And, as you know, each mailbox has a number on it: 00,01,...,99. So to be absolutely sure that everyone gets a memo, a memo numbered ABC can only be put in mailbox AB, BC, or AC." "Got it. I hate you." "And you must distribute all of the memos." (The first is medium, but I think the 2nd two fit in the hard category.) 1) Pissed off, you're determined to show how stupid your boss is. Find a distribution where at least half the mailboxes are empty. (Even if you can't get the rest, give a second thought to this part.) 2) So now prove that this is the most you can annoy your boss. That is, that in any distribution at most half the mailboxes are empty. (I haven't attempted the last, so I'm not positive there's a nonbruteforce method, though I tend to believe there is.) 3) How many possible distributions are there in which exactly N mailboxes are empty? (So knowing this you can determine how good your boss's plan was. How likely it would be that N boxes would have been empty if you just filled them randomly according to his rule.) 

Title: Re: Odd memo distribution Post by James Fingas on Oct 7^{th}, 2003, 7:57am Happy to say I was able to solve the first part, but it hasn't provided any insight into the second part. The third part looks very very messywe are talking about some very big numbers here. 

Title: Re: Odd memo distribution Post by Barukh on Oct 7^{th}, 2003, 12:07pm 1) [hide] Take all the mailbox numbers that have both digits less than 5, or greater than 4. There are exactly 50 such numbers. Then, every memo can be mapped to at least one such number. [/hide] What really amazed me, that this beautiful puzzle has a tight relation to this one (http://www.ocf.berkeley.edu/~wwu/cgibin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1064517916). It means that after we know the answer to the part 2), we will have also the missing proof in the twin puzzle. Thanks, Mike_V! :D Where are you, visitor?! 

Title: Re: Odd memo distribution Post by James Fingas on Oct 7^{th}, 2003, 12:24pm That is not the only way of doing it. [hide]Take all mailboxes where both digits are even, or both digits are odd.[/hide] This suggests that there are a large number of ways of solving the problem. In fact, I'd say that there are 126 ways of solving the problem in this manner, and in all of them, there are a significant number of arbitrary memotomailbox choices. But still no progress on the second part :( 

Title: Re: Odd memo distribution Post by Mike_V on Oct 7^{th}, 2003, 1:49pm Barukh, that is indeed intriguing. Though, I think I may be having issues relating the two as closely as you mean. James, I'm curious where the number 126 came from. As for part 2. Hint: [hide]You don't need all the memos. For example, to prove that there are always at least 10 nonempty mailboxes, you only need 10 distinct memos.[/hide] Hint 2: [hide]For any one memo you need at least one mailbox. But what about for any two? What about for the set of memos whose numbers consist only of certain digits?[/hide] 

Title: Re: Odd memo distribution Post by James Fingas on Oct 7^{th}, 2003, 1:53pm on 10/07/03 at 13:49:07, Mike_V wrote:
It seems like both Barukh and I have [hide]partitioned the digits into two sets of five digits each. We fill all mailboxes such that both digits are from the same set. It is easy to show that all memos can be assigned to at least one mailbox this way, and that exactly 50 mailboxes are therefore filled. 126 = (10 choose 5)/2.[/hide] 

Title: Re: Odd memo distribution Post by Barukh on Oct 8^{th}, 2003, 12:14pm on 10/07/03 at 13:49:07, Mike_V wrote:
What I meant is the following: [hide]Call the distribution of memos to mailboxes optimal if it leaves as many empty mailboxes as possible. Denote S_{M} the set of nonempty mailboxes in an optimal distribution. Now, consider the controlling placement of rooks in a 3dimensional cube 10x10x10. Assign to every field in the cube a number XYZ, according to its coordinates 0 [le] X, Y, Z [le] 9. Call the placement with minimal number of rooks optimal. Denote S_{R} the set of numbers XY of the fields occupied by the rooks in an optimal placement. Then, for every optimal distribution S_{M} there is an optimal placement S_{R} = S_{M}, and vice versa. Probably, this formulation is too messy, so I'll give an example. Here's the optimal rook placement corresponding to James's optimal distribution (the numbers specify the Zcoordinates of the rooks  proposed by Visitor): 97531  9 (Y) 86420  8 75319  7 64208  6 53197  5 42086  4 31975  3 20864  2 19753  1 08642  0 =========+ 0123456789 (X) [/hide] 

Title: Re: Odd memo distribution Post by James Fingas on Oct 8^{th}, 2003, 1:25pm That's very interesting. Seems to work as far as I can tell. How do the Z placements for the rooks come out of the memos and mailboxes? 

Title: Re: Odd memo distribution Post by James Fingas on Oct 9^{th}, 2003, 1:13pm Okay, I think I see how this relates to the rooks question, but from what I understand, I don't think a proof of optimality here will necessarily translate to a proof of optimality for the rooks question. When you fill a mailbox numbered 92, you eat up memos with numbers 92* 9*2 and *92. There are 28 such memos (because 922 and 992 are counted twice each). With the rooks question, you place a rook at location 962, and you can attack locations 96*, 9*2, and *62. There are 28 such locations (since 962 is counted three times). This may seem similar on the surface, but I think it's not functionally equivalent. When you do as Barukh and I have done to generate our 50mailbox solutions, then you can generate a rook solution to match the memo solution fairly easily. But for a general mailboxmemo solution, it may not be possible. I have demonstrated to myself that both the mailbox/memo problem and the chess problem need at least 40 mailboxes/rooks, but it seems like that number cannot be achieved (definitely not for the rooks, and it seems not for the mailboxes either). But still no proof of optimality. 

Title: Re: Odd memo distribution Post by visitor on Oct 9^{th}, 2003, 2:16pm For the beginnings of an optimal proof. Let's start with a theoretical minimum of 40 mailboxes. Suppose you fill 4 mailboxes beginning with a 0 (eg 00,01,02,03) hoping to fill no more than 40 total. Those 4 mailboxes that begin with 0 eat up all the mail beginning with a 0 except 044049, 054059, 064069... Total 36 letters. Each of those 36 letters would require the last 2 digits to be one of the remaining filled mailboxes. There are 36 fillable mailboxes left to reach our hoped for 40 minimum, so it might seem possible. That's why it's the theoretical minimum. But that's assuming no overlap. Take 4 mailboxes beginning with a 4, to avoid overlap (44,45,46,47), now you can take 2 beginning with an 8 (88,89). And you're out of room. Every box you choose from now on will have to overlap one of those first 10 boxes. By the time you've chosen 10 mailboxes to fill, all the remaining mailboxes will have to be suboptimal with respect to one of these 10. Or, from the opposite perspective, it is those 10 mailboxes that must be suboptimal with respect to the rest of the filled boxes. You can't reduce that number without making one of those numbers doubly suboptimal. And that's why the true minimum is 10 higher than the theoretical minimum of 40. 

Title: Re: Odd memo distribution Post by visitor on Oct 10^{th}, 2003, 5:54am I'm not sure that actually proved it, but the proof follows: if any starting digit has only 4 chosen mailboxes, you will need 36 specific mailboxes to carry the rest of the letters beginning with that digit. But those 36 have no digit in common with these 4 boxes, so, for the same reason, they will need 16 specific mailboxes to handle the mail they can't. So if there is even a single starting digit has less than 5 mailboxes, the minimum solution would have to be 52. 

Title: Re: Odd memo distribution Post by visitor on Oct 10^{th}, 2003, 6:13am That proof would seem to expand very nicely to give us the missing proof for all the higher dimensions of the rook problem as well. Take 3 digit mailboxes and 4 digit letters. Fill in boxes 001004. They will handle all mail beginning with 2 0's except 00550059, 00650069... Total of 25 which must all be handled specifically by mailboxes 055059, 065069... And those 25, since they have nothing but the first 0 in common with the boxes you chose first, must be handled specifically by all 25 of the low order set. Apply the same argument to every starting digit, and to every additional dimension, and you'll see that we can never get away with less than 1/2 of the boxes being filled. 

Title: Re: Odd memo distribution Post by visitor on Oct 10^{th}, 2003, 7:10am This is turning into a monologue. But that higher dimension proof may not be selfevident or complete. (It might give the impression that you only need 111555 filled and 666999 filledor 250 out of a thousand). No (because that would not handle mail that has 2 low digits and 2 high), the point is that, add all the extra digits you want, all the dimensions you want, you can always slice out and examine one 3dimensional chessboard or one 2digit set of mailboxes (chosen from any dimension you wish), and that puzzle's solution is unaffected by the existence of other numbers and dimensions that are not being considered. In the mailbox puzzle, since the number of mailboxes is always one digit less than the number of letters, any digit is never affected by anything but the digit to the left of it or the digit to the right, and not both at the same time. It must always use half of its digits. 

Title: Re: Odd memo distribution Post by Barukh on Oct 10^{th}, 2003, 8:56am on 10/08/03 at 13:25:12, James Fingas wrote:
James, sorry for the delay (local server was down last night :/)  so I'll answer both posts. I don't think there is a unique way to determine Zcoordinates of the rooks. In fact, any two Zlayers may be switched to give another optimal placement. I beleive the opposite is also true: for a given optimal placement there are many memostomailboxes distributions. What I still claim that there is a onetoone correspondence between the mailboxes and the rooks in optimal configurations. And so proving the optimality for one will prove it for another. on 10/09/03 at 13:13:38, James Fingas wrote:
The fact that the lower bounds are the same in two problems also implicitly supports my thesis. 

Title: Re: Odd memo distribution Post by Barukh on Oct 10^{th}, 2003, 12:11pm on 10/10/03 at 07:10:52, visitor wrote:
Visitor, to change it to a dialogue. I didn't understand your proof quite well; could you please elaborate  maybe, it will be more convinincing then? 

Title: Re: Odd memo distribution Post by Mike_V on Oct 10^{th}, 2003, 4:56pm I too am not able to follow your proof. on 10/10/03 at 05:54:16, visitor wrote:


Title: Re: Odd memo distribution Post by visitor on Oct 10^{th}, 2003, 6:19pm I wish I knew exactly what I was thinking (especially that last post, which now makes no sense to me at all). I’m real close to proving the original optimums, but my suggested proof for higher dimension and larger mailrooms is a flop. In the rooks problem, I first proposed a theoretical minimum, which for 10x10x10, would have been 40: 4 on level one leaves 36 squares on that level uncontrolled (a 6 by 6 square, if the 4 rooks are all placed within a 4x4 square in one corner). 4 on each of the other nine levels totals 36 rooks to spare, hence the theoretical possibility of success. But to work, you would have to have one directly above each of the 36 uncontrolled squares of level one. An uncontrolled square at coordinates 8,8 on level one can only be controlled on a different level at 8,8. But if you place all 36 remaining rooks somewhere above those spaces, you'd have no rooks in the first 4 rows or columns on any of those 9 levels. You’re leaving a 4x4 gap on each of those levels with only 4 of those 16 squares defended by the rooks from level one. You'll need another 12 rooks to control the rest of those squares for a total of 52. That’s going to be the minimum unless every level has 5 rooks. With mailboxes, I’m not sure my first post proved anything, but I was on the right track. I suggested trying to use only 4 boxes beginning with 0 (00,01,02,03). Just like with the rooks, it leaves 36 memos unboxed beginning with 0 (044049, 054059...). The only way to box memo 044 without starting with a 0 is by using box 44. But if we select all 36 boxes that way, then we still haven’t boxed memos xy0xy3, where either x or y is 1 to 3 (and the other is anything but 0). And once again this low sector will need 16 mailboxes (for 52 total). You can’t get away from that limit unless you use 5 boxes starting with every single digit. I have some ideas on measuring efficiency, but it’s not a proof: You can't place more than 10 rooks or fill more than 10 mailboxes before you start having overlap that means the remaining mailboxes will all be suboptimal. That leads to this conclusion: Any mailbox can hold 28 memos. If that's all that mattered, we could put 1000 memos in 36 mailboxes. But as soon as the first 10 boxes are chosen and filled with 28 memos each, the rest of your mailboxes will be less than full. Let’s say, you start with 00, 11, 22, 33, 44, 55, 66, 77, 88, 99. They don’t overlap at all, so you’ve swallowed up 280 memos. The next box you choose (let’s say 01) would only get 24 memos at most (because 001,010,011, and 110 are already boxed). You can fill 10 boxes att this efficiency level. After that the most efficient box left would only get 20 memos (losing 4 memos to one of the first 10 boxes and 4 memos to one of the second 10). If I’m right that this maximum efficiency drops at a constant rate it will take 50 boxes to hold 1000 memos. Now let’s say we expand it to 10,000 memos to be placed in 1,000 boxes. A full box holds 37 memos. I think you can select no more than perhaps 40 boxes with no overlap at all (because these 3 digit numbers can’t have any 2 digit number in common). The next 40 boxes (or perhaps only 30?) would hold no more than 34 memos each (each 3 digit mailbox can form 3 2digit numbers that have already occurred in one of the first 40 boxes, for 3 overlaps). I’m not sure of the exact numbers here, but again, if it’s valid to extend the drop in efficiency, it will not be possible to fit 10,000 memos in much less than 500 boxes, but I can’t prove the exact number without figuring exactly how to create as many nonoverlapping boxes as possible. I need to take a break. 

Title: Re: Odd memo distribution Post by Mike_V on Nov 30^{th}, 2005, 2:19pm Well, after spending some time away from these boards, I came back and noticed that the unsolved problems sticky hasn't been updated in quite a while. Perhaps it's being updated elsewhere? In any event, since my odd memo distribution is still there, I'm going to solve it in the interest of the 3D chessboard problem: First to get you started, a few labels: [hideb] Call a memo optimistic if it's digits are strictly increasing. Pessimistic if strictly decreasing. And constant if constant. For example, memo 125 is optimistic, memo 732 is pessimistic, 555 is constant, and 195 is none of the above. Note that these are completely disjoint sets in both memos and boxes (no optimistic memo can share a mailbox with a pessimistic or constant one). Also, for any set S, an Smemo is one for which all the digits of the memo are in S. Thus for S = {1,2,3,4}: 123, 124, 134 and 234 are all the Smemos. [/hideb] Perhaps that's enough, if not, here's the claim: [hideb] Clearly, we need 10 boxes for the constant memos. 000 MUST go in 00, 111 in 11, etc. I claim we need at least 20 boxes for the optimistic memos, and another (as I mentioned disjoint) 20 boxes for the pessimistic memos. More specifically, I claim: For all sets, S, with S = 2n, at least n*(n1) boxes are needed for all optimistic Smemos. Thus with n=5 we need 5*4 = 20. And by similarity, the same applies for the pessimistic ones, so we have 10+20+20 = 50 mailboxes at a minimum. [/hideb] Can you prove that? If not, read on. [hideb] By induction on n. First, it's trivially true for n=1 (no opt. Smemos for S=2). So assume true for n1. Now choose any set S with S = 2n and let a be the smallest element of this set. Now, let c be the largest^{1} element of S such that box ac is empty. So, for all d>c in S, ad is filled. And for all b<c in S, the opt. Smemo abc must be in either ab or bc (since ac is empty). Thus we need a unique box for each such b. So for all elements other than a and c in S, we have a mailbox = 2n  2 boxes. ^{1}Assuming there is any such c. But if not, all boxes ac for c>a in S are filled = 2n  1 boxes, which is even more than otherwise. Now, consider the set S' = S  {a,c}. Since S' = 2n2, the induction assumption states that the opt. S' memos (which are also opt. Smemos) need at least (n1)*(n2) boxes. Since the first 2n2 boxes all have a or c in them, and none of the second (n1)*(n2) boxes have either, they are disjoint. Thus we need at least (n1)*(n2) + 2n  2 = n*(n1) boxes for all opt. Smemos. [/hideb] And we're done. So now, the chess problem. Unfortunately, the same claim definitely does NOT hold: Rooks on squares 126, 134, 235, 345, and 256 cover all opt. Ssquares of the set S = {1,2,3,4,5,6}, for example. This is 5 total rooks, less than 6. Furthermore a single rook can cover both optimistic and pessimistic squares: a rook on 143 covers both 123 and 543. So even the initial setup of this problem is not terribly helpful. However, there IS significant similarity, so hopefully someone can work off the ideas of this proof to find one for the 3D chess control problem. 

Title: Re: Odd memo distribution Post by Icarus on Nov 30^{th}, 2005, 8:23pm on 11/30/05 at 14:19:20, Mike_V wrote:
No  I've just been too lazy to update it in quite a while. 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 