|
||
Title: Stamps and envelopes Post by Altamira_64 on Jan 2nd, 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 3rd, 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 7th, 2016, 12:36pm the stamps from each lot can be used multiple times. |
||
Title: Re: Stamps and envelopes Post by rmsgrey on Jan 8th, 2016, 1:15pm on 01/07/16 at 12:36:25, Altamira_64 wrote:
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 3rd, 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 12th, 2016, 12:40am Solution with 14: ACFG BDGH CEHI DFIJ EGJK FHKL GILM HJMN IKNA JLAB KMBC LNCD MADE NBEF |
||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |