Kitonum

21123 Reputation

26 Badges

16 years, 211 days

MaplePrimes Activity


These are Posts that have been published by Kitonum

This post - this is a generalization of the question from  here .
Suppose we have  m  divisible objects that need to be divided equally between n persons, and so that the total number of parts (called  N  in the text of the procedure) after cutting should be a minimum. Cutting procedure exactly solves this problem. It can be proved that the estimate holds  n<=N<=n+m-1, and  N<n+m-1 if and only if there are several objects (< m), whose measures sum to be a multiple of the share (Obj in the text of the procedure).

In the attached file you can find also the text of the second procedure Cutting1, which is approximately solves the problem. The procedure Cutting1 is much faster than Cutting. But the results of their work are usually the same or Cutting procedure gives a slightly better result than Cutting1.

Required parameters of the procedure: L is the list of the measures of the objects to be cutted, n is the number of persons. The optional parameter  Name is a name or the list of names of the objects of L (if the latter then should be nops(L)=nops(Name) ).

 

Cutting:=proc(L::list(numeric), n::posint, Name::{name,list(name)}:=Object)

local m, n1, L1, L11, mes, Obj, It, M, N;

uses combinat, ListTools;

m:=nops(L); L1:=sort([seq([`if`(Name::name,Name||i,Name[i]),L[i]], i=1..m)], (a,b)->a[2]<=b[2]);

mes:=table(map(t->t[1]=t[2],L1));

Obj:=`+`(L[])/n;

It:=proc(L1, n)

local i, M, m1, S, n0, a, L2;

if nops(L1)=1 then return [[[L1[1,1],Obj]] $ n] fi;

if n=1 then return [L1] fi;

for i from 1 while `+`(seq(L1[k,2],k=1..i))<=Obj do

od;

M:=[seq(choose(L1,k)[], k=1..ceil(nops(L1)/2))];

S:=[];

for m1 in M while nops(S)=0 do n0:=`+`(seq(m1[k,2],k=1..nops(m1)))/Obj;

if type(n0,integer) then S:=m1 fi;

od;

if nops(S)=0 then

a:=Obj-`+`(seq(L1[k,2],k=1..i-1));

L2:=[[L1[i,1],L1[i,2]-a],seq(L1[k],k=i+1..nops(L1))];

 [[seq(L1[k], k=1..i-1),`if`(a=0,NULL,[L1[i,1],a])],It(L2,n-1)[]] else L2:=sort(convert(convert(L1,set) minus convert(S,set), list),(a,b)->a[2]<=b[2]);

[It(S,n0)[], It(L2,n-n0)[]] fi;

end proc;

M:=It(L1,n);

N:=add(nops(M[i]), i=1 ..nops(M));

Flatten(M, 1);

[Categorize((a,b)->a[1]=b[1],%)];

print(``);

print(cat(`Cutting scheme (total  `, N, `  parts):`) );

print(map(t->[seq(t[k,2]/`+`(seq(t[k,2],k=1..nops(t)))*t[1,1],k=1..nops(t))], %)[]);

print(``);

print(`Scheme of sharing out:`);

seq([Person||k,`+`(seq(M[k,i,2]/mes[M[k,i,1]]*M[k,i,1], i=1..nops(M[k])))],k=1..n);

end proc:

 

Examples of use.

First example from the link above:

Cutting([225,400,625], 4, Cake);  # 3 cakes must be equally divided by 4 persons

eval(%,[Cake1,Cake2,Cake3]=~[225,400,625]);  # Check

          

 

 

 

Second example (the same for 10 persons):

Cutting([225,400,625], 10, Cake);

        

 

 

Third example (7 identical apples should be divided between 12 persons):

Cutting([1 $ 7], 12, apple); 

 

 

Cutting.mw

 

 Edited:

1. Fixed a bug in the procedure Cutting  (I forgot sort the list  L2  in sub-procedure  It  if  nops(S)<>0 ).

2. Changes made to the sub-procedure  It  for the case if there are several objects (>1  and  < m), whose measures                     sum to be a multiple of the share  Obj .

 

We assume that the radius of the outer stationary circle is  1. If we set the radius  x  of the inner stationary circle, all the other circles are uniquely determined by solving the system Sys.  Should be  x<=1/3 . If  x=1/3  then all the inner circles have a radius  1/3 . The following picture explains the meaning of symbols in the procedure Circles:

                                   

 

 

