Puzzle
7 minute read

Ponder This Challenge - August 2018 - (Almost) prime water sharing

There is a well-known riddle about two friends (Alice and Bob) who went walking in the desert.
Alice had two gallons of water and Bob had three gallons.
They met Charlie who had no water at all and they all (Alice, Bob, and Charlie) shared the five gallons of water evenly.
As a token of his gratitude, Charlie gave them five gold coins.
What is the fair way to split these five coins?
Hint: it is *not* the obvious two to Alice and three to Bob. (Why?)

Our challenge this month is to solve a similar problem:
In J.R.R. Tolkien's works, nine rings were given to humans. Our challenge is this: Each one of the nine ring holders brought W_i droplets of water (W_1, W_2, W_3, ..., W_9).
Sauron (who had the one ring to rule them all) came without any water at all. They all shared their water; and each one of the ring holders got G_i (G_1, G_2, G_3, ..., G_9) tiny nuggets of gold in return. Where W_1+W_2+...+W_9 = G_1+G_2+...+G_9.
However, the 18 W_i and G_i water droplet and gold nugget amounts, respectively, are all different and at least 17 of them are prime numbers.
Find the nine W_i's.

Solution

  • We first present Hao Zheng's solution (thanks, Hao!):

    Start with a set of prime numbers (for example, the first 60 primes) as the candidate pool for the water droplets and each time choose nine of these primes. The key is to filter the candidate pool first. Let S be the prime set of the first 60 primes. Here we use two steps to filter S. Let p1 be the smallest number from S and p2 be the 2nd smallest, and so on. We can safely eliminate p1=2. We must have p1> (p1+p2+...+p9)/10 or 10*p1>p1+p2+...+p9>p1+(p1+2*1)+(p1+2*2)+...+(p1+2*8) and this gives us p1>72. So the minimum prime of the set S is 73. 2. After applying the above step to filter the prime set, we end up with a new set. Let's still call it S and still assume p1 is the smallest, p2 is the 2nd smallest, and so on. We should still have
    p1> (p1+p2+...+p9)/10. If not, then we can remove p1 from S. Repeat this step until we cannot remove any more numbers from S.

    We end up with the following prime set: S = {191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281}
    So there are C(18,9) = 48620 different combinations of choosing 9 numbers from 18 numbers. It's fairly quick to verify these 48620 cases using a program.
    Here is one of the solutions: (w1, w2, w3, w4, w5, w6, w7, w8, w9) = (223, 227, 229, 233, 239, 251, 257, 277, 281) and (g1, g2, g3, g4, g5, g6, g7, g8, g9) = (13, 53, 73, 113, 173, 293, 353, 553, 593). These are all primes except 553.

    Oleg Vlasii (thanks!) sent us a nice solution, inspired by Trinity Hall Prime number:

    W_1 = 1111111111111111113989; G_1 = 1111111111111111139891;
W_2 = 1121222112111112113953; G_2 = 1212221121111121139531;
W_3 = 1121211212211122114003; G_3 = 1212112122111221140031;
W_4 = 1121211212211122113693; G_4 = 1212112122111221136931;
W_5 = 1121222112121212115303; G_5 = 1212221121212121153031;
W_6 = 1121211212121212118547; G_6 = 1212112121212121185471;
W_7 = 1121211212112112117037; G_7 = 1212112121121121170371;
W_8 = 1121222112112112113457; G_8 = 1212221121121121134571;
W_9 = 1040377703888884080017; G_9 = 0403777038888840800171.

    When focus on digits '2' we can see "IBM" in both W and G.

    Several of you found the wrong (but interesting) solution where the sum of G_i is one-fifth of the sum of W_i.

    WATERCONTRGOLD
    269 271 277 281 283 293 307 313 3316.5 8.5 14.5 18.5 20.5 30.5 44.5 50.5 68.513 17 29 37 41 61 89 101 137

    Amos Guler found a quite large solution: W = 53129 53171 53267 53309 53327 53411 53441 53591 103407 and G = 1237 1657 2617 3037 3217 4057 4357 5857 504017 where the only non-prime is W_9=103407.

    And Kipp Johnson found a nice way to convert a solution without the primality condition into a valid solution.

    The real story is about 19 (3+7+9) rings:
    "Three Rings for the Elven-kings under the sky,
    Seven for the Dwarf-lords in their halls of stone,
    Nine for Mortal Men doomed to die"
    So Radu-Alexandru Todor found a solution for all 19 rings holders:
    W = [6737, 6761, 6791, 6827, 6857, 6863, 6899, 6971, 6997, 7001, 7019, 7109, 7127, 7349, 7417, 7433, 7451, 7481, 7499] and
    G = [151, 631, 1231, 1951, 2551, 2671, 3391, 4831, 5351, 5431, 5791, 7591, 7951, 12391, 13751, 14071, 14431, 15031, 15391]
    All these numbers are prime.

