Project Euler Problem 768 Chandelier

[Charlie-Boo]

I have never asked about a PE problem before, but this is so frustrating here I am. It has to do with definitions.

The problem is to count how many ways you can put m identical candles in n distinct candleholders in a (circular) chandelier and be balanced. f(n,m) = the number. The problem seems to be what they consider "balanced". They say:

"If only one candle is fitted, then the chandelier will be imbalanced. However, if a second identical candle is placed in the opposite candleholder (assuming n is even) then perfect balance will be achieved and the chandelier will hang level."

If this means we put in pairs of candles on opposite sides then there are m/2 pairs and n/2 places we can put them, so the answer is trivial: The number of subsets of size m/2 from a set of size n/2 i.e. (n/2)C(m/2). (This would be unprecedented.)

They give f(12,4)=15 which is in fact 6C2.

They give f(36,6)=876 but 18C3 is 816. I am missing 60. That suggests that not all candles are in pairs e.g. an equilateral triangle of 3 candles balances so I could put a pair at each vertex. But that would add many more than 60.

I considered the possibility that it is a typo, but the answer to the problem is rejected.

I just want to know where I'm wrong. The solvers are coming in VERY slowly!

C-B

[Mike Terry]

On 17/10/2021 18:09, Charlie-Boo wrote:
> I have never asked about a PE problem before, but this is so frustrating here I am. It has to do with definitions.
>
> The problem is to count how many ways you can put m identical candles in n distinct candleholders in a (circular) chandelier and be balanced. f(n,m) = the number. The problem seems to be what they consider "balanced". They say:
>
> "If only one candle is fitted, then the chandelier will be imbalanced. However, if a second identical candle is placed in the opposite candleholder (assuming n is even) then perfect balance will be achieved and the chandelier will hang level."
>

That is true, but I doubt that's their /definition/ of balanced?
Probably the intended definition is just mean that "the chandelier
balances" in the obvious way. So I expect f(12,3) = 4 ? That's because
the following placements balance: {0,4,8}, {1,5,9}, {2,6,10}, {3,7,11}
and those are the only placements that balance.

Ok, more formally, I assume the candleholders are equally space, and for
a placement with position vectors e_1, e_2, ... e_n the balancing
requirement would be e_1 + ... + e_n = 0.

> If this means we put in pairs of candles on opposite sides then there are m/2 pairs and n/2 places we can put them, so the answer is trivial: The number of subsets of size m/2 from a set of size n/2 i.e. (n/2)C(m/2). (This would be unprecedented.)
>
> They give f(12,4)=15 which is in fact 6C2.

Yes, but when placing 4 candles, all balancing placements will have to
have the placements in opposite pairs. Hmmm, that needs a proper proof,
but e.g. if we place 3 in an equilateral triangle, the last candle will
unbalance everything. So your (n/2)C(m/2) happens to work for this input.

>
> They give f(36,6)=876 but 18C3 is 816. I am missing 60. That suggests that not all candles are in pairs e.g. an equilateral triangle of 3 candles balances so I could put a pair at each vertex. But that would add many more than 60.

Well, I've not calculated anything, but the difference for f(36,6) is
that they can be placed in two sets of 3 equilateral triangles. (But
some of those placements will also result in opposite pairs, so overall
would think this would add 12*10/2 = 60. Hey that's exactly your
shortfall!

So you do you say you'd need many more than 60? We can divide the
holders into 3 runs of 12, so we choose one of those first giving the 12
factor, then the next triangle must contain one of the remaining 11 in
the run, but /not/ the one opposite one of the first placements, so
there are 10 possibilities, and we divide by 2 because the order of
choosing the triangles doesn't matter.

A more worrying problem for me is whether there are balancing placements
which /don't/ consist of subsets with rotational symmetry. That's a
genuine maths problem rather than a programming problem, and I think the
answer is "no", but I don't have an instant proof of that...

Mike.

[Charlie-Boo]

Mike,

You got it! I didn't consider the overlaps. The "many more" was due to my not realizing that the larger the regular polygon, the fewer both the orientations and the number of them (there's no tradeoff.) Triangles do add only 60 possibilities. Yes, it is math not computer science - it's Geometry!

