wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Stamps and envelopes
        
(Message started by: Altamira_64 on Jan 2^nd, 2016, 7:10am)

Title: Stamps and envelopes
Post by Altamira_64 on Jan 2^nd, 2016, 7:10am

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?

Title: Re: Stamps and envelopes
Post by markr on Jan 3^rd, 2016, 11:43am

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.

Title: Re: Stamps and envelopes
Post by Altamira_64 on Jan 7^th, 2016, 12:36pm

the stamps from each lot can be used multiple times.

Title: Re: Stamps and envelopes
Post by rmsgrey on Jan 8^th, 2016, 1:15pm

on 01/07/16 at 12:36:25, 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".

Title: Re: Stamps and envelopes
Post by dudiobugtron on May 3^rd, 2016, 11:45pm

Solution for 13, in case it is useful for other solvers:
[hide]ABCD
AEFG
AHIJ
AKLM
BEHK
BFIL
BGJM
CEIM
CFJK
CGHL
DEJL
DGIK
DFHM[/hide]

Title: Re: Stamps and envelopes
Post by Altamira_64 on May 12^th, 2016, 12:40am

Solution with 14:

ACFG
BDGH
CEHI
DFIJ
EGJK
FHKL
GILM
HJMN
IKNA
JLAB
KMBC
LNCD
MADE
NBEF