Circles:=proc(x)

local OO, O1, O2, O3, O4, O2x, O2y, O3x, O3y, OT, T1, T2, T3, s, t, dist, Sys, Sol, sol, y, u, v, z, C0, R0, P;

uses plottools, plots;

OO:=[0,0]: O1:=[x+y,0]: O2:=[O2x,O2y]: O3:=[O3x,O3y]: O4:=[-x-z,0]: OT:=[x+2*y-1,0]:

T1:=(O2*~y+O1*~u)/~(y+u): T2:=(O3*~u+O2*~v)/~(u+v): T3:=(O4*~v+O3*~z)/~(v+z):

solve({(T2-T1)[1]*(s-((T1+T2)/2)[1])+(T2-T1)[2]*(t-((T1+T2)/2)[2])=0, (T3-T2)[1]*(s-((T2+T3)/2)[1])+(T3-T2)[2]*(t-((T3+T2)/2)[2])=0}, {s,t}):

assign(%);

dist:=(A,B)->sqrt((B[1]-A[1])^2+(B[2]-A[2])^2):

Sys:={dist(O1,O2)^2=(y+u)^2, dist(OO,O2)^2=(x+u)^2, dist(O2,O3)^2=(u+v)^2, dist(OO,O3)^2=(x+v)^2, dist(O3,O4)^2=(z+v)^2, x+y+z=1, dist(O2,OT)^2=(1-u)^2, dist(O3,OT)^2=(1-v)^2};

Sol:=op~([allvalues([solve(Sys)])]);

sol:=select(i->is(eval(convert([y>0,u>0,v>0,z>0,O2y>0,x<=y,u<=y,v<=u,z<=v],`and`),i)), Sol)[];

assign(sol);

O1:=[x+y,0]: O2:=[O2x,O2y]: O3:=[O3x,O3y]: O4:=[-x-z,0]: OT:=[x+2*y-1,0]:

C0:=eval([s,t],sol);

R0:=eval(dist(T1,C0),sol):

P:=proc(phi)

local eq, r1, r, R, Ot, El, i, S, s, t, P1, P2;

uses plots,plottools;

eq:=1-dist([r*cos(s),r*sin(s)],OT)=r-x;

r1:=solve(eq,r);

r:=eval(r1,s=phi);

R[1]:=evalf(r-x);

Ot[1]:=evalf([r*cos(phi),r*sin(phi)]);

El:=plot([r1*cos(s),r1*sin(s),s=0..2*Pi],color="Green",thickness=3);

for i from 2 to 6 do

S:=[solve({1-dist(OT,[s,t])=dist(Ot[i-1],[s,t])-R[i-1], 1-dist(OT,[s,t])=dist(OO,[s,t])-x})];

P1:=eval([s,t],S[1]); P2:=eval([s,t],S[2]);

Ot[i]:=`if`(evalf(Ot[i-1][1]*P1[2]-Ot[i-1][2]*P1[1])>0,P1,P2);

R[i]:=dist(Ot[i],OO)-x;

od;

display(El,seq(disk(Ot[k],0.012),k=1..6),circle(C0,R0,color=gold,thickness=3),circle([x+2*y-1,0],1, color=blue,thickness=4), circle(OO,x, color=red,thickness=4), seq(circle(Ot[k],R[k], thickness=3),k=1..6), scaling=constrained, axes=none);

end proc:

animate(P,[phi], phi=0..Pi, frames=120);

end proc:  

 

Example of use (I got  x=0.22  just by measuring the ruler displayed original animation):

Circles(0.22);

                               

 

 

The curve on the following animation is an astroid (a special case of hypocycloid). See wiki for details. Hypocycloid procedure creates animation for any hypocycloid.  Parameters of the procedure: R is the radius of the outer circle, r is the radius of the inner circle.

Hypocycloid:=proc(R,r)

local A, B, f, g, F;

uses plots,plottools;

A:=circle(R,color=green,thickness=4):

B:=display(circle([R-r,0],r,color=red,thickness=4),line([R-r,0],[R,0],color=red,thickness=4)):

