wu :: forums « wu :: forums - Stamps and envelopes » Welcome, Guest. Please Login or Register. Jun 14th, 2021, 6:22pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: ThudnBlunder, Grimbal, SMQ, Icarus, william wu, towr, Eigenray)    Stamps and envelopes « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Stamps and envelopes  (Read 2169 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: 2840
 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