20150831, 14:09  #1 
"Mike"
Aug 2002
8138_{10} Posts 
September 2015

20150904, 13:20  #2 
"Robert Gerbicz"
Oct 2005
Hungary
2×733 Posts 
On Ibm there was an update:
"Update (3/9): You can do better than 56." 
20150905, 22:01  #3  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5,869 Posts 
Quote:
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=1314 more. 

20150906, 01:43  #4  
Jul 2015
9_{10} Posts 
Quote:
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... 

20150906, 19:02  #5 
"Robert Gerbicz"
Oct 2005
Hungary
2·733 Posts 

20150907, 14:46  #6 
Romulan Interpreter
Jun 2011
Thailand
2^{5}×5×59 Posts 
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 20150907 at 14:50 
20150907, 16:46  #7  
"Robert Gerbicz"
Oct 2005
Hungary
2·733 Posts 
Quote:
Post solution only after the official solution appears, usually the contest ends in the first few days of the next month. 

20151002, 04:10  #8 
Romulan Interpreter
Jun 2011
Thailand
10010011100000_{2} Posts 
They put October on, but didn't put the solution for September. I will wait few days more to post my reasoning.

20151006, 14:08  #9 
Romulan Interpreter
Jun 2011
Thailand
2^{5}·5·59 Posts 
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 N1 teams, we must have "2" in our string, because having a 2 will "save" one team (i.e. we use N medals to award N1 teams, by giving a team 2 medals, there is no other way). But we have to reward N2 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" x1 "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 singleman teams, or we can reward N1 teams, by rewarding the team with 2 members, or we can reward N2 teams, by rewarding the team with 3 members, or we can reward N3 teams, by rewarding both the team with 2 members and the team with 3 members. But we can't reward N4 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, y1, x1, a1, b1, N1". The "1, 2, 4" in the beginning is very important. You will recognize the powers of 2. So, we can reward N1 (i.e. "save 1") teams by awarding the team with 2 people. We can reward N2 (i.e. "save 2") teams by awarding the team with 3 people. We can reward N3 (i.e. "save 2+1") teams by awarding both, the team with 3 people and with 2 people. We can reward N4 (i.e. "save 4") teams by awarding the team with 5 people. We can reward N5 (i.e. "save 4+1") teams by awarding both, the team with 5 people and with 2 people. We can reward N6 (i.e. "save 4+2") teams by awarding both, the team with 5 people and with 3 people. We can reward N7 (i.e. "save 4+2+1") teams by awarding all the teams (with 5 people, 3 people, 2 people). But we can not reward N8 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 N1, N2, 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 N1, N2, ... N7 teams. We can reward N7 teams in 2 ways now, either like before (2, 3, 5), or just rewarding the team with 8 members. We can reward N8, by rewarding the teams with 8 and 2 (save 7+1 respectively, we get N71). And so on, until we use up all the 2, 3, 5, 8, rewarding N1247=N14 teams. So, we need a x=16, to reward N15 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") Nk=N12471523 teams, but we can't reward Nk1 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 20151006 at 14:25 
20151006, 14:39  #10  
"Robert Gerbicz"
Oct 2005
Hungary
2·733 Posts 
Quote:
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 multiperson teams. [[See my solution in the attached c code.]] It is clear that if a1<=a2...<=a_k in the multiperson teams then a_k<=2^k is true: see the awards with N,N1,...,N2^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,..,k1), 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 Ns single person teams, giving Ns+b=N(sb) teams, note that this is only true if N>=s. 3. if k is the smallest number that is not reached, where k=sb, then Nk=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_[k1] Last fiddled with by R. Gerbicz on 20151006 at 14:40 

20151006, 22:00  #11  
"Robert Gerbicz"
Oct 2005
Hungary
10110111010_{2} Posts 
Quote:
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). 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
September 2017  R. Gerbicz  Puzzles  21  20180317 13:19 
September 2016  Batalov  Puzzles  8  20161004 14:10 
September 2014  Xyzzy  Puzzles  3  20141102 19:04 
TPS Record Rally: September 1621  Oddball  Twin Prime Search  11  20110922 06:47 
Anyone going to Vienna in September?  fivemack  Factoring  1  20070907 00:29 