Composition of heterogeneous subsets - intriguing. Is it just a matter of the center of gravity being the center? Project Euler has some great problems, including new variations of very simple principles of mathematics. But they drift too far from Competitive Programming for my tastes. The relative youth of Computer Science makes it an attractive alternative to Mathematics as a source of unsolved problems (or ill-understood principles such as Dynamic Programming.) It is disconcerting when Project Euler problems require advance mathematical theorems or principles of Geometry or Trigonometry to solve. Now it's physics. 😊

Thanks and all the best.

Charlie

[Mike Terry]

Yes, I think centre of gravity, but that presents an interesting
question. Say we were looking at f(60,12) - it would be nice, from a
computational angle, to say we have the following (overlapping)
possibilities:

- 6 pairs of opposites, or
- 4 triangles
- 2 triangles and 3 pairs
- (3 squares, but these are all special cases of 6 pairs)
- (similarly hexagons are covered by counting the 4 triangles)
- (similarly decagons, um, dodecagons(?), um, 15-gons, etc. :)
would be covered if we had enough candles to actually make them)
so in summary we could look at primes p dividing 60, namely
2,3 and 5 and decompose the placements into sums of p-gons.
- Hey so I forgot 5 above,
2 pentagons + 1 pair, 1 pentagon + 1 triangle + 2 pairs
etc.

That might give a way of breaking down the problem, perhaps.

BUT is it even TRUE that all balancings can be decomposed into the "sum
of p-gons"?

All I can instantly see is that if we could show every balancing
contained at least /one/ p-gon [even if only p=2 which is a balanced
pair] then the whole lot would decompose, because if we remove one p-gon
from a balancing it will still balance! so then there will be another
p-gon we can remove etc. and in the end the whole balancing must
decompose like that.

So mathematically, an equivalent question is "does every balancing
placement contain /at least one/ p-gon?" But I can't see why that must
be true (if it actually is true!). The reason I suspect it is true, is
that I have a vague (and maybe false) memory of this being asked here or
in rec.puzzles many years ago, like 15 to 20 years maybe and I think
there was some not too difficult proof but now I haven't a clue how it
went... It seems like a number theory question, involving roots of
unity and maybe group actions but that might be overcomplicating things
:) [Also I can't think of a simple counter-example of a balancing with
no p-gons, but I've not tried very hard at that.]

Anyway good luck and let us know how it goes for you.
Mike.

[James Waldby]

Mike Terry <news.dead.p...@darjeeling.plus.com> wrote:
> On 18/10/2021 03:10, Charlie-Boo wrote:
>> On Sunday, October 17, 2021 at 2:19:18 PM UTC-4, Mike Terry wrote:
>>> On 17/10/2021 18:09, Charlie-Boo wrote:
>>>> I have never asked about a PE problem before, but this is so frustrating here I am. It has to do with definitions.
>>>>
>>>> The problem is to count how many ways you can put m identical candles in n distinct candleholders in a (circular) chandelier and be balanced. f(n,m) = the number. The problem seems to be what they consider "balanced". They say:

...

...

>> You got it! I didn't consider the overlaps. The "many more" was due to my not realizing that the larger the regular polygon, the fewer both the orientations and the number of them (there's no tradeoff.) Triangles do add only 60 possibilities. Yes, it is math not computer science - it's Geometry!
>>
>> Composition of heterogeneous subsets - intriguing. Is it just a matter of the center of gravity being the center? Project Euler has some great problems

...

> Yes, I think centre of gravity, but that presents an interesting
> question. Say we were looking at f(60,12) - it would be nice, from a
> computational angle, to say we have the following (overlapping)
> possibilities:
>
> - 6 pairs of opposites, or
> - 4 triangles
> - 2 triangles and 3 pairs
> - (3 squares, but these are all special cases of 6 pairs)
> - (similarly hexagons are covered by counting the 4 triangles)
> - (similarly decagons, um, dodecagons(?), um, 15-gons, etc. :)
> would be covered if we had enough candles to actually make them)
> so in summary we could look at primes p dividing 60, namely
> 2,3 and 5 and decompose the placements into sums of p-gons.
> - Hey so I forgot 5 above,
> 2 pentagons + 1 pair, 1 pentagon + 1 triangle + 2 pairs

...

