Newsgroup sci.math.num-analysis 29201

Directory

Hello out there,
	I have a problem for you which I and my
fellow students could not solve. Presented by my High
School Engineering class, it concerns a Carvel Puzzle
Toy. Read on...
Most of you know the puzzle im talking about, it is a square
of 4x4 with 15 little tabs in it and a blank space. The goal
is to get the tabs in numerical sequence from the top left,
1,2,3,4 etc onto 15, and finally the blank space ends up in
the bottom right hand corner. 
Here is my problem:
If the tabs are already in numerical sequence (already solved),
is it possible to reverse the positions of the 1 and 2 while the
remaining tabs remain in sequence? Example:
1     2     3     4                            2     1     3     4
5     6     7     8                            5     6     7     8
9    10   11    12                           9    10   11    12
13  14   15     X                            13  14   15     X
This is the solved                        This is what I have
version.                                       to get.
Is it possible to reverse the 1 and 2? Well, attempted to calculate
a system, based on the factor of 4, to find a relation between the 
solved version and any other version. Based on the binary tree method,
we couldn't do it. Any help would be appreciated.
We also calculated, that if we used a computer with simple IF
statements, that it would take about a second to calculate 1
possiblity, and 665,000 years to calculate all possibilities. My hope
is that one of you can do it within a post. Thanks :)

PLEASE REMOVE ME FROM YOUR DISTRIBUTION LIST.
THANK YOU.

~~~ VACANCY FOR AN ENVIRONMENTAL MODELLER (TWO YEAR RESEARCH POSITION) 
~~~
ZENECA Agrochemicals is a successful international business, with several 
thousand employees in Research and Development world-wide.  We have two 
main Research sites, one at Jealott's Hill in the UK, and a second at 
Richmond, California, with a field trials network stretched across dozens 
of sites world-wide.
We currently have a vacancy for an environmental modeller . To ensure the 
safety of pesticides to man and the environment extensive data are 
collected, including the amounts of pesticide residue present on crops.  
In fact, one of the major activities in our Environmental Sciences 
function is performing crop residue trials.  These involve the 
application of pesticides to crops in field trials, and analysing the 
pesticide residue content of the edible crop parts.  Many of hundreds of 
such trials are performed every year covering variables such as 
countries, different crops, different application rates and timings, 
various crop parts and processed products, and of course different 
pesticides.  These data are ultimately used in conjunction with toxicity 
data to determine the safety of the use of the pesticide products to man, 
in order that government authorities can be satisfied that the proposed 
uses of the products can be permitted.
Since human safety is involved, the activity of crop residue work has 
naturally become very conservative in nature, based entirely on real 
measurements, many of which are essentially repetitive.  And since there 
has often been little scope for debate about what trials have to be done, 
there has been little reason to sit back and look at the data and seek to 
quantitatively understand it.  This contrasts with some other areas of 
scientific activity in the company, where a quantitative understanding 
(and if possible a theoretical understanding) of the data has become of 
paramount importance.  However it is clear that the complex datasets 
generated are amenable to understanding, since experienced pesticide 
residue chemists have a pretty good general idea of what the results will 
be before they do a trial, and a fair amount is known from other work on 
the fundamental processes involved.
You will run a project to develop a better quantitative understanding of 
the parameters which govern crop residue data in order to improve risk 
assessment and data generation processes.  There will be support from our 
mathematical modelling group in Environmental Sciences, who already work 
on other aspects of pesticide fate, transport and risk assessment in the 
environment, and our Statistics Group who provide a variety of services 
to R&D.;
Once some quantitative understanding has been gained, the practical 
applications will start to open up, and will need assessing.  These may 
include:
 - extrapolating results from major crops to related minor crops, from 
country to country and between chemically related products
 - predicting residue trial results for validation purposes, and building 
a scientific basis for reducing the repetitive element of the trialling 
work
 - predicting crop residues for early foresight of human risk assessment 
during novel chemical development programs
 - designing product application programs which will minimise or 
eliminate crop residues
 - refining ecological risk assessments for non-target organisms living 
in or feeding on treated crops
You will be a numerate self starter with good communication skills, keen 
to make the most of this exciting opportunity.
Jealott's Hill Research Station is located in pleasant surroundings 
between Bracknell and Maidenhead.  We offer a range of benefits including 
profit sharing, pension scheme, subsidised restaurant and lively sports 
and recreation club.
If you wish to apply for this vacancy please send your CV, with full 
career details including qualifications and experience to date, quoting 
reference Ecol 93 to Penny Hodge, Human Resources Department, Zeneca 
Agrochemicals, Jealott's Hill Research Station, Bracknell, Berkshire RG42 
6EY.

