mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2015-08-31, 14:09   #1
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

209F16 Posts
Default September 2015

https://www.research.ibm.com/haifa/p...ember2015.html
Xyzzy is offline   Reply With Quote
Old 2015-09-04, 13:20   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·3·11·23 Posts
Default

On Ibm there was an update:

"Update (3/9):
You can do better than 56."
R. Gerbicz is offline   Reply With Quote
Old 2015-09-05, 22:01   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

3·1,979 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
On Ibm there was an update:

"Update (3/9):
You can do better than 56."
That frustrates me as my solution gives a maximum of 55. There must be something I haven't seen yet.


I believe N=8 is the maximum for 4 teams. Based on my current reasoning this means N=13 for 5 teams, N=21 for 6 teams, N=34 for 7 teams and N=55 for 8 teams. This follows the Fibonacci sequence. Apparently there is something better than this. I need to study N=9 and N=13-14 more.
henryzz is offline   Reply With Quote
Old 2015-09-06, 01:43   #4
KangJ
 
Jul 2015

32 Posts
Default

Quote:
Originally Posted by henryzz View Post
That frustrates me as my solution gives a maximum of 55. There must be something I haven't seen yet.


I believe N=8 is the maximum for 4 teams. Based on my current reasoning this means N=13 for 5 teams, N=21 for 6 teams, N=34 for 7 teams and N=55 for 8 teams. This follows the Fibonacci sequence. Apparently there is something better than this. I need to study N=9 and N=13-14 more.

I think N=8 is the maximum for 4 teams.
However, N=56 is possible for 8 teams. (Not Fibonacci strategy)

2, 3, 5, 8, 16, 24, 32, 56

I am trying to find N>56 cases for 8 teams...
KangJ is offline   Reply With Quote
Old 2015-09-06, 19:02   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

27568 Posts
Default

Quote:
Originally Posted by henryzz View Post

I believe N=8 is the maximum for 4 teams.
That is always useful to solve the smaller cases, like for 4 teams.
R. Gerbicz is offline   Reply With Quote
Old 2015-09-07, 14:46   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

980810 Posts
Default

This problem is extremely simple, just elementary logic and elementary math, no programming or search. Had some time to look into it today, and it didn't take more than half hour.
edit: I'll post my reasoning at the end of the month.
edit 2: remark that solving "smaller cases" won't help much in this particular case/problem (and I will explain why)

Last fiddled with by LaurV on 2015-09-07 at 14:50
LaurV is offline   Reply With Quote
Old 2015-09-07, 16:46   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

151810 Posts
Default

Quote:
Originally Posted by LaurV View Post
This problem is extremely simple, just elementary logic and elementary math, no programming or search.
[...]
I'll post my reasoning at the end of the month.
I have used c code.
Post solution only after the official solution appears, usually the contest ends in the first few days of the next month.
R. Gerbicz is offline   Reply With Quote
Old 2015-10-02, 04:10   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24×613 Posts
Default

They put October on, but didn't put the solution for September. I will wait few days more to post my reasoning.
LaurV is offline   Reply With Quote
Old 2015-10-06, 14:08   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24·613 Posts
Default

Ok, the answer is online, so we won't spoil anything.
As said, this is just an elementary logic problem, no need any computing power to solve it.
First, we have to reward ANY number of teams. To be able to reward 1 team, and no money left, we must have a team with N people. Obvious. Also, to reward two teams, we must have two teams whose sum is N.

On the other side of the spectrum, to be able to reward N-1 teams, we must have "2" in our string, because having a 2 will "save" one team (i.e. we use N medals to award N-1 teams, by giving a team 2 medals, there is no other way).

But we have to reward N-2 teams too. So, either we have 2 teams with 2 members, or 1 team with 3 members.

So, up to now, we have either "2, 3, z, y, x, a, b, a+b=N" or "2, 2, z, y, x, a, b, a+b=N"

How much we "save" in each case? Note that having a team with x members will "save" x-1 "medals" (or dollars, whatever). First case can "save" 1+2, the second can only "save" 1+1. The binary representation comes immediately into mind, and that is why the first one is more optim than the second, we can reward N teams, by giving the money to single-man teams, or we can reward N-1 teams, by rewarding the team with 2 members, or we can reward N-2 teams, by rewarding the team with 3 members, or we can reward N-3 teams, by rewarding both the team with 2 members and the team with 3 members. But we can't reward N-4 teams. For that we need a team with 4(save)+1=5 members.

Look to the string now: "2, 3, 5, y, x, a, b, N".

The "Fibonacci" is coincidental here. The string has nothing to do with Fibo, and THAT is the realization one has to do. Look to how much we "save" with every team. The string of "savings" are "1, 2, 4, y-1, x-1, a-1, b-1, N-1".

