September 2015

[Xyzzy]

https://www.research.ibm.com/haifa/p...ember2015.html

[R. Gerbicz]

On Ibm there was an update:

"Update (3/9):
You can do better than 56."

[henryzz]

Originally Posted by R. Gerbicz

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.

[KangJ]

Originally Posted by henryzz

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...

[R. Gerbicz]

Originally Posted by henryzz

I believe N=8 is the maximum for 4 teams.

That is always useful to solve the smaller cases, like for 4 teams.

[LaurV]

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)

[R. Gerbicz]

Originally Posted by LaurV

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.

[LaurV]

They put October on, but didn't put the solution for September. I will wait few days more to post my reasoning.

[LaurV]

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)

[R. Gerbicz]

Originally Posted by LaurV

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]

[R. Gerbicz]

Originally Posted by LaurV

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).