Dutch wrote:

> Here is my problem:
> 
> If the tabs are already in numerical sequence (already solved),
> is it possible to reverse the positions of the 1 and 2 while the
> remaining tabs remain in sequence? Example:
> 
> 1     2     3     4                            2     1     3     4
> 5     6     7     8                            5     6     7     8
> 9    10   11    12                           9    10   11    12
> 13  14   15     X                            13  14   15     X
> 
> This is the solved                        This is what I have
> version.                                       to get.
> 
> Is it possible to reverse the 1 and 2? 
No, I don't think so.  Here is my reasoning:
Each time you move a piece, it really just swaps locations with
the space.  So we can think of an individual move as a transposition 
of the space and whatever tile we are moving.  We can then think of 
any exchange of tiles as a "product" of transpositions involving the
space.  For example, to move 15 to 12`s spot, 11 to 15's spot and
12 to 11's spot, we would do this:
1     2     3     4
5     6     7     8
9     10    11    12 
13    14    15    X
1     2     3     4
5     6     7     8
9     10    11    12 
13    14    X     15 
1     2     3     4
5     6     7     8
9     10    X     12 
13    14    11    15
1     2     3     4
5     6     7     8
9     10    12    X
13    14    11    15
1     2     3     4
5     6     7     8
9     10    12    15
13    14    11    X
Or:
 exchange 15 with X,
 exchange 11 with X,
 exchange 12 with X,
 exchange 15 with X
So, the exchange of 1 and 2 (move 1 to 2's spot, move 2 to 1's spot)
can be thought of as a long series of transpositions involving the
space. However, in order for the space to end up where it started,
an even number of transpositions is required.  To see this, consider 
the puzzle repainted as a checkerboard:
X O X O
O X O X
X O X O
O X O X
It will take an even number of moves to go from a square labeled 
"X" to another square labeled "X".  So, the transpostion of 1 and 2
must be the product an even number moves.
I hope everything up to here is clear.  The conclusion of my reasoning
requires some group theory (which I am not so good at).  Basically, if
you have a transformation that can can be written as an odd number of
transpositions, then it can't be written as an even number.  We have an
odd number (exchange 1 and 2 is one transposition) that must be written
as an even number (to get the space back to where it started).  This
is not possible, so it can't be done.
I hope that this helps.  Sorry that it is so long.  There is probably
an easier way.
Jason

Actually, the point is called a "centroid," and it's at the
intersection of the lines drawn from the vertices to the midpoints
of the opposite sides.  These lines are divided by this point
into segments in the ratio of one to two.  I've checked the case
of a right triangle with equal (45 degree) angles.  It turns out
that the line from one of the 45 deg. vertices to the centroid
divides the 45 deg. angle into angles of  26.6 deg. and 18.4 deg.
On 14 Dec 1996 04:37:01 GMT in sci.math.num-analysis, FEARLESSFD
(fearlessfd@aol.com) wrote:
> The COG of any triangle is given by the intersection of the lines
> bisecting the angles.
> fred a.
--
Prof. Ronald J. Hartranft          http://www.Lehigh.edu
Dept. of Mech. Engr. & Mechanics         /~rjh2/rjh2.html
Lehigh University                  Phone: 610-758-4109
19 Memorial Drive West             Email: rjh2@Lehigh.edu
Bethlehem, Penn. 18015-3085

I have been able to find many examples of algorithms that generate cubic 
splines for (x,y) series of data, but they all insist that the "x" series be 
layed out as such x(1) < x(2) < x(3) < x(4)...... x(n-1) < x(n).
Does anyone know of one that allows for values of "x" that do not follow this 
pattern (ie. the spline doubles back over itself)?

Jason W DeGraw wrote:
> 
> Dutch wrote:
> 
> 
> 
> > Here is my problem:
> >
> > If the tabs are already in numerical sequence (already solved),
> > is it possible to reverse the positions of the 1 and 2 while the
> > remaining tabs remain in sequence? Example:
> >
> > 1     2     3     4                            2     1     3     4
> > 5     6     7     8                            5     6     7     8
> > 9    10   11    12                           9    10   11    12
> > 13  14   15     X                            13  14   15     X
> >
> > This is the solved                        This is what I have
> > version.                                       to get.
> >
> > Is it possible to reverse the 1 and 2?
> 
> No, I don't think so.  Here is my reasoning:
> 
> Each time you move a piece, it really just swaps locations with
> the space.  So we can think of an individual move as a transposition
> of the space and whatever tile we are moving.  We can then think of
> any exchange of tiles as a "product" of transpositions involving the
> space.  For example, to move 15 to 12`s spot, 11 to 15's spot and
> 12 to 11's spot, we would do this:
> 
> 1     2     3     4
> 5     6     7     8
> 9     10    11    12
> 13    14    15    X
> 
> 1     2     3     4
> 5     6     7     8
> 9     10    11    12
> 13    14    X     15
> 
> 1     2     3     4
> 5     6     7     8
> 9     10    X     12
> 13    14    11    15
> 
> 1     2     3     4
> 5     6     7     8
> 9     10    12    X
> 13    14    11    15
> 
> 1     2     3     4
> 5     6     7     8
> 9     10    12    15
> 13    14    11    X
> 
> Or:
>  exchange 15 with X,
>  exchange 11 with X,
>  exchange 12 with X,
>  exchange 15 with X
> 
> So, the exchange of 1 and 2 (move 1 to 2's spot, move 2 to 1's spot)
> can be thought of as a long series of transpositions involving the
> space. However, in order for the space to end up where it started,
> an even number of transpositions is required.  To see this, consider
> the puzzle repainted as a checkerboard:
> 
> X O X O
> O X O X
> X O X O
> O X O X
> 
> It will take an even number of moves to go from a square labeled
> "X" to another square labeled "X".  So, the transpostion of 1 and 2
> must be the product an even number moves.
> 
> I hope everything up to here is clear.  The conclusion of my reasoning
> requires some group theory (which I am not so good at).  Basically, if
> you have a transformation that can can be written as an odd number of
> transpositions, then it can't be written as an even number.  We have an
> odd number (exchange 1 and 2 is one transposition) that must be written
> as an even number (to get the space back to where it started).  This
> is not possible, so it can't be done.
> 
> I hope that this helps.  Sorry that it is so long.  There is probably
> an easier way.
> 
> Jason
Dutch,
Jason's reasoning is right on and his explanation closely
follows that given in "Mathematical Recreations and Essays"
by W.W. Rouse Ball and H. S. M. Coxeter.
As Jason concluded, there must be an even number of transitions,
in going from a given arrangement to a new arrangement.
On a historical note, this problem first appeared in the late
1800s and went under the name 'The Fifteen Puzzle. Two articles
concerning it were in the American Journal of MAthematics, 1879,
Vol. ii. As you can tell, it has been around a while.
Regards,
phil kenny