The "1, 2, 4" in the beginning is very important. You will recognize the powers of 2.

So, we can reward N-1 (i.e. "save 1") teams by awarding the team with 2 people.
We can reward N-2 (i.e. "save 2") teams by awarding the team with 3 people.
We can reward N-3 (i.e. "save 2+1") teams by awarding both, the team with 3 people and with 2 people.
We can reward N-4 (i.e. "save 4") teams by awarding the team with 5 people.
We can reward N-5 (i.e. "save 4+1") teams by awarding both, the team with 5 people and with 2 people.
We can reward N-6 (i.e. "save 4+2") teams by awarding both, the team with 5 people and with 3 people.
We can reward N-7 (i.e. "save 4+2+1") teams by awarding all the teams (with 5 people, 3 people, 2 people).

But we can not reward N-8 people. For that, we need a 9 (! yes!) in our string. Remark: it is not an 8!

Sure you got the idea. If we would have an "infinite" (i.e. big number, more than 8 "multiple persons" teams) in our competition, the beginning of our string would always be:

2, 3, 5, 9, 17, 33, ..... 2^x+1....

Why? because this "saves" (or, it is "consumes" a better word?), respectively 1, 2, 4, 8, 16, 32.... 2^x... dollars each, and by combinations between them we can "make" any number between 1 (or 0) and 2^(x+1)-1. But we will always need the next power of 2 to reward less teams (i.e. "save" more money).

It has nothing to do with Fibo, it is just powers of 2, and the Fibo in the beginning is coincidental, because 2, 3, 5, is just powers of 2 plus 1. From here, generalization is very simple (yes, I can produce the string with ANY specific number of teams, such as N be maximum, see below too).

Now, this can't really be our string, because in this case we can't reward 2, 3, 4, etc. teams. We were only talking about N-1, N-2, but not about the other side of the spectrum. We can not have on the forth position a number higher than 9, otherwise we will not be able to award 8 teams. But we can have a number less than 9. Technically we may also have a number less than 5 on the third position, depends on the limitations coming from the other side.

What we know up to now, for sure, makes the string to be:

2, 3, max 5, max 9, x, a, b, N=a+b.

With this we can reward 1, or 2 teams (i.e. the team with N members, or respectively "the team with 'a' members and the team with 'b' members").

How we award 3 teams? Obviously, we will need to split either a, or b, into two. It doesn't matter which one we take. Say we split a (please remark that a<b, in this case), then we have a=x+"max 9".

But to award 4 teams we need to continue splitting the leftmost (which is "max 9") into other two, therefore we get "max9"="max5"+3. So, the "max9" is in fact "max8", because is "max5" plus 3.

Remark the rule, it is a kind of "tricky Fibo", where the sum is not for every term in the sequence, but from every second term in the sequence. Always split the leftmost one, to increase the number of "awardable" teams by 1.

Putting all together:

2, 3, 5, 8, x (as big as possible), a=x+8, any b (as big as possible), N=a+b.

("5" and "8" can not be smaller now, because then "a" is smaller, therefore N is smaller)

Remark that we have to pic x and b in this case, as big as possible, and that none of them enters in constrain relations (like "8", or "a", or "N"), that is what I said "every second one".

How many teams we can reward now, in both directions?
Well, we know we can reward N-1, N-2, ... N-7 teams. We can reward N-7 teams in 2 ways now, either like before (2, 3, 5), or just rewarding the team with 8 members.
We can reward N-8, by rewarding the teams with 8 and 2 (save 7+1 respectively, we get N-7-1).
And so on, until we use up all the 2, 3, 5, 8, rewarding N-1-2-4-7=N-14 teams. So, we need a x=16, to reward N-15 teams.

Now we have the string of teams: 2, 3, 5, 8, 16, 24, b, N=b+24.

Repeating the procedure above, we can reward up to (or better said, "down to") N-k=N-1-2-4-7-15-23 teams, but we can't reward N-k-1 teams. We will need a b=k+2 for that (to "save"/"consume" k+1 additional dollars when awarding that team). From which k=52. therefore:

2, 3, 5, 8, 16, 24, 54, 78 - which is the final, and the best solution.

As said above this is very easy to generalize, you go with powers of two for a while, then from the back, each second (even) term is the sum of the "savings" (sum of each term minus number of terms), and each "second plus 1" (odd) term is the sum of two previous terms. Well this is more difficult to say than to do. There is only one small trick left, but I will let you find it.

Generally, after we finish with "powers of 2 plus 1", then odd terms are formed like in the Fibo sequence, but even terms are derived from sums of everything before, not only the last 2. That is why it grows much faster. You will consider that in this discussion "odd/even" depends on the parity of the number of teams, but this is irrelevant for the reasoning part.

So, can you say what is N for 20 teams instead of 8?
(I can, and I can prove is maximal)

