- katastrofa
**Posts:**8772**Joined:****Location:**Alpha Centauri

ps.: outrun, did you try to find an upper bound on minmax S by induction?

That's indeed interesting to investigate, haven't tried that. Have you?ps.: outrun, did you try to find an upper bound on minmax S by induction?

- katastrofa
**Posts:**8772**Joined:****Location:**Alpha Centauri

Nope BTW, I posted some reasoning (above) which can speed up brute force methods on the previous page, but it got lost in spam.I'm not sure what's your definition of brute force and I didn't have the patience to read all those responses, but a partial solution is straightforward and allows to find the final result much faster then the actual brute force approach. You only need to notice that the average sum of triple S is 24. This means that the minmax S cannot be smaller than 24, because if any triple has S<=23, then there must be some another triple for which S>=25. Simples! This observation already spares some computational time. Next, you notice that minmax S = 24 would require a uniform S over the whole "ring", because if S = 24 for any triple a, b, c, then the "adjacent" triple must be b, c, a, while you have only one a at your disposal. This makes you start the search from 25 and quickly find the solution.

I think I can guess in what textbook you came across this task and indeed most problems in this field are NP-hard.

When I was a student I had to prove if some problem was NP complete or not, ..horrible... I also had a oral exam where I got questions like "can you give an example of an NP-hard problem and how it not intersects with co-NP-space-complete?". It's often non-intuitive, when I was a student "primarily test" was not known to be in either P or NP, later it was discovered to be in P.

The puzzle comes from the Le Mond newspaper that has regular entertaining math puzzles. I found out about it while reading this excellent blog: https://xianblog.wordpress.com/

The puzzle comes from the Le Mond newspaper that has regular entertaining math puzzles. I found out about it while reading this excellent blog: https://xianblog.wordpress.com/

GZIP: On