f:=t->plot([(R-r)*cos(s)+r*cos((R-r)/r*s),(R-r)*sin(s)-r*sin((R-r)/r*s),s=0..t],color=blue,thickness=4):

g:=t->rotate(rotate(B,-R/r*t,[R-r,0]),t):

F:=t->display(A,f(t),g(t),scaling=constrained):

animate(F,[t], t=0..2*Pi*denom(R/r), frames=90);

end proc:

 

Examples of use:

Hypocycloid(4,1); 

                                      

 

 

Hypocycloid(5,3);

                                      

 

 

 Круги.mw

IntegerPoints2  procedure generalizes  IntegerPoints1  procedure and finds all the integer points inside a bounded curved region of arbitrary dimension.  We also use a brute force method, but to find the ranges for each variable  Optimization[Minimize]  and   Optimization[Maximize]  is used instead of  simplex[minimize]  or  simplex[minimize] .

Required parameters of the procedure: SN is a set or a list of  inequalities and/or equations with any number of variables, the Var is the list of variables. Bound   is an optional parameter - list of ranges for each variable in the event, if  Optimization[Minimize/Maximize]  fails. By default  Bound  is NULL.

If all constraints are linear, then in this case it is recommended to use  IntegerPoints1  procedure, as it is better to monitor specific cases (no solutions or an infinite number of solutions for an unbounded region).

Code of the procedure:

IntegerPoints2 := proc (SN::{list, set}, Var::(list(symbol)), Bound::(list(range)) := NULL)

local SN1, sn, n, i, p, q, xl, xr, Xl, Xr, X, T, k, t, S;

uses Optimization, combinat;

n := nops(Var);

if Bound = NULL then

SN1 := SN;

for sn in SN1 do

if type(sn, `<`) then

SN1 := subs(sn = (`<=`(op(sn))), SN1) fi od;

for i to n do

p := Minimize(Var[i], SN1); q := Maximize(Var[i], SN1);

xl[i] := eval(Var[i], p[2]); xr[i] := eval(Var[i], q[2]) od else

assign(seq(xl[i] = lhs(Bound[i]), i = 1 .. n));

assign(seq(xr[i] = rhs(Bound[i]), i = 1 .. n)) fi;

Xl := map(floor, convert(xl, list)); Xr := map(ceil, convert(xr, list));

X := [seq([$ Xl[i] .. Xr[i]], i = 1 .. n)];

T := cartprod(X); S := table();

for k while not T[finished] do

t := T[nextvalue]();

if convert(eval(SN, zip(`=`, Var, t)), `and`) then

S[k] := t fi od;

convert(S, set);

end proc:

 

In the first example, we find all the integer points in the four-dimensional ball of radius 10:

Ball := IntegerPoints2({x1^2+x2^2+x3^2+x4^2 < 10^2}, [x1, x2, x3, x4]):  # All the integer points

nops(Ball);  # The total number of the integer points

seq(Ball[1000*n], n = 1 .. 10);  # Some points

                                                                    48945

                  [-8, 2, 0, -1], [-7, 0, 1, -3], [-6, -4, -6, 2], [-6, 1, 1, 1], [-5, -6, -2, 4], [-5, -1, 2, 0],

                                [-5, 4, -6, -2], [-4, -5, 1, 5], [-4, -1, 6, 1], [-4, 3, 5, 6]

 

 

In the second example, with the visualization we find all the integer points in the inside intersection of  a cone and a cylinder:

A := <1, 0, 0; 0, (1/2)*sqrt(3), -1/2; 0, 1/2, (1/2)*sqrt(3)>:  # Matrix of rotation around x-axis at Pi/6 radians

f := unapply(A^(-1) . <x, y, z-4>, x, y, z):  

S0 := {4*x^2+4*y^2 < z^2}:  # The inner of the cone

S1 := {x^2+z^2 < 4}:  # The inner of the cylinder

S2 := evalf(eval(S1, {x = f(x, y, z)[1], y = f(x, y, z)[2], z = f(x, y, z)[3]})):

S := IntegerPoints2(`union`(S0, S2), [x, y, z]);  # The integer points inside of the intersection of the cone and the rotated cylinder

Points := plots[pointplot3d](S, color = red, symbol = solidsphere, symbolsize = 8):

