mersenneforum.org September 2015
 Register FAQ Search Today's Posts Mark Forums Read

 2015-08-31, 14:09 #1 Xyzzy     "Mike" Aug 2002 100000001101012 Posts September 2015
 2015-09-04, 13:20 #2 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 101110011102 Posts On Ibm there was an update: "Update (3/9): You can do better than 56."
2015-09-05, 22:01   #3
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2·33·109 Posts

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

2015-09-06, 01:43   #4
KangJ

Jul 2015

916 Posts

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

2015-09-06, 19:02   #5
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×743 Posts

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

 2015-09-07, 14:46 #6 LaurV Romulan Interpreter     Jun 2011 Thailand 3×3,221 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 2015-09-07 at 14:50
2015-09-07, 16:46   #7
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·743 Posts

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

 2015-10-02, 04:10 #8 LaurV Romulan Interpreter     Jun 2011 Thailand 25BF16 Posts They put October on, but didn't put the solution for September. I will wait few days more to post my reasoning.
 2015-10-06, 14:08 #9 LaurV Romulan Interpreter     Jun 2011 Thailand 966310 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 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
2015-10-06, 14:39   #10
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·743 Posts

Quote:
 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]

Last fiddled with by R. Gerbicz on 2015-10-06 at 14:40

2015-10-06, 22:00   #11
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

27168 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post R. Gerbicz Puzzles 21 2018-03-17 13:19 Batalov Puzzles 8 2016-10-04 14:10 Xyzzy Puzzles 3 2014-11-02 19:04 Oddball Twin Prime Search 11 2011-09-22 06:47 fivemack Factoring 1 2007-09-07 00:29

All times are UTC. The time now is 19:35.

Thu Aug 5 19:35:41 UTC 2021 up 13 days, 14:04, 1 user, load averages: 4.04, 3.78, 3.59