Author |
Topic: Odd memo distribution (Read 4189 times) |
|
Mike_V
Junior Member
Gender: 
Posts: 60
|
 |
Odd memo distribution
« on: Oct 5th, 2003, 11:25pm » |
 Quote  Modify
|
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 non-brute-force 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.)
|
|
 IP Logged |
Don't specify the unspecified.
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Odd memo distribution
« Reply #1 on: Oct 7th, 2003, 7:57am » |
Quote Modify
|
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 messy--we are talking about some very big numbers here.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Odd memo distribution
« Reply #2 on: Oct 7th, 2003, 12:07pm » |
Quote Modify
|
1) 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.
What really amazed me, that this beautiful puzzle has a tight relation to this one. 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! 
Where are you, visitor?!
|
| « Last Edit: Oct 7th, 2003, 12:08pm by Barukh » |
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Odd memo distribution
« Reply #3 on: Oct 7th, 2003, 12:24pm » |
Quote Modify
|
That is not the only way of doing it. Take all mailboxes where both digits are even, or both digits are odd. 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 memo-to-mailbox choices.
But still no progress on the second part 
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Mike_V
Junior Member
Gender:
Posts: 60
|
|
Re: Odd memo distribution
« Reply #4 on: Oct 7th, 2003, 1:49pm » |
Quote Modify
|
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: You don't need all the memos. For example, to prove that there are always at least 10 non-empty mailboxes, you only need 10 distinct memos.
Hint 2: 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?
|
|
IP Logged |
Don't specify the unspecified.
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Odd memo distribution
« Reply #5 on: Oct 7th, 2003, 1:53pm » |
Quote Modify
|
on Oct 7th, 2003, 1:49pm, Mike_V wrote:| James, I'm curious where the number 126 came from. |
|
It seems like both Barukh and I have 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.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Odd memo distribution
« Reply #6 on: Oct 8th, 2003, 12:14pm » |
Quote Modify
|
on Oct 7th, 2003, 1:49pm, Mike_V wrote:| Barukh, that is indeed intriguing. Though, I think I may be having issues relating the two as closely as you mean. |
|
What I meant is the following: Call the distribution of memos to mailboxes optimal if it leaves as many empty mailboxes as possible. Denote SM the set of non-empty mailboxes in an optimal distribution.
Now, consider the controlling placement of rooks in a 3-dimensional 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 SR the set of numbers XY of the fields occupied by the rooks in an optimal placement.
Then, for every optimal distribution SM there is an optimal placement SR = SM, 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 Z-coordinates of the rooks - proposed by Visitor):
-9-7-5-3-1 | 9 (Y)
8-6-4-2-0- | 8
-7-5-3-1-9 | 7
6-4-2-0-8- | 6
-5-3-1-9-7 | 5
4-2-0-8-6- | 4
-3-1-9-7-5 | 3
2-0-8-6-4- | 2
-1-9-7-5-3 | 1
0-8-6-4-2- | 0
=========+
0123456789 (X)
|
| « Last Edit: Oct 8th, 2003, 12:16pm by Barukh » |
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Odd memo distribution
« Reply #7 on: Oct 8th, 2003, 1:25pm » |
Quote Modify
|
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?
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Odd memo distribution
« Reply #8 on: Oct 9th, 2003, 1:13pm » |
Quote Modify
|
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 50-mailbox solutions, then you can generate a rook solution to match the memo solution fairly easily. But for a general mailbox-memo 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.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
visitor
Guest
|
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 044-049, 054-059, 064-069... 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.
|
|
IP Logged |
|
|
|
visitor
Guest
|
|
Re: Odd memo distribution
« Reply #10 on: Oct 10th, 2003, 5:54am » |
Quote Modify
 Remove