Sp := plot3d([r*cos(phi), r*sin(phi), 2*r], phi = 0 .. 2*Pi, r = 0 .. 5, style = surface, color = "LightBlue", transparency = 0.7):

F := plottools[transform]((x, y, z)->convert(A . <x, y, z>+<0, 0, 4>, list)):

S11 := plot3d([2*cos(t), y, 2*sin(t)], t = 0 .. 2*Pi, y = -4 .. 7, style = surface, color = "LightBlue", transparency = 0.7):

plots[display]([F(S11), Sp, Points], scaling = constrained, orientation = [25, 75], axes = normal);

      

 

 

In the third example, we are looking for the integer points in a non-convex area between two parabolas. Here we have to specify ourselves the ranges to enumeration (Optimization[Minimize] command fails for this example):

P := IntegerPoints2([y > (-x^2)*(1/2)+2, y < -x^2+8], [x, y], [-4 .. 4, -4 .. 8]);

A := plots[pointplot](P, color = red, symbol = solidcircle, symbolsize = 10):

B := plot([(-x^2)*(1/2)+2, -x^2+8], x = -4 .. 4, -5 .. 9, color = blue):

plots[display](A, B, scaling = constrained);

     

 

 IntegerPoints2.mw

 

This post is my attempt to answer the question from   here : how to find all integer points (all points with integer coordinates) in the intersection of two cubes. The following procedure  IntegerPoints  solves a more general problem: it finds all the integer points of a bounded polyhedral region of arbitrary dimension, defined by a system of linear inequalities and / or equations.

Required parameters of the procedure: SN is a set or a list of linear inequalities and/or equations with any number of variables, the Var is the list of variables. The procedure returns the set of all integer points, satisfying the conditions  SN .

Code of the procedure:

restart;

IntegerPoints := proc (SN::{list, set}, Var::list)

local SN1, sn, n, Sol, k, i, s, S, R;

uses PolyhedralSets, SolveTools[Inequality];

SN1 := convert(evalf(SN), fraction);

for sn in SN1 do

if type(sn, `<`) then SN1 := subs(sn = (`<=`(op(sn))), SN1)

end if; end do;

if IsBounded(PolyhedralSet(SN1)) = false then error "The region should be bounded" end if;

n := nops(Var);

Sol := LinearMultivariateSystem(SN, Var);

if Sol = {} then return {} else

k := 0;

for s in Sol do if nops(indets(s[1])) = 1 then

S[0] := [[]];

for i to n do

S[i] := [seq(seq([op(j1), op(j2)], j2 = [isolve(eval(s[i], j1))]), j1 = S[i-1])] end do;

k := k+1; R[k] := op(S[n]);

end if; end do;

convert(R, set);

map(t->rhs~(t), %);

end if;

end proc:

 

Examples of use:

IntegerPoints({x > 0, y > 0, z > 0, 2*x+3*y+z < 12}, [x, y, z]);

       

  {[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 1, 4], [1, 1, 5], [1, 1, 6], [1, 2, 1], [1, 2, 2], [1, 2, 3], [2, 1, 1], [2, 1, 2],

                                   [2, 1, 3], [2, 1, 4], [2, 2, 1], [3, 1, 1], [3, 1, 2]}

 

IntegerPoints({x > 0, y > 0, z > 0, 2*x+3*y+z = 12}, [x, y, z]);

                                    {[1, 1, 7], [1, 2, 4], [1, 3, 1], [2, 1, 5], [2, 2, 2], [3, 1, 3], [4, 1, 1]}

 

IntegerPoints([x > 0, y > 0, z > 0, 2*x+3*y+z = 12, x+y+z <= 6], [x, y, z]);

                                                           {[1, 3, 1], [2, 2, 2], [4, 1, 1]}

isolve({x > 0, y > 0, z > 0, 2*x+3*y+z < 12});  #  isolve fails with these examples

              Warning, solutions may have been lost

isolve({x > 0, y > 0, z > 0, 2*x+3*y+z = 12});

              Warning, solutions may have been lost

 

In the following example (with a visualization) we find all integer point in the intersection of a square and a triangle:

S1 := {x > 0, y > 0, x < 13/2, y < 13/2}:

S2 := {y > (1/4)*x+1, y < 2*x, y+x < 12}:

S := IntegerPoints(`union`(S1, S2), [x, y]):

Region := plots[inequal](`union`(S1, S2), x = 0 .. 7, y = 0 .. 7, color = "LightGreen", nolines):

Points := plot([op(S)], style = point, color = red, symbol = solidcircle):

Square := plottools[curve]([[0, 0], [13/2, 0], [13/2, 13/2], [0, 13/2], [0, 0]], color = blue, thickness = 3):

Triangle := plottools[curve]([[4/7, 8/7], [4, 8], [44/5, 16/5], [4/7, 8/7]], color = blue, thickness = 3):

plots[display](Square, Triangle, Points, Region, scaling = constrained);

                                           

 

 

In the following example (with a visualization) we find all integer point in the intersection of two cubes. The second cube is obtained from the first cube by rotation with orthogonal matrix  A  and by a translation:

A := <1/3, 2/3, 2/3; -2/3, 2/3, -1/3; -2/3, -1/3, 2/3>:

f := unapply(A^(-1).<x+5, y-4, z-7>, x, y, z):

S1 := {x > 0, y > 0, z > 0, x < 6, y < 6, z < 6}:

S2 := eval(S1, {x = f(x, y, z)[1], y = f(x, y, z)[2], z = f(x, y, z)[3]}):

S := IntegerPoints(`union`(S1, S2), [x, y, z]);

Points := plots[pointplot3d](S, color = red, symbol = box):

Cube := plottools[cuboid]([0, 0, 0], [6, 6, 6], color = blue, linestyle = solid):

F := plottools[transform]((x, y, z)->convert(A.<x, y, z>+<-5, 4, 7>, list)):

plots[display](Cube,  F(Cube), Points, scaling = constrained, linestyle = solid, transparency = 0.7, orientation = [25, 75], axes = normal);

 

 

 

In the example below, all the ways to exchange $ 1 coins of 1, 5, 10, 25 and 50 cents, if the number of coins no more than 8, there is no pennies and there is at least one 50-cent coin:

IntegerPoints({x1 = 0, x2 >= 0, x3 >= 0, x4 >= 0, x5 >= 1,  x1+5*x2+10*x3+25*x4+50*x5 = 100, x1+x2+x3+x4+x5 <= 8}, [x1, x2, x3, x4, x5]);

nops(%);

                              {[0, 0, 0, 0, 2], [0, 0, 0, 2, 1], [0, 0, 5, 0, 1], [0, 1, 2, 1, 1], [0, 2, 4, 0, 1],

                                                 [0, 3, 1, 1, 1], [0, 4, 3, 0, 1], [0, 5, 0, 1, 1]}

                                                                                    8

 

Integer_points.mw

 

Addition: Below in my comments another procedure  IntegerPoints1  is presented that solves the same problem.

Consider the well-known Euler's formula  

 eix = cos x + i sin x   

When we calculate that for  x = π  we get:

eiπ = cos π + i sin π   or

eiπ = −1 + i × 0   (because cos π = −1 and sin π = 0)  or

eiπ = −1  or  eiπ + 1 = 0

It seems absolutely magical that such a neat equation combines  5  fundamental constants: e ,  i ,  π , 1 , 0

The purpose of this post - to give a simple visualization of equality  eiπ = −1  (statical and animated) by expanding  eiπ  in a series of complex numbers. These numbers we represent as vectors in the plane. We will see that the partial sums of this series are broken lines like a spiral, twisting around the point -1 steadily approaching to it.

Euler procedure has one required parameter  n is positive integer - the number of displayed terms of the series  for  eiπ  

Optional parameter  a  is any symbol (by default  a=NULL). We use this option if  instead of a static spiral want to see an animated spiral. 

Procedure code can be found in the attached file  Euler.mw

 

Examples of use.

The first example shows  8 terms of the series (broken line of 8 units):

Euler(8);

                

 

 

The terms of the series where  n> = 10  on the same plot can not be seen as very small. In this case, we use  the second plot with magnification of  100 : 1 .  

The second example:

Euler(14);

 

 

 

In the third example, we see an animated broken line. It's  first 9 units represented  on the left plot, and then for n> = 10 on the right plot:

Euler(13, a);

  

 

Euler.mw

3 4 5 6 7 8 9 Page 5 of 12