9
$\begingroup$

I'm not a math guru, but I do like Christmas lights.

I am helping set up a decent sized lighting display for my work, I have measured all outlines and props to figure out how many lights we are going to need for each area.

The lights come with 100 lights/string however, we would like to cut the strings into the appropriate number of bulbs per outline/prop and put connectors on the ends so we don't have a bunch of extra bulbs at the end of props (some only need 16 bulbs on a prop and we don't want to be limited in having to daisy chain everything using lit up bulbs in the strings. We want to splice in plain wire between props.)

I realize there are other factors such as voltage drop, amperage, etc. we need to think about (I'm getting help from an electrical engineer friend for that.)

But I am trying to figure out the best way to divide the 100 bulb strings without having more cuts than I need.

I was first thinking of making the largest cuts first (say I need 56) I now have 44 bulbs on that string, but I don't think it's the most efficient to then say I need a sting of 42 so then cut 2 off when I may have needed 2 sets of 22 that would have equaled 44 and used up the remaining bulbs on that string.

Without including the full strings of 100 that I need, here are the quantities and number of bulbs per string I need... what is the best way for me to start trying to divide these up while avoiding unnecessary cuts and splices?

$$\begin{array}{rl} \text{Quantity} & \text{Bulbs Per String} \\ 8 & 10\\ 1 & 16\\ 4 & 18\\ 1 & 20\\ 4 & 22\\ 1 & 23\\ 1 & 30\\ 4 & 34\\ 34 & 36\\ 1 & 38\\ 3 & 40\\ 2 & 42\\ 1 & 44\\ 1 & 47\\ 1 & 50\\ 2 & 51\\ 3 & 52\\ 4 & 54\\ 2 & 56\\ 1 & 58\\ 1 & 60\\ 1 & 76\\ 4 & 77\\ 1 & 78\\ 2 & 79\\ 3 & 80\\ 4 & 81\\ 2 & 96\\ 8 & 99\\ \end{array}$$

$\endgroup$
4
$\begingroup$

So you need a total of $4,944$ lamps, which means at least $50$ strings.

It would be a hard task also for a computer to proceed "brute-force" and check all possible combinations.

So I can suggest you just to proceed by "wise judgement" in a sort of a "greedy" algorithm. You are not going to achieve a fully optimal result, but the bulk discount you will get should compensate for that.

a) Clearly the 96 and 99 pieces will go by themselves: that makes 10 strings.

b) Next, the 36 lamps sections being the largest majority (34 out of 105) are those "leading the play". I would try and accomodate them first.

The complement of 36 is 64. Two pieces of 36 leave a remainder of 28.
There are not many ways to reuse such remainders.
Therefore proceed and accomodate these two measures first of all, then pass to the remaining ones.

-- Addendum --

I have been pondering upon the fact that the problem would be optimally solved by an "analogic gravitational computer": a prismatic box of width $100$ filled with rods (e.g. pencils) of the given lengths.

Luci_Natale_1

Once well shaken a number of times it will reach a (near) optimal filling.
And if the apex angle is progressively reduced to get a parallelepiped $100 \times 1 \times H$, and the material of the box is transparent you can read the solution.
I deem that such analogic calculator will perform the greedy algorithm said above (more or less).

$\endgroup$
  • $\begingroup$ Thanks so much! I just put all my strings into an excel sheet and started matching them up. The best I could do was getting it down to a waste of 556 bulbs and 55 stings being used to make the smaller strings. I can live with that, we'll just have lots of spares. $\endgroup$ – Tim Larson Oct 27 '18 at 21:44
  • 1
    $\begingroup$ @TimLarson: glad it helped. It is an interesting and very practical problem, that caught my attention and lead me to devise the addendum to my answer. $\endgroup$ – G Cab Oct 28 '18 at 11:29
  • $\begingroup$ The "analogic gravitational computer" is a great idea, with a very cool name! It is an engineer-style solution. $\endgroup$ – Giuseppe Negro Oct 28 '18 at 11:40
  • $\begingroup$ @TimLarson: the above from a pure mathematical point. The electrical and spatial sequencing constraints will be more challenging, I suppose. $\endgroup$ – G Cab Oct 28 '18 at 11:43
  • 1
    $\begingroup$ @GiuseppeNegro: thanks for appreciation. In fact I am an engineer, and engineering is the bridge from math/physics to ..Christmas lights. $\endgroup$ – G Cab Oct 28 '18 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.