Thank you both for your information. Especially
the historical context. Ill bring it up in class on
Monday, and see what my professor says. 

>REPORT ON NEW OR IMPROVED RESULTS OF COVERING DESIGNS C(v,k,t,m,l,=b):
More new results:
  v k t m l    b bOld
 -------------------- 
 52 7 3 3 1 1065 1066
 54 7 3 3 1 1205 1206 
 26 7 5 5 1 4358 4373
 18 7 6 6 1 3363 3366
 21 7 6 6 1 9647 9648
All were found with the program "SOPT" (System Optimizer) v1.0 by R.Belic
-- Uenal Mutlu (bm373592@muenchen.org)   
   Math Research, Designs/Codes, Data Compression Algorithms, C/C++
   Loc  : Istanbul/Turkey + Munich/Germany
   *** Alle Jahre Scheiss-Weihnachten, Kommerz-Terror, Mach Mit! ***

Daniel Zagar  writes:
	>I am writing a serial interface and i need the exact information about
	>representation of floating point numbers, ie bit patterns etc.
	>  What is the standard on Windows NT?
The standard doesn't depend on the operating; the standard depends on
the computer hardware you are using.
Therefore, you need to get a manual for the particular hardware.
For an Intel machine, you need the hardware manual for the x86,
for example.
	>  What is the standard on IRIX?
	>Information about reference manuals with IEEE or corresponding standard
	>numbers or is also needed.

In article <58vit3$kmb@fountain.mindlink.net> Grant Hiebert,
ghiebert@noif.ncp.bc.ca writes:
>I have been able to find many examples of algorithms that generate cubic 
>splines for (x,y) series of data, but they all insist that the "x" series be 
>layed out as such x(1) < x(2) < x(3) < x(4)...... x(n-1) < x(n).
>
>Does anyone know of one that allows for values of "x" that do not follow this 
>pattern (ie. the spline doubles back over itself)?
>
This is often done as a parametric spline, i.e., model both x and y as
a function of arclength.
John D'Errico
derrico@kodak.com