mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2016-12-01, 14:46   #1
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

11111110110102 Posts
Default December 2016

https://www.research.ibm.com/haifa/p...ember2016.html
Xyzzy is offline   Reply With Quote
Old 2016-12-01, 20:21   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

942010 Posts
Default

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

All too often one finds the following requirement in a job description:
"A successful applicant must be able to lift up to 50 lb. bags."
Batalov is offline   Reply With Quote
Old 2016-12-02, 03:10   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

25·5·59 Posts
Default

Quote:
Originally Posted by Batalov View Post
"A successful applicant must be able to lift up to 50 lb. bags."
Technically, there is nothing illegal in that, as the IATA safety limit is fixed to 23 kg..
Quote:
Originally Posted by 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.
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..

Last fiddled with by LaurV on 2016-12-02 at 03:16
LaurV is offline   Reply With Quote
Old 2017-01-02, 15:18   #4
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

2×33×151 Posts
Default

https://www.research.ibm.com/haifa/p...ember2016.html
Xyzzy is offline   Reply With Quote
Old 2017-01-02, 16:26   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

24CC16 Posts
Default

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?
Batalov is offline   Reply With Quote
Old 2017-01-02, 21:33   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·733 Posts
Default

Quote:
Originally Posted by Batalov View Post
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?
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).
R. Gerbicz is offline   Reply With Quote
Old 2017-01-02, 21:41   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×3×5×157 Posts
Default

Brilliant!
Batalov is offline   Reply With Quote
Old 2017-01-03, 03:06   #8
uau
 
Jan 2017

2·32·5 Posts
Default

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.
uau is offline   Reply With Quote
Old 2017-01-03, 03:59   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·3·5·157 Posts
Default

Added to OEIS as A280432 (draft)
Let's see if editors will contribute an insight?

This problem deserves an AMS paper (if there isn't one on the subject)!
Batalov is offline   Reply With Quote
Old 2017-01-03, 07:51   #10
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×733 Posts
Default

a(0)=1 and it is optimal.
R. Gerbicz is offline   Reply With Quote
Old 2017-01-03, 16:01   #11
uau
 
Jan 2017

2×32×5 Posts
Default

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
-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 -1
-1  1  1 -1  0 -1  1
 0 -1  1  1 -1 -1  1


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
uau is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
December 2017 Batalov Puzzles 4 2018-01-04 04:33
December 2015 Xyzzy Puzzles 15 2016-01-06 10:23
December 2014 Xyzzy Puzzles 13 2015-01-02 19:41
Conference in Amsterdam 1-2 December fivemack Information & Answers 6 2011-12-12 13:13
Server update in December ltd Prime Sierpinski Project 4 2010-12-17 13:14

All times are UTC. The time now is 10:03.

Sun May 9 10:03:35 UTC 2021 up 31 days, 4:44, 0 users, load averages: 4.78, 4.44, 4.11

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.