|
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.
|
|
IP Logged |
|
|
|
visitor
Guest
|
|
Re: Odd memo distribution
« Reply #11 on: Oct 10th, 2003, 6:13am » |
Quote Modify
Remove
|
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 001-004. They will handle all mail beginning with 2 0's except 0055-0059, 0065-0069... Total of 25 which must all be handled specifically by mailboxes 055-059, 065-069... 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.
|
|
IP Logged |
|
|
|
visitor
Guest
|
|
Re: Odd memo distribution
« Reply #12 on: Oct 10th, 2003, 7:10am » |
Quote Modify
Remove
|
This is turning into a monologue. But that higher dimension proof may not be self-evident or complete. (It might give the impression that you only need 111-555 filled and 666-999 filled--or 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 3-dimensional chessboard or one 2-digit 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.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Odd memo distribution
« Reply #13 on: Oct 10th, 2003, 8:56am » |
Quote Modify
|
on Oct 8th, 2003, 1:25pm, James Fingas wrote:| 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? |
|
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 Z-coordinates of the rooks. In fact, any two Z-layers may be switched to give another optimal placement. I beleive the opposite is also true: for a given optimal placement there are many memos-to-mailboxes distributions.
What I still claim that there is a one-to-one correspondence between the mailboxes and the rooks in optimal configurations. And so proving the optimality for one will prove it for another.
on Oct 9th, 2003, 1:13pm, James Fingas wrote:| ...I have demonstrated to myself that both the mailbox/memo problem and the chess problem need at least 40 mailboxes/rooks... |
|
The fact that the lower bounds are the same in two problems also implicitly supports my thesis.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Odd memo distribution
« Reply #14 on: Oct 10th, 2003, 12:11pm » |
Quote Modify
|
on Oct 10th, 2003, 7:10am, visitor wrote:| This is turning into a monologue. |
|
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?
|
|
IP Logged |
|
|
|
Mike_V
Junior Member
Gender:
Posts: 60
|
|
Re: Odd memo distribution
« Reply #15 on: Oct 10th, 2003, 4:56pm » |
Quote Modify
|
I too am not able to follow your proof.
on Oct 10th, 2003, 5:54am, visitor wrote:| 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. |
|
That's where I lose you.
|
|
IP Logged |
Don't specify the unspecified.
|
|
|
visitor
Guest
|
|
Re: Odd memo distribution
« Reply #16 on: Oct 10th, 2003, 6:19pm » |
Quote Modify
Remove
|
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 (044-049, 054-059...). 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 xy0-xy3, 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 2-digit 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 non-overlapping boxes as possible.
I need to take a break.
|
|
IP Logged |
|
|
|
Mike_V
Junior Member
Gender:
Posts: 60
|
|
Re: Odd memo distribution
« Reply #17 on: Nov 30th, 2005, 2:19pm » |
Quote Modify
|
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:
| hidden: |
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 S-memo 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 S-memos.
|
Perhaps that's enough, if not, here's the claim:
| hidden: |
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*(n-1) boxes are needed for all optimistic S-memos.
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.
|
Can you prove that? If not, read on.
| hidden: |
By induction on n. First, it's trivially true for n=1 (no opt. S-memos for |S|=2). So assume true for n-1.
Now choose any set S with |S| = 2n and let a be the smallest element of this set.
Now, let c be the largest1 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. S-memo 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.
1Assuming 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'| = 2n-2, the induction assumption states that the opt. S' memos (which are also opt. S-memos) need at least (n-1)*(n-2) boxes.
Since the first 2n-2 boxes all have a or c in them, and none of the second (n-1)*(n-2) boxes have either, they are disjoint. Thus we need at least (n-1)*(n-2) + 2n - 2 = n*(n-1) boxes for all opt. S-memos.
|
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. S-squares 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.
|
|
IP Logged |
Don't specify the unspecified.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Odd memo distribution
« Reply #18 on: Nov 30th, 2005, 8:23pm » |
Quote Modify
|
on Nov 30th, 2005, 2:19pm, Mike_V wrote:| 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? |
|
No - I've just been too lazy to update it in quite a while.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print