Solvers

  • Daniel Chong Jyh Tar (30/07/18 02:03 PM IDT)
  • Andreas Eisele (30/07/18 03:29 PM IDT)
  • Noam Lasry (30/07/18 04:45 PM IDT)
  • Bert Dobbelaere (30/07/18 08:03 PM IDT)
  • Sean Egan (30/07/18 08:19 PM IDT)
  • Hao Zheng (30/07/18 10:28 PM IDT)
  • JJ Rabeyrin (31/07/18 12:36 AM IDT)
  • Harald Bögeholz (31/07/18 06:00 AM IDT)
  • Dong Lingyun, Alistair Ong & Ma Hongqiang (31/07/18 09:27 AM IDT)
  • Steven Langerwerf (31/07/18 10:18 AM IDT)
  • Alex Fleischer (31/07/18 10:55 AM IDT)
  • Reiner Martin (31/07/18 11:31 AM IDT)
  • Alper Halbutogullari (31/07/18 11:36 AM IDT)
  • Paul Shaw (31/07/18 12:30 PM IDT)
  • Thomas Egense (31/07/18 02:00 PM IDT)
  • Guillaume Escamocher (31/07/18 02:05 PM IDT)
  • Stijn Theunis (31/07/18 05:25 PM IDT)
  • Jordan Rinder (31/07/18 05:29 PM IDT)
  • Eden Saig (01/08/18 01:03 AM IDT)
  • Rickard Björklund (01/08/18 02:12 AM IDT)
  • Almog Yair (01/08/18 02:59 AM IDT)
  • Susanne Wienand (01/08/18 10:48 AM IDT)
  • Harold Gutch (01/08/18 12:34 PM IDT)
  • Alex Ang (01/08/18 04:26 PM IDT)
  • Keith Schneider (01/08/18 07:29 PM IDT)
  • Joseph Berman (01/08/18 08:25 PM IDT)
  • Nicolas Ayotte (01/08/18 08:57 PM IDT)
  • Loukas Sidiropoulos (02/08/18 12:37 AM IDT)
  • Vladimir Volevich (02/08/18 05:19 AM IDT)
  • Allen Zhu (02/08/18 05:56 AM IDT)
  • Amos Guler (02/08/18 10:08 AM IDT)
  • Graham Hemsley (02/08/18 11:01 AM IDT)
  • Dieter Beckerle (02/08/18 11:12 AM IDT)
  • David Greer (02/08/18 01:20 AM IDT)
  • Ali Can Keserel (02/08/18 05:17 PM IDT)
  • Anna Judith (02/08/18 079:07 PM IDT)
  • Pi-Ching Liu (03/08/18 12:43 AM IDT)
  • Shirish Chinchalkar (03/08/18 03:08 AM IDT)
  • Ian Sleightholme (03/08/18 03:31 PM IDT)
  • Prashant Wankhede (03/08/18 03:10 AM IDT)
  • Kang Jin Cho (03/08/18 08:56 PM IDT)
  • Francis Golding (03/08/18 06:43 PM IDT)
  • Andreas Stiller (03/08/18 11:24 PM IDT)
  • Sri Mallikarjun J (03/08/18 11:56 PM IDT)
  • Motty Porat (04/08/18 01:30 AM IDT)
  • Ricardo Koller (04/08/18 03:03 AM IDT)
  • Andreas Knüpfer (04/08/18 11:34 AM IDT)
  • Thomas Huet (04/08/18 03:48 PM IDT)
  • Raymond Lo (04/08/18 03:58 PM IDT)
  • Joaquim Neves Carrapa (04/08/18 04:00 PM IDT)
  • Parth Trivedi (04/08/18 04:38 PM IDT)
  • Armin Krauß (04/08/18 04:54 PM IDT)
  • Michael Liepelt (04/08/18 10:10 PM IDT)
  • Todd Will (04/08/18 11:02 PM IDT)
  • Kipp Johnson (04/08/18 11:54 PM IDT)
  • Emir Haleva (05/08/18 12:33 AM IDT)
  • David F.H. Dunkley (05/08/18 10:30 AM IDT)
  • Tyler Mullen (05/08/18 12:00 PM IDT)
  • Mathias Schenker (05/08/18 01:35 PM IDT)
  • Daniel Bitin (05/08/18 02:52 PM IDT)
  • Ritesh Ranjan (05/08/18 05:44 PM IDT)
  • Florian Fischer (05/08/18 06:42 PM IDT)
  • Shouky Dan & Tamir Ganor (05/08/18 09:39 PM IDT)
  • Fabio Michele Negroni (05/08/18 10:21 PM IDT)
  • Zhang Dingwen (06/08/18 11:27 AM IDT)
  • Rustam Salikhov (06/08/18 02:54 PM IDT)
  • Brian Pietsch (06/08/18 03:47 PM IDT)
  • Joseph DeVincentis (06/08/18 03:52 PM IDT)
  • Marcel Caria (06/08/18 05:01 PM IDT)
  • Adrian Neacsu (06/08/18 05:57 PM IDT)
  • Lavanya Kannan (06/08/18 06:06 PM IDT)
  • Gale Greenlee (07/08/18 12:44 AM IDT)
  • Soumitra Agarwal (07/08/18 08:54 AM IDT)
  • Clive Tong (07/08/18 01:03 PM IDT)
  • Luke Pebody (08/08/18 03:30 PM IDT)
  • Rachit Srivastava (08/08/18 08:17 PM IDT)
  • Andrejs Pilka (09/08/18 09:00 AM IDT)
  • Arthur Vause (09/08/18 04:02 PM IDT)
  • Davin Choo (11/08/18 09:50 AM IDT)
  • Amaury Garrec (11/08/18 01:24 PM IDT)
  • Hugo Pfoertner (11/08/18 09:37 PM IDT)
  • Kurt Foster (11/08/18 09:42 PM IDT)
  • Lakshman inkulu (12/08/18 03:19 PM IDT)
  • Danny Antonetti (12/08/18 08:15 PM IDT)
  • Robert Lang (13/08/18 09:59 AM IDT)
  • Chuck Carroll (13/08/18 01:38 PM IDT)
  • Ehud Aharoni & Omri Soceanu (14/08/18 05:00 PM IDT)
  • Siddhartha Srivastava (14/08/18 05:17 PM IDT)
  • Boris Rakus (15/08/18 04:49 PM IDT)
  • Charles Joscelyne (15/08/18 06:39 PM IDT)
  • Dominik Reichl (15/08/18 08:25 PM IDT)
  • Tilo Anschütz (16/08/18 11:43 AM IDT)
  • Yuxuan Shui (17/08/18 07:56 PM IDT)
  • Li Li (18/08/18 08:16 PM IDT)
  • Franciraldo Cavalcante (19/08/18 06:38 PM IDT)
  • Hanlin Ren (20/08/18 04:09 PM IDT)
  • Alexander Raß (20/08/18 04:25 PM IDT)
  • Feyzullah Egriboyun (21/08/18 01:23 AM IDT)
  • Mehmet Saruhan (21/08/18 09:21 AM IDT)
  • Stephane Vaillant (21/08/18 04:49 PM IDT)
  • Heidi Stockton (23/08/18 06:56 PM IDT)
  • Oscar Volpatti (24/08/18 07:03 PM IDT)
  • Sergey Koposov (25/08/18 02:14 AM IDT)
  • Sergey Subbotin (25/08/18 04:53 PM IDT)
  • Lorenz Reichel (25/08/18 11:26 PM IDT)
  • Nathaniel Litton (27/08/18 12:51 AM IDT)
  • Mykola Zubach (27/08/18 09:04 AM IDT)
  • Xiao Liu (28/08/18 05:30 AM IDT)
  • Jimmy Waters (28/08/18 06:30 PM IDT)
  • Atul Gupta (28/08/18 09:36 PM IDT)
  • Daniel Son (30/08/18 08:17 PM IDT)
  • Paolo Farinelli (30/08/18 10:05 PM IDT)
  • Oleg Vlasii (31/08/18 10:06 AM IDT)
  • Muralidhar Seshadri (31/08/18 11:21 PM IDT)
  • Radu-Alexandru Todor (01/09/18 01:53 AM IDT)
  • itsik horovitz (01/09/18 10:55 PM IDT)

Related posts