/* 30 bottles problem in Picat. From Alcuins via Paul Vaderlind "Klassisk Nöjesmatematik", 2003, page 38 ("Classical Recreational Mathematics") """ A man died and left 30 bottles to his 3 sons. 10 bottles was filled with oil, 10 was half full with oil, and 10 was empty. The wish of the man was that all the sons should get the same amount of bottles and the same amount of oil. How to distribute bottles and oil in a fair way if it's not allowed to pour oil from one bottle to another. How many solutions are there? """ For 3 sons, [10,10,10] bottles with oil distributed as [1,1/2,0] there are 5 solutions (with symmetry breaking). Each row is the number of bottles of each type per son: [0,10,0] [5,0,5] [5,0,5] [1,8,1] [4,2,4] [5,0,5] [2,6,2] [3,4,3] [5,0,5] [2,6,2] [4,2,4] [4,2,4] [3,4,3] [3,4,3] [4,2,4] For the distributions [1,1/2,0] the number of solutions for A bottles ([A,A,A], i.e. the same number of bottles of each type) between 1 and 20: 0,1,1,2,1,3,2,4,3,5,4,7,5,8,7,10,8,12,10,14 which is the following integer sequence: https://oeis.org/A005044 """ Alcuin's sequence: expansion of x^3/((1-x^2)*(1-x^3)*(1-x^4)). 0, 0, 0, 1, 0, 1, 1, 2, 1, 3, 2, 4, 3, 5, 4, 7, 5, 8, 7, 10, ... With a different offset (i.e., without the three leading zeros, as in A266755), the number of ways in which n empty casks, n casks half-full of wine and n full casks can be distributed to 3 persons in such a way that each one gets the same number of casks and the same amount of wine [Alcuin]. E.g., for n=2 one can give 2 people one full and one empty and the 3rd gets two half-full. """ Without the symmetry breaking the number of solutions are 0,3,1,6,3,10,6,15,10,21,15,28,21,36,28,45,36,55,45,66 which is identified as https://oeis.org/A008795 """ Molien series for 3-dimensional representation of dihedral group D_6 of order 6. ... a(n-3) is the number of ordered triples of positive integers which are the side lengths of a nondegenerate triangle of perimeter n. - Rob Pratt, Jul 12 2004 a(n) is the number of ways to distribute n identical objects into 3 distinguishable bins so that no bin contains an absolute majority of objects. - Geoffrey Critzer, Mar 17 2010 ... a(n) is the number of coins left after packing 3-curves coins patterns into fountain of coins base n. Refer to A005169: "A fountain is formed by starting with a row of coins, then stacking additional coins on top so that each new coin touches two in the previous row". See illustration in links. - Kival Ngaokrajang, Oct 12 2013 """ For NumSons = 4 (and the same distributions [1,1/2,0] and [A,A,A] bottles there are solutions for the following values of A (A in 1..20) 4, 8, 12, 20, The total number of solutions for A in 1..20: 0,0,0,1,0,0,0,4,0,0,0,5,0,0,0,13,0,0,0,14 [Not in OEIS] Here are the 4 solutions for A=8 (8 bottles of each type): [0,6,0] [2,2,2] [3,0,3] [3,0,3] [1,4,1] [1,4,1] [3,0,3] [3,0,3] [1,4,1] [2,2,2] [2,2,2] [3,0,3] [2,2,2] [2,2,2] [2,2,2] [2,2,2] For NumSons=5, there are solutions for the following number of bottles (of each type). 5,10,15,20, 0,0,0,0,1,0,0,0,0,5,0,0,0,0,6,0,0,0,0,23 Here are the 5 solutions for A=10 [0,6,0] [1,4,1] [3,0,3] [3,0,3] [3,0,3] [0,6,0] [2,2,2] [2,2,2] [3,0,3] [3,0,3] [1,4,1] [1,4,1] [2,2,2] [3,0,3] [3,0,3] [1,4,1] [2,2,2] [2,2,2] [2,2,2] [3,0,3] [2,2,2] [2,2,2] [2,2,2] [2,2,2] [2,2,2] For NumSons=6 there are solutions for the following A: 4,6,8,10,12,14,16,18,20 The total number of solutions: 0,0,0,1,0,1,0,3,0,2,0,7,0,4,0,13,0,9,0,23 [Not in OEIS] This program was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import util. import cp. % import sat. main => go. /* The original problem instance number of bottles: [10,10,10] types : [1,1/2,0] -> [2,1,0] number of sons : 3 */ go => B = [10,10,10], % Number of bottles of each type T = [2,1,0], % Amount of oil in each bottle [1,1/2,0] -> [2,1,0] NumSons = 3, Sols = findall(X,distribute_bottles(B,T,NumSons, X)), foreach(Sol in Sols) foreach(Row in Sol) println(Row.to_list) end, nl end, println(num_sols=Sols.len), nl. /* Checking the solutions (and the number of solutions) for a generalized version: - the distribution of the three bottle types are the same ([1,1/2,0] -> [2,1,0]) - the number of bottles of each type is [A,A,A] for A in 1..20 - there are 3 sons */ go2 => nolog, NumSols = [], foreach(A in 1..20) println(a=A), B = [A,A,A], % Number of bottles of each type T = [2,1,0], % Amount of oil in each bottle [1,1/2,0] -> [2,1,0] NumSons = 3, Sols = findall(X,distribute_bottles(B,T,NumSons, X)), foreach(Sol in Sols) foreach(Row in Sol) println(Row.to_list) end, nl end, println(len=Sols.len), NumSols := NumSols ++ [Sols.len], nl end, println(NumSols), nl. /* Vaderlind (op cit, page 40): """ Problem 15 How to distribute 5 full, 8 half-full, and 11 empty bottles of wine between three persons if each person get the same number of bottles and the same amout of wine. Find all solutions. """ And some additional problems (Vaderlind, op.cit, page 215): """ Also, try to solve a similar puzzle, this time with 5 full, 11 half-full, and 8 empty bottles (three solutions) and 11 full, 5 half-full, and 8 empty bottles (one solution) """ Here are the solutions for all 6 permutations of [5,8,11] (including the original problem instance from page 40): b = [5,8,11] tot_oil = 18 tot_bottles = 24 [0,6,2] [2,2,4] [3,0,5] [1,4,3] [1,4,3] [3,0,5] [1,4,3] [2,2,4] [2,2,4] len = 3 b = [8,5,11] tot_oil = 21 tot_bottles = 24 [2,3,3] [3,1,4] [3,1,4] len = 1 b = [8,11,5] tot_oil = 27 tot_bottles = 24 [1,7,0] [3,3,2] [4,1,3] [2,5,1] [2,5,1] [4,1,3] [2,5,1] [3,3,2] [3,3,2] len = 3 b = [5,11,8] tot_oil = 21 tot_bottles = 24 [0,7,1] [2,3,3] [3,1,4] [1,5,2] [1,5,2] [3,1,4] [1,5,2] [2,3,3] [2,3,3] len = 3 b = [11,5,8] tot_oil = 27 tot_bottles = 24 [3,3,2] [4,1,3] [4,1,3] len = 1 b = [11,8,5] tot_oil = 30 tot_bottles = 24 [2,6,0] [4,2,2] [5,0,3] [3,4,1] [3,4,1] [5,0,3] [3,4,1] [4,2,2] [4,2,2] len = 3 */ go3 => nolog, T = [2,1,0], % Amount of oil in each bottle [1,1/2,0] -> [2,1,0] NumSons = 3, Bs = permutations([5,8,11]), % Number of bottles of each type foreach(B in Bs) println(b=B), Sols = findall(X,distribute_bottles(B,T,NumSons, X)), foreach(Sol in Sols) foreach(Row in Sol) println(Row.to_list) end, nl end, println(len=Sols.len), nl end, nl. /* Vaderlind, op.cit. page 40 """ Problem 16 How can 9 containers which contains 1,2,3,4,5,6,7,8,and 9 liter wine be distributed between three persons such that each person get three containers and the same amount of wine. Determine all solutions. It is not allowed to pour over wine from one container to another """ Here are the two solutions: [0,0,1,1,0,0,0,1,0] [0,1,0,0,0,1,1,0,0] [1,0,0,0,1,0,0,0,1] [0,0,1,0,1,0,1,0,0] [0,1,0,1,0,0,0,0,1] [1,0,0,0,0,1,0,1,0] I.e. a) p1: 3, 5, 7 p2: 2, 4, 9 p3: 1, 6, 8 b) p1: 3, 4, 8 p2: 2, 6, 7 p3: 1, 5, 9 (At page 215, Vaderlind notices that these two solutions are magic squares of order 3.) */ go4 => nolog, B = [1,1,1,1,1,1,1,1,1], % Number of bottles T = [1,2,3,4,5,6,7,8,9], % Amount of oil in each bottle NumSons = 3, Sols = findall(X,distribute_bottles(B,T,NumSons, X)), foreach(Sol in Sols) foreach(Row in Sol) println(Row.to_list=[I : I in 1..T.len, Row[I] == 1]) end, nl end, println(len=Sols.len), nl. /* Generalized version of go4/0. */ go4b => nolog, N = 18, B = [1 : _ in 1..N], % Number of bottles T = 1..N, % Amount of oil in each bottle NumSons = 3, Sols = findall(X,distribute_bottles(B,T,NumSons, X)), foreach(Sol in Sols) foreach(Row in Sol) println(Row.to_list=[I : I in 1..T.len, Row[I] == 1]) end, nl end, println(len=Sols.len), nl. /* Random instances 1) Random number of types of bottles (N) 2) Random ratios of oil (integer) (T) 3) Random number of bottles for each type (B) 4) Random number of sons (NumSons) Some configurations with solutions that was found: * [n = 6,t = [3,5,6,6,7,9],b = [9,8,8,5,2,1],num_sons = 3] 199 solutions * [n = 6,t = [0,5,7,9,9,10],b = [10,8,7,2,2,1],num_sons = 3] 12 solutions * [n = 6,t = [3,3,7,8,9,10],b = [10,10,7,7,5,3],num_sons = 3] 1160 solutions */ go5 => nolog, _ = random2(), N = random(3,3), T = [random(0,15) : _ in 1..N].sort_down, % Ratio of oil in each bottle B = [random(5,20) : _ in 1..N].sort_down, % Number of bottles of each type NumSons = random(4,5), println([n=N,t=T,b=B,num_sons=NumSons]), Sols = findall(X,distribute_bottles(B,T,NumSons, X)), foreach(Sol in Sols) foreach(Row in Sol) println(Row.to_list) end, nl end, println(len=Sols.len), nl. distribute_bottles(B,T,NumSons, X) => N = B.len, TotOil = sum([T[I]*B[I] : I in 1..N]), println(tot_oil=TotOil), TotBottles = sum(B), println(tot_bottles=TotBottles), M = T.len, X = new_array(NumSons,M), X :: 0..TotOil, foreach(S in 1..NumSons) % Total number of bottles per son NumSons*sum([X[S,J] : J in 1..N]) #= TotBottles, % Same amount of oil per son NumSons*sum([X[S,J]*T[J] : J in 1..N]) #= TotOil, if S < NumSons then lex_le(X[S],X[S+1]) % symmetry breaking end end, % Total number of bottles for each bottle type foreach(J in 1..N) sum([X[S,J] : S in 1..NumSons]) #= B[J] end, solve($[degree,updown],X).