Author |
Topic: Stamps and envelopes (Read 2408 times) |
|
Altamira_64
Junior Member
Posts: 116
|
 |
Stamps and envelopes
« on: Jan 2nd, 2016, 7:10am » |
 Quote  Modify
|
We have 14 different lots of stamps, each lot from a different country (all stamps of each lot are the same) and an adequate number of envelopes.
We must place exactly 4 different stamps on each envelope. What is the maximum number of envelopes we can make, provided that any two envelopes must not have more than one stamp in common?
|
| « Last Edit: Jan 3rd, 2016, 7:18am by Altamira_64 » |
 IP Logged |
|
|
|
markr
Junior Member
Gender: 
Posts: 90
|
|
Re: Stamps and envelopes
« Reply #1 on: Jan 3rd, 2016, 11:43am » |
Quote Modify
|
Each lot can go on at most floor((14-1)/3) = 4 envelopes. With 13 lots, you can get to the theoretical maximum 13 envelopes. I'm not sure that an extra lot allows you to get to a 14th envelope. I'm guessing not.
|
|
IP Logged |
|
|
|
Altamira_64
Junior Member
Posts: 116
|
|
Re: Stamps and envelopes
« Reply #2 on: Jan 7th, 2016, 12:36pm » |
Quote Modify
|
the stamps from each lot can be used multiple times.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Stamps and envelopes
« Reply #3 on: Jan 8th, 2016, 1:15pm » |
Quote Modify
|
on Jan 7th, 2016, 12:36pm, Altamira_64 wrote:| the stamps from each lot can be used multiple times. |
|
That doesn't seem relevant to markr's post.
Label the stamp lots A-N for convenience of reference.
Every time you use an A stamp, it has to go with 3 different stamps - so you can put ABCD, AEFG, AHIJ, AKLM, but then you can't use A again because with only N that it hasn't been used with, there aren't enough new lots of stamps to go with it.
That means each stamp lot can be used at most 4 times (with 12 of the other 13 lots) so the maximum possible number of envelopes is 14 lots times 4 stamps per lot, divided by 4 stamps per envelope for a total of 14 as the upper bound.
13 envelopes is achievable (and can be achieved only using 13 lots), which gives a lower bound, so the open question is whether you can actually get the 14th envelope or not.
My intuition returns a solid "maybe".
|
|
IP Logged |
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Stamps and envelopes
« Reply #4 on: May 3rd, 2016, 11:45pm » |
Quote Modify
|
Solution for 13, in case it is useful for other solvers:
ABCD
AEFG
AHIJ
AKLM
BEHK
BFIL
BGJM
CEIM
CFJK
CGHL
DEJL
DGIK
DFHM
|
|
IP Logged |
|
|
|
Altamira_64
Junior Member
Posts: 116
|
|
Re: Stamps and envelopes
« Reply #5 on: May 12th, 2016, 12:40am » |
Quote Modify
|
Solution with 14:
ACFG
BDGH
CEHI
DFIJ
EGJK
FHKL
GILM
HJMN
IKNA
JLAB
KMBC
LNCD
MADE
NBEF
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print