Talk:Sailors, coconuts and a monkey problem
J
I smiled at that end comment, but there may be an issue with the choice of an end value to search over. It seems that unlike testing incrementing values you have to put a ceiling on the range searched for.
But then you would have to do that in many solutions such as choosing an integer type in C or a range to search over in constraint solvers so just ignore me.
--Paddy3118 (talk) 08:35, 3 May 2015 (UTC)
I do have to put in a ceiling - that gives me bound search time and protects me from "infinite loop" bugs while I'm playing with the code. But if a given value doesn't give me good results, it's trivial for me to multiply it by 10 and try again. I guess what I'm saying is that for this problem, this approach saved time for me. (But I guess you basically said this already, in your second paragraph.) --Rdm (talk) 11:55, 3 May 2015 (UTC)
Analysis
Let the solution be described by:
n6 g6 n5 g5 n4 g4 n3 g3 n2 g2 n1 g1
where n is the number of coconuts at each stage and g is the number of coconuts in each pile.
note that g1 is n1/5 and g2*4, which implies that n1 is divisible by 20. It is simple to calculate the entire table given n1. It is obvious that n1 is of the form X + (4*5)*2*(2*)*(2*2)*(2*2*2*2) or 5120. X is divisible by 20 and less than 5120. Which implies that J's maximum value is justified if over generous. By examination X must be a member of the series 20 + 40*z. Let us look at that:
20 26 33.5 42.875 60 76 96 121 100 126 158.5 199.125 140 176 221 277.25 180 226 283.5 355.375 220 276 346 433.5 260 326 408.5 511.625 300 376 471 589.75 340 426 533.5 667.875 380 476 596 746 420 526 658.5 824.125 460 576 721 902.25
By examining the 4th column we can see that when the step is 320 ((4*5)*2*(2*)*(2*2) X is 60. So X must be a member of the series 60 + 320*z. Let us look at that:
60 76 96 121 152.25 191.3125 380 476 596 746 933.5 1167.875 700 876 1096 1371 1714.75 2144.4375 1020 1276 1596 1996 2496 3121 1340 1676 2096 2621 3277.25 4097.5625 1660 2076 2596 3246 4058.5 5074.125 1980 2476 3096 3871 4839.75 6050.6875 2300 2876 3596 4496 5621 7027.25 2620 3276 4096 5121 6402.25 8003.8125 2940 3676 4596 5746 7183.5 8980.375 3260 4076 5096 6371 7964.75 9956.9375 3580 4476 5596 6996 8746 10933.5 3900 4876 6096 7621 9527.25 11910.0625 4220 5276 6596 8246 10308.5 12886.625 4540 5676 7096 8871 11089.75 13863.1875 4860 6076 7596 9496 11871 14839.75 5180 6476 8096 10121 12652.25 15816.3125 5500 6876 8596 10746 13433.5 16792.875 5820 7276 9096 11371 14214.75 17769.4375 6140 7676 9596 11996 14996 18746 6460 8076 10096 12621 15777.25 19722.5625 6780 8476 10596 13246 16558.5 20699.125 7100 8876 11096 13871 17339.75 21675.6875 7420 9276 11596 14496 18121 22652.25 7740 9676 12096 15121 18902.25 23628.8125 8060 10076 12596 15746 19683.5 24605.375 8380 10476 13096 16371 20464.75 25581.9375 8700 10876 13596 16996 21246 26558.5 9020 11276 14096 17621 22027.25 27535.0625 9340 11676 14596 18246 22808.5 28511.625 9660 12076 15096 18871 23589.75 29488.1875 9980 12476 15596 19496 24371 30464.75 10300 12876 16096 20121 25152.25 31441.3125 10620 13276 16596 20746 25933.5 32417.875 10940 13676 17096 21371 26714.75 33394.4375 11260 14076 17596 21996 27496 34371 11580 14476 18096 22621 28277.25 35347.5625 11900 14876 18596 23246 29058.5 36324.125 12220 15276 19096 23871 29839.75 37300.6875 12540 15676 19596 24496 30621 38277.25 12860 16076 20096 25121 31402.25 39253.8125 13180 16476 20596 25746 32183.5 40230.375 13500 16876 21096 26371 32964.75 41206.9375 13820 17276 21596 26996 33746 42183.5 14140 17676 22096 27621 34527.25 43160.0625 14460 18076 22596 28246 35308.5 44136.625 14780 18476 23096 28871 36089.75 45113.1875 15100 18876 23596 29496 36871 46089.75 15420 19276 24096 30121 37652.25 47066.3125
Examination of the final column we see that for the step of 5120 "(4*5)*2*(2*)*(2*2)*(2*2*2*2)" X is 1020.
--Nigel Galloway (talk) 09:44, 5 May 2015 (UTC)
- Nigel, it's a great analysis, but technically adding an answer based on this is excluded from the task as I did not want people to just copy an analytical solution from somewhere (OEIS has one) and use that.
- What to do? Right now I've added a note to your example on the page to discourage others from going down the same route but left it in place.
- A workable compromise? --Paddy3118 (talk) 06:19, 12 May 2015 (UTC)
- Well Paddy3118 you certainly seem to like these silly notes, certainly you are not a mathematician or a lawyer, so this should be interesting. According to the task description I should calculate the starting value. By what stretch of the English language do any of the solutions calculate the starting value?
- Let us compare my solution with the Python solution. On numerous combinatronics problems I have stressed the importance of separating the verification of candidates from the selection of candidates. In spite of this and whatever the drivel "Parameterised the number of sailors using an inner loop including the last mornings case" means the Python solution does not do this, and for that alone is worth no more than 0 out of 100.
- I contend that my solution does meet the task requirements because _ng verifies each candidate by applying the problems constrains using integer divisions and remainders and tests on remainders, any lawyer want to tell me otherwise?.
- The question is how do I select the candidates? To answer this I introduce the oxymoron 'honest sailors' as a literary device to add dramatic effect and a technical device to explain the selection.
- The case when 4 sailors are honest and one dishonest is constructed as the initial basis:
26 5 20 4
- It is impossible to have 2 dishonest sailors unless at least 1 sailor is dishonest. So I suggest the case for 2 dishonest sailors is a proper subset of the set of solutions for 1 dishonest sailor which I shall represent as 20+g*20. I try each of these values against my verification procedure which returns false until g=2 giving the answer:
96 19 76 15 60 12
- It is impossible to have 3 dishonest sailors unless at least 2 sailors are dishonest. So I suggest the case for 3 dishonest sailors is a proper subset of the set of solutions for 2 dishonest sailors which I shall represent as 60+g*80. I try each of these values against my verification procedure which returns true with g=0 giving the answer:
121 24 96 19 76 15 60 12
- It is impossible to have 4 dishonest sailors unless at least 3 sailors are dishonest. So I suggest the case for 4 dishonest sailors is a proper subset of the set of solutions for 3 dishonest sailors which I shall represent as 60+g*320. I try each of these values against my verification procedure which returns false until g=2 giving the answer:
2496 499 1996 399 1596 319 1276 255 1020 204
- It is impossible to have 5 dishonest sailors unless at least 4 sailors are dishonest. So I suggest the case for 5 dishonest sailors is a proper subset of the set of solutions for 4 dishonest sailors which I shall represent as 1020+g*1280. I try each of these values against my verification procedure which returns true with g=0 giving the answer:
3121 624 2496 499 1996 399 1596 319 1276 255 1020 204
- So in spite of stopping and starting I find the solution with 8 candidates. Which is certainly more calculated than the Python candidate selection which would better be described as brainless. As with all good AI programs on classical computers it is possible to ask the program to explain its reasoning, the output for the 100 case is Sailors, coconuts and a monkey problem/Ruby output 100 honest sailors. As you can see it selects 4950 candidates to find the solution for 100 sailors, less than the Python solution uses for 5 sailors.
- Compromise? You must decide what calculate means. If it means calculate, then you should specify the equation you want to use to calculate the correct value in steps 1 and 3 which must simply be verified in steps 2 and 4. You should then stick a silly note on just about every solution. If it is acceptable to provide candidates to the verification procedure until a correct solution is found, then I see no reason to consider my solution less worthy than any other (actually I think it's better than any other) and you should remove your silly note from my solution.
--Nigel Galloway (talk) 14:35, 13 May 2015 (UTC)