> BUT is it even TRUE that all balancings can be decomposed into the "sum
> of p-gons"?
>
> All I can instantly see is that if we could show every balancing
> contained at least /one/ p-gon [even if only p=2 which is a balanced
> pair] then the whole lot would decompose, because if we remove one p-gon
> from a balancing it will still balance! so then there will be another
> p-gon we can remove etc. and in the end the whole balancing must
> decompose like that.
>
> So mathematically, an equivalent question is "does every balancing
> placement contain /at least one/ p-gon?" But I can't see why that must
> be true (if it actually is true!). The reason I suspect it is true, is
> that I have a vague (and maybe false) memory of this being asked here or
> in rec.puzzles many years ago, like 15 to 20 years maybe and I think
> there was some not too difficult proof but now I haven't a clue how it
> went... It seems like a number theory question, involving roots of
> unity and maybe group actions but that might be overcomplicating things
> :) [Also I can't think of a simple counter-example of a balancing with
> no p-gons, but I've not tried very hard at that.]

Project Euler Problem 768 <https://projecteuler.net/problem=768>
concerns placing 20 candles upon a subset of 360 evenly spaced
candleholders on a circular chandelier. For balance we need lever
arms to be equal across any diameter of the circle, including the x
and y axes in particular. We can suppose unit masses and unit radii
and candle 1 at (1,0), and the i'th candle at location (x_i,y_i) and
angle t_i, some multiple of 2pi/360. That is, every candle is at a
360'th root of unity, and most are at lower-degree roots also.

For balance, we need sum{i}(x_i) = sum{i}(y_i) = 0, or equivalently
sum{i}(e^(i*t_i)) = 0 + 0i = 0, via Euler's Formula. There are
several items on math.stackexchange and mathoverflow.net (see links
below) with proofs inter alia that (a) no proper subset of prime p'th
roots of unity can sum to an integer, (b) sums over subsets of roots
of unity are unique. Those results ought to be enough to show every
balancing placement is a superposition of regular polygons, but at
the moment I don't see how to deal with composite numbers of sides.

<https://math.stackexchange.com/questions/1108446>
<https://mathoverflow.net/questions/46068>
<https://mathoverflow.net/questions/139355>
<https://mathoverflow.net/questions/180058>

[Ferrell Wheeler]

On Sunday, October 17, 2021 at 10:53:19 PM UTC-4, Mike Terry wrote:

> Yes, I think centre of gravity, but that presents an interesting
> question. Say we were looking at f(60,12) - it would be nice, from a
> computational angle, to say we have the following (overlapping)
> possibilities:
>
> - 6 pairs of opposites, or
> - 4 triangles
> - 2 triangles and 3 pairs
> - (3 squares, but these are all special cases of 6 pairs)
> - (similarly hexagons are covered by counting the 4 triangles)
> - (similarly decagons, um, dodecagons(?), um, 15-gons, etc. :)
> would be covered if we had enough candles to actually make them)
> so in summary we could look at primes p dividing 60, namely
> 2,3 and 5 and decompose the placements into sums of p-gons.
> - Hey so I forgot 5 above,
> 2 pentagons + 1 pair, 1 pentagon + 1 triangle + 2 pairs
> etc.
>
> That might give a way of breaking down the problem, perhaps.
>
> BUT is it even TRUE that all balancings can be decomposed into the "sum
> of p-gons"?

Consider a chandelier with 30 holders and candles placed at locations {0, 1, 7, 13, 19, 20}.

I believe this is balanced with no n-gons in sight.

Ferrell

[Mike Terry]

Yes, this works - nice one!

Looking at your example I see there's a simple idea behind it. You have
in effect one pentagon, and one triangle, but each has one candle
missing. So the pentagon has only 4 candles in place {1,7,13,19} and
the triangle has just 2 candles in place {0,20}. The two "missing"
candles would be at {10,25} which balance each other, so of course the
combination {0,1,7,13,19,20} balances.

Hmm, I guess we /could/ consider this as being decomposable into n-gons
like this:

{0,1,7,13,19,20} = {1,7,13,19,25} + {0,10,20} - {10,25}

Of course this isn't what I was originally meaning by decomposing into
n-gons - you certainly sunk my original idea with your example! :)

Whether the new "signed decomposition" idea would help in any way with
the original problem I've no idea!! But it's kind of interesting
anyway... Balancing anti-candles!!


Mike.