Last fiddled with by LaurV on 2015-10-06 at 14:25
LaurV is offline   Reply With Quote
Old 2015-10-06, 14:39   #10
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101111011102 Posts
Default

Quote:
Originally Posted by LaurV View Post
So, can you say what is N for 20 teams instead of 8?
(I can, and I can prove is maximal)
Of course not, but reached n=9;N=146 for 2,3,5,9,14,30,44,102,146 ; n=10;N=268 for 2,3,5,9,17,33,65,70,198,268 (these are optimal solutions)
n=11;N=524 (optimal??) for 2,3,5,9,17,33,65,129,134,390,524
n=12;N=1033 (optimal?????) for 2,3,5,9,17,33,65,129,256,261,772,1033

My sent solution was (It looks like a shorter solution and contains also a proof.):
"N=78 and one optimal solution is reached with number of people 2,3,5,8,16,24,54,78 in the multi-person teams. [[See my solution in the attached c code.]]

It is clear that if a1<=a2...<=a_k in the multi-person teams then a_k<=2^k is true: see the awards with N,N-1,...,N-2^k+1 teams, if a_k>2^k, then we can't use a_k and larger teams in that distribution (the total number of people in the teams would be larger than N), and in this case we have less than 2^k choices to select the teams (we select a_i or not for i=1,..,k-1), but we need 2^k choices, contradiction.

If we see the 1 team award we get that a_8=N, and using the above idea a_1=2. We iterate on all above cases, using the following ideas:
1. obviously we use a_8 only in the 1 team distribution
2. if there are s people in b teams, then we have to use N-s single person teams, giving N-s+b=N-(s-b) teams, note that this is only true if N>=s.
3. if k is the smallest number that is not reached, where k=s-b, then N-k=1, so N=k+1 as the only remaining case that we have not considered is that when we use a_8 (the largest team), and use no other teams."

my further remark: you can say better than a_k<=2^k for fixed a_1,a_2..a_[k-1]

Last fiddled with by R. Gerbicz on 2015-10-06 at 14:40
R. Gerbicz is offline   Reply With Quote
Old 2015-10-06, 22:00   #11
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5EE16 Posts
Default

Quote:
Originally Posted by LaurV View Post
Sure you got the idea. If we would have an "infinite" (i.e. big number, more than 8 "multiple persons" teams) in our competition, the beginning of our string would always be:

2, 3, 5, 9, 17, 33, ..... 2^x+1....

Why? because this "saves" (or, it is "consumes" a better word?), respectively 1, 2, 4, 8, 16, 32.... 2^x... dollars each, and by combinations between them we can "make" any number between 1 (or 0) and 2^(x+1)-1. But we will always need the next power of 2 to reward less teams (i.e. "save" more money).

[...]
Now, this can't really be our string, because in this case we can't reward 2, 3, 4, etc. teams. We were only talking about N-1, N-2, but not about the other side of the spectrum. We
I have even a problem with the 2,3,5 start, compare this with the 2,3,4 start. In each case we would like to reach for example saving=3 on the beginning of the sequence. If we use 4 on the second case then the total number of teams=N-(s+4-(b+1))=N-s+b-3, if on the rest of the sequence we have used s people on b teams. On the first case we have to select 2,3 to reach saving=3 (and you have no other choice), and you get total number of teams=N-(s+5-(b+2))=N-s+b-3.

It looks like good, we have gotten the same number of teams, what we have reached on the suboptimal(?) 2,3,4 sequence we have reached that one on the 2,3,5 sequence. Now suppose that N=s+4, and see the number of single person of teams, on the second case we have N-(s+4)=0, so not using single person teams, and on the first case: we use N-(s+5)=-1 single person teams, what is impossible!

That's why it was important to note that condition in my previous post, that you need s<=N (where s is the number of people in the multiperson teams).

You can also see this effect on n=4 and using the multiperson teams=2,3,5,9 so your optimal start: we can't reach 9=a+b, so the two teams award selection, but the others are possible. Why this happens? we need saving=7, but that is reachable only with 2+3+5, but that is 10>n, so we can't reach the two teams selection. (That's why for n=4 the optimal is only N=8 and not N=9).
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
September 2017 R. Gerbicz Puzzles 21 2018-03-17 13:19
September 2016 Batalov Puzzles 8 2016-10-04 14:10
September 2014 Xyzzy Puzzles 3 2014-11-02 19:04
TPS Record Rally: September 16-21 Oddball Twin Prime Search 11 2011-09-22 06:47
Anyone going to Vienna in September? fivemack Factoring 1 2007-09-07 00:29

All times are UTC. The time now is 00:33.


Thu Dec 2 00:33:50 UTC 2021 up 131 days, 19:02, 1 user, load averages: 0.70, 0.95, 0.98

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.