December 2016
 

[url]https://www.research.ibm.com/haifa/ponderthis/challenges/December2016.html[/url]

The Dec problem formulation would have been funny if it was not also too true!

All too often [URL="https://www.nas.org/articles/Wanted_A_College_Degree_and_the_Ability_to_Lift_50_Pounds"]one finds[/URL] the following requirement in a job description:
"A successful applicant must be able to lift up to 50 lb. bags."

[QUOTE=Batalov;448169]"A successful applicant must be able to lift up to 50 lb. bags."[/QUOTE]
Technically, there is nothing illegal in that, as the IATA safety limit is fixed to 23 kg.. :razz:
[QUOTE=IATA regulations]Your bag should weigh less than 23KG/50LBS. This is an international regulation set for the health and safety of airport workers who have to lift hundreds of bags daily. If your bag weighs more than this, you may be asked to repack, or have it labeled as "heavy luggage". The maximum weight however is 32KG/70LBS in the EU and the US. Some airlines impose lower limits. Refer to the airline website and your conditions of carriage.[/QUOTE]

Back on topic, another problem which can be solved in few minutes with a pencil... Yuck...
Programming an algorithm for higher N, however, may turn out to be... interesting... I will go for it this month.

edit: OTOH, I agree with Serge, formulation is silly, they could say "weighting coins", or everything else (we just had a similar problem recently), eventually it comes to that: having 27 coins and being allowed 4 weightings with a "non weight-marked" balance scale, tell if all coins have the same weight..

[url]https://www.research.ibm.com/haifa/ponderthis/solutions/December2016.html[/url]

Believe it or not, I've been waiting for the solution, because I expected it to be illuminating - and it certainly was. This is not in OEIS {2,4, ?, 30,114, ...}

I am now playing with this technique to see that this non-trivial (i.e. not a power of 2) set of solutions only arises at n>=4. I spent a few weekends tinkering with n=3, and it would explain why this was a dead end. Is a(3) = 8?

[QUOTE=Batalov;450339]Believe it or not, I've been waiting for the solution, because I expected it to be illuminating - and it certainly was.
[]
Is a(3) = 8?[/QUOTE]

a(3)>=10 !!! One solution, but check it:
BCDE;FGIJ
GIJ;AFH
BCDEF;AGHIJ
it was found very quickly with my code that used simply random permutations on each side.

Not solved this puzzle, but I wasn't that far: for the first contest and for N=30 there are only 15 different cases, up to symmetry, for the 2nd contest there is still not that many cases, but if you want only a few cases to check then you can arrive to the solution's group idea (use very few groups).

Brilliant!

Optimal answers to the original problem are a(1) = 2, a(2) = 4, a(3) = 10.
Optimal values for the "linear algebra with contest_count+1 groups" approach should be a(1) = 2, a(2) = 4, a(3) = 10, a(4) = 30, a(5) = 114, a(6) = 454. I haven't given much thought to how plausible it is that there could be a better solution which does not divide into contests+1 groups that way.

Added to OEIS as [URL="https://oeis.org/A280432"]A280432[/URL] (draft)
Let's see if editors will contribute an insight?

This problem deserves an AMS paper (if there isn't one on the subject)!

a(0)=1 and it is optimal.

If you want the 6-contest solutions for the sequence, here are the two ways to get 454:

[CODE]
group sizes 108, 90, 80, 58, 44, 39, 35
[COLOR=#000000][FONT=monospace]-1 -1 1 0 1 1 1[/FONT][/COLOR]
[COLOR=#000000][FONT=monospace]-1 0 1 1 1 -1 -1[/FONT][/COLOR]
[COLOR=#000000][FONT=monospace]-1 1 -1 1 1 -1 1[/FONT][/COLOR]
[COLOR=#000000][FONT=monospace]-1 1 0 1 -1 1 -1[/FONT][/COLOR]
[COLOR=#000000][FONT=monospace]-1 1 1 -1 0 -1 1
[/FONT][/COLOR][COLOR=#000000][FONT=monospace] 0 -1 1 1 -1 -1 1[/FONT][/COLOR]


group sizes 130, 85, 76, 62, 42, 35, 24
-1 -1 1 1 1 1 0
-1 1 -1 1 0 1 1
-1 1 0 1 1 -1 -1
-1 1 1 -1 1 -1 1
-1 1 1 0 -1 1 -1
0 -1 1 1 -1 -1 1
[/CODE]