HDTenEightyP/NetNews huggingface dataset:
From: mouse@thunder.mcrcim.mcgill.edu (der Mouse)
Newsgroups: rec.puzzles
Subject: Re: 8-queen problems (revisited?)
Date: 21 Dec 92 01:00:19 GMT
Organization: McGill Research Centre for Intelligent Machines

In article <1992Dec17.133922.29503@zellweger.ch>, bisc@zellweger.ch (Thomas K. Bischoff) writes:
> In article <1992Dec15.181155.22208@questrel.com> chris@questrel.com (Chris Cole) writes:

>> From the Archive, the answer [to 8-queens] is:

>> void try(int row, int left, int right) {
[...]
>>      poss = ~(row|left|right) & 0xFF;
>>      while (poss != 0) {
>>         place = poss & -poss;
>>         try(row|place, (left|place)<<1, (right|place)>>1);
>>         poss &= ~place;
> Could some kind soul explain this program. I have tried to understand
> it for several hours. (I know C, this is not the problem).

This is a rather clever program, actually, and generalizes to board
sizes up to the word size of the machine.

The three arguments to try() can be thought of as bitmasks
corresponding to vertical attacks, diagonal attacks from one direction,
and diagonal attacks from the other way.  The while loop I didn't edit
away is, essentially, "loop for each bit set in poss", with "place" set
to each such bit in turn.

For example, if the arguments to try are row=0x84, left=0x10, and
right=0x41, this corresponds to vertical attacks down columns 1 and 6,
a diagonal attack from one direction against the square in column 4,
and diagonal attacks from the other direction against the squares in
columns 2 and 8.  These values would actually occur (MSB at left):

row:               left:              right:
. . . . . Q . .    . . . . . Q . .    . . . . . Q . .
Q . . . . . . .    Q . . . . . . .    Q . . . . . . .
x . . . . x . .    . . . x . . . .    . x . . . . . x

Thus, for example, row|left|right is all cells that are forbidden for
the current row.  Adding |place to each one, as is done in the
subexpressions in the recursive call, corresponds to placing a queen
there; the shifts correspond to the way diagonal attacks attack squares
one square farther over per row away from the attacking queen.

					der Mouse

			    mouse@larry.mcrcim.mcgill.edu
Newsgroups: rec.puzzles
From: fsmgs@camelot.acf-lab.alaska.edu (Michael Schmahl [Black-Robe Mage])
Subject: Re: Answers to Hard Analogies
Organization: University of Alaska Computer Network
Date: Fri, 18 Dec 1992 05:53:05 GMT

Chris Long writes
] 
] Questions:
] 
] 1. Host : Guest :: Cynophobia : Lyssophobia
] 2. Mountain : Plain :: Acrocephalic : Homalocephalic
] 3. Lover : Believer :: Philofelist : Gelenathropist
] 4. 4 : 6 :: Bumblebee : Blue Bird
] 5. 2 : 1 :: Major : Brigadier
] 6. 1 : 24 :: Group : Field Army
] 7. 4 : 64 :: Crotchet : Hemidemisemiquaver
] 8. Last : First :: Grave : Prestissimo
] 9. 7 : 9 :: Throne : Seraph
] 10. Pride : Hatred :: Beelzebub : Sonneillon
] 11. Dollar : Bond :: Grant : Roosevelt
] 12. Ek : Sankh :: 1 : 10^14

Very hard!  I would have only got no's 5, 7, and 12, but I think I would have  
gotten more if the 'means' terms were exchange.  Technically these analogies are  
incorrect unless the two middle terms are interchanged.  'Host' is not to 'Guest'  
as 'Cynophobia' is to 'Lyssophobia'.  But 'Host' is to 'Cynophobia' (Cynophobia is  
the fear of a host -- in this case a dog), as 'Guest' is to 'Lyssophobia'  
(Lyssophobia is the fear of the host's -- the dog's -- guest -- in this case,  
rabies (although fear of fleas mokes more sense)).  Although mathematically  
correct, this isn't a test of math....

--
CONFIG.DAT not found.  Reboot universe?
Newsgroups: rec.puzzles
From: mouse@thunder.mcrcim.mcgill.edu (der Mouse)
Subject: Re: The Rifleman Problem
Organization: McGill Research Centre for Intelligent Machines
Date: Fri, 18 Dec 92 03:31:19 GMT

In article <Dec15.235132.63842@yuma.ACNS.ColoState.EDU>, boll@CS.ColoState.EDU (dave boll) writes:

> N riflemen are situated randomly on a plane.

Um, this needs more precision.  "[R]andomly" without further
modification usually means "with each possibility having equal
probability", which is not possible over the entire plane.

Are they situated with uniform distribution over some finite piece of
the plane?  With some nonuniform distribution over the whole plane (the
former is just a special case of this)?  What?

					der Mouse

			    mouse@larry.mcrcim.mcgill.edu
From: klausf@hathi.informatik.rwth-aachen.de (Klaus Frank)
Newsgroups: rec.puzzles
Subject: Re: Cute problem radicalized
Date: 15 Dec 92 15:48:52 GMT
Organization: Rechnerbetrieb Informatik - RWTH Aachen
Distribution: world
NNTP-Posting-Host: hathi.informatik.rwth-aachen.de

jkenton@world.std.com (Jeff Kenton) writes:

>	Given the numbers 101, 10101, 1010101, ... (decimal, not binary)

And here's another problem for those who are fascinated by 101 and 91: 

	Given x, y such that the following equations hold for a number n:
		0 <= n < 10^8
		x = (n^13) mod (10^12 - 1)
		y = (n^13) mod 10

	Calculate n, but don't use just brute force. 

Newsgroups: rec.puzzles
From: kanad@quip.eecs.umich.edu (Kanad Chakraborty)
Subject: Re: Closed form wanted.
Organization: University of Michigan EECS Dept., Ann Arbor
Date: Wed, 16 Dec 1992 00:00:31 GMT

In article <1992Dec15.235005.3396@zip.eecs.umich.edu> kanad@quip.eecs.umich.edu (Kanad Chakraborty) writes:
>Give a closed form, as a function of x, for the summation :
>
>Sigma 1/k * 2^k/(2^(2k) - 1) 
>1 <= k
>
>Kanad

Oops!! I meant 

Sigma 1/k * x^k/(x^(2k) - 1)
1 <= k

Sorry for the typos.

Yours apologetically,

Kanad
Date: Tuesday, 15 Dec 1992 11:19:45 EST
From: <RVESTERM@vma.cc.nd.edu>
Newsgroups: rec.puzzles
Subject: Re: Serial representation of arbitrary data

this is most likely nowhere near optimal.  but then, i don't care.
i like it.

choose an arbitrary string of binary digits, C.

let A1, ... , An be the n strings that you want to store.

let B be the smallest binary string such that the following two conditions
hold:

        1) B does not occur as a substring of any A1, ... , An;

        2) for no initial segment D of C is any terminal segmant E of B
           such that E concatenated with D is C.

then store A1, ... , An as follows (spaces are only for readability,
obviously):

     B C A1 B A2 B A3 B A4 B ... An-1 B An

there's probably some way to choose an optimal C, but again, i care not
for optimumitude. (optimumitude?).

so here's an example.  lat's say we choose C to be 10110.  let's say that
the strings we want to store are 10101010, 11, 0101, and 101001101.

the smallest number which is not a substring of any of these four strings
is 1000.  moreover, neither 1000, 10001, 1000101, 10001011, 100010110,
000, 0001, 00010, 000101, 0001011, 00010110, 00, 001, 0010, 00101, 001011,
0010110, 0, 01, 010, 0101, 01011, 010110, nor the empty string equal to
10110 (that is, no terminal segment of 1000 concatenated with any initial
segment of 10110 is 10110).

so we store our four numbers as (again, spaces are just for your benefit)

     1000 10110 10101010 1000 11 1000 0101 1000 101001101

now to extract what we've stored, we look for C.  we see 100010110, and
we know that C is 10110.  thus B is 1000.  then we see 101010101000, and
since B is 1000, we have that A1=10101010.  next, we see 111000.  B is
1000, so A2 is 11.  next, 01011000, giving A3=0101.  finally, we see
101001101, and reach the end of our string, so A4=101001101.

there was no possibility of confusing part of a stored string for
our marker, since our marker (1000) was picked such that it did not occur
as a substring of any of our stored strings.

again, maybe there's an optimal C.

bob vesterman.


Newsgroups: rec.puzzles
From: ccli@descartes.uwaterloo.ca (Calvin Li)
Subject: Re: Monty Hall Puzzle RIP
Organization: University of Waterloo
Date: Fri, 18 Dec 1992 21:49:52 GMT

NO!

It doesn't matter on the number of combinations to win.

O.k.  Here it is.  I will assume that everyone here will agree that you start
out with a 1/3 odds of having chosen the right door.  This also means that 
there is a 2/3 chance that it isn't your door.  Even though Monty opens a door,
this doesn't change the odds of your having chosen the right door.  The other
door has odds of 2/3 to win.  

I know that this won't convince you, so I propose to extend this point by an
extension of the problem. Suppose, instead, that there are 100 doors.  You choose
1.  Then, 98 of the other doors are removed.  Do you still think that you have a
50 -50 chance of having chosen the right door?  I'd switch!!  And if that still
doesn't convince you, try 1,000,000 doors.  you pick one.  Every other one but
one are removed.  Would you stay, or would you change?

Calvin Li.
Food for thought... :)
Newsgroups: rec.puzzles,sci.math
From: pcl@ox.ac.uk (Paul C Leyland)
Newsgroups: rec.puzzles,sci.math
Subject: Re: Marilyn Vos Savant's error?
Date: 16 Dec 92 18:36:56 GMT
	<1992Dec15.160000.3714@cs.cornell.edu>
	<BzBE0J.A6F@watdragon.uwaterloo.ca>
	<1992Dec15.211052.17873@cs.cornell.edu> <0_l2xhh@rpi.edu>
Organization: Oxford University Computing Services, 13 Banbury Rd Oxford OX2
	6NN
In-reply-to: rogerj@aix.rpi.edu's message of 15 Dec 92 21:54:35 GMT

In article <0_l2xhh@rpi.edu> rogerj@aix.rpi.edu (Diversion (Jeff Rogers)) writes:

   What I didn't see in this thread ('tho I may have missed it earlier, I just
   picked up the thread) is the simple biological argument. The probability of
   any given child being a boy[girl] is 50%. Regardless of the sexes of any
   siblings. 

   Disregarding psychological implications:
   "I have 100 children, (at least) 99 of which are boys"

   The chance that the 100th child is a boy is _still_ 50%.

Wrong!
	It's strongly dependent on heredity; age of mother when giving
birth and a lot of other factors. There is a moderately strong
correlation for parents to have same-sex children.  The incidence of
identical twins, which are the same sex by definition, would suggest a
positive correlation should be expected.  The population average of
the sex ratio in the UK is something like 53% of live births are of
boys; infant mortality hits boys harder than girls so the ratio tends
to equalise.  As people age, the longevity of women is markedly
greater than that of men, so by the time your children are in their
eighties, it's rather more likely that they are female.

I don't have references, etc, to hand.  If people *really* want to
know, I'll find out and post them.  My wife has done quite a bit of
research into infant mortality rates and into premature birth
incidence and survival.  I guess she'll tell me the results.

Paul
--
Paul Leyland <pcl@oxford.ac.uk>          | Hanging on in quiet desperation is
Oxford University Computing Service      |     the English way.
13 Banbury Road, Oxford, OX2 6NN, UK     | The time is come, the song is over.
Tel: +44-865-273200  Fax: +44-865-273275 | Thought I'd something more to say.
Organization: Junior, Math/Computer Science, Carnegie Mellon, Pittsburgh, PA
Newsgroups: rec.puzzles
Date: Tue, 15 Dec 1992 19:24:15 -0500 
From: Court Demas <court+@CMU.EDU>
Subject: Re: Bit Counting
	<1992Dec14.140459.17126@cs.cornell.edu>

> In article <8325@charon.cwi.nl> dik@cwi.nl (Dik T. Winter) writes:
> >...
> >  Otherwise you had better inform
> >us what your definition of arithmetic operations is.  (I would say:
> >addition, subtraction, multiplication, division, exponentiation,
> >root finding, etc., etc., but not clearing specific bits, that is a
> >logical operation.)

Er- Have you ever heard of an ALU which doesn't support ANDs?  I can't
see how people don't consider boolean functions to be arithmetic.

-court
Newsgroups: rec.puzzles
From: kanad@quip.eecs.umich.edu (Kanad Chakraborty)
Subject: Closed form wanted.
Organization: University of Michigan EECS Dept., Ann Arbor, MI
Date: Tue, 15 Dec 1992 23:50:05 GMT

Give a closed form, as a function of x, for the summation :

Sigma 1/k * 2^k/(2^(2k) - 1) 
1 <= k

Kanad
From: ST102315@brownvm.brown.edu (Jake)
Newsgroups: rec.puzzles
Subject: Big Numbers
Date: Wed, 16 Dec 1992 11:29:37 EST
Organization: Brown University
NNTP-Posting-Host: brownvm.brown.edu
News-Software: BNN via BNN_POST v1.0 beta

All this talk about large numbers and their notation caused me to
ponder the following question...

What is the smallest number that cannot be specified by a description
containing less than one hundred fifty letters?

Answers are much appreciated.

-jwgh
Newsgroups: rec.puzzles
From: boll@CS.ColoState.EDU (dave boll)
Subject: Re: The Rifleman Problem
Date: Fri, 18 Dec 1992 16:23:14 GMT
Organization: Colorado State University, Computer Science Department

In article <1992Dec18.033119.19454@thunder.mcrcim.mcgill.edu> mouse@thunder.mcrcim.mcgill.edu (der Mouse) writes:
>In article <Dec15.235132.63842@yuma.ACNS.ColoState.EDU>, boll@CS.ColoState.EDU (dave boll) writes:
>
>> N riflemen are situated randomly on a plane.
>
>Um, this needs more precision.  "[R]andomly" without further
>modification usually means "with each possibility having equal
>probability", which is not possible over the entire plane.
>
>Are they situated with uniform distribution over some finite piece of
>the plane?  With some nonuniform distribution over the whole plane (the
>former is just a special case of this)?  What?
>
  Well, I believe this caused some confusion during the Omni puzzle as
  well. As I dimly recall, some people used a circle, some a square. I
  think the most 'elegant' solution is the surface of a sphere, as this
  eliminates boundary situations.   
-- 
     ------------------------------------------------------------
     Dave Boll  boll@handel.cs.colostate.edu
                "The speed of time is 1 second per second"
     ------------------------------------------------------------
From: warwick@cs.uq.oz.au (Warwick Allison)
Newsgroups: rec.puzzles
Subject: Turtle Puzzle (Re: A puzzle)
Date: 14 Dec 92 06:55:56 GMT
Reply-To: warwick@cs.uq.oz.au

apardon@rc1.vub.ac.be (Antoon Pardon) writes:
>jhsegal@wiscon.weizmann.ac.il (Livian) writes:

>|> There is a turtle in the midlle of a circle,and a turtle eater on the
>|> circle's circumference.The turttle eater's speed is 4 times(bigger then PI)
>|> bigger than the turtlle's.
>|> How the hell can the turtle get out from the circle,without being eaten
>|> by the tuttle eater?

>The turtle starts with positioning itself on a concentric circle with
>radius 1/4 with the centre between it and the turtle eater.

[assume turtle eater cannot come inside circle!!!?]

You need to demonstrate that the turtle can GET to this position (otherwise,
a simpler solution is to position itself r/10000 from the edge, with the
eater on the other side.

Unfortunately, for the R/4 case, this cannot be done, but for *slightly*
inside the R/4 distance, simply run around that circle until the eater is
opposite (must happen, since eater must run 4+epsilon times further), then
swiftly make the 90 degree turn, and head for the hills/circumference.

>It can now go for the point exactly opposite of the turtle eater. It
>will take the turtle 3/4 to get there while it will take the turtle eater
>PI/4 to get there. So the turtle makes it.

For the 1/(4+epsilon) case, the turtle still survives, since 3/4 << pi/4.

So,
	0 < epsilon < 12/pi-4

--
Warwick
--
  _-_|\      warwick@cs.uq.oz.au            /Disclaimer:
 /     * <-- Computer Science Department,  /  
 \_.-._/     University of Queensland,    /   C references are NULL && void*
      v      Brisbane, Australia.        /  
Newsgroups: rec.puzzles
From: ilan@leland.Stanford.EDU (ilan vardi)
Subject: Re: Naming Large Numbers
Organization: DSG, Stanford University, CA 94305, USA
Date: Fri, 18 Dec 92 01:19:28 GMT

There is a possibly interesting game consisting of trying to name
larger numbers than your opponent, where the rules are that you can
operate on his number and the point is that you use few operations to
name a bigger number. For example:

A: names 5 

B: names 5 + 1

But B could have said 2*5 and done better, or else 2^5. So in general
you would get

A: names n

B: ``I successor you,'' i.e., n+1

   ``I double you'', i.e., 2*n.

   ``I exponentiate you,'' i.e., 2^n, 

   ``I tower you,'' i.e., 2^2^2...^2, n times. 

In fact he could have said: ``I Ackerman you,'' which really means 
``I diagonalize you''.

So in some sense, the game can be viewed as happening on the recursive
hierarchy with a move taking you from one limit to another.  For
example, after B says ``I diagonalize you'', A responds with ``I
diagonalize you'', which means ``I diagonalize your diagonalization''.
E.g., you diagonalize the using the Ackerman function, by
diagonalizing the sequence

B_1(n, k) = Ackerman(Ackerman...(Ackerman(n)))   (k Ackerman's)

B_2(n, k) = B_2(n, B_1(n, k-1))

i.e., the function you end up with is essentially

  C(n) = B_n(n, n) 

up to some fussing about whether n -> n-1 or not.

Such moves seem to be optimal, in some sense.

-ilan
From: dbush@csugrad.cs.vt.edu (David Bush)
Newsgroups: rec.puzzles
Subject: Re: Big Numbers
Date: 17 Dec 92 20:37:55 GMT
Organization: Virginia Tech Computer Science Dept, Blacksburg, VA

>Nitpicks, nitpicks, nitpicks...

Right on! Let's name some big numbers. I hope speaking in TERSE mathematics (as
opposed to english) is acceptable:

H(K)=10^(10^...10^(10^100)...)
     \    K      /
H(0,K1,K2,...,KN)=H(H(K1,...,KN),H(K2,...,KN),...,H(KN))
H(M,K1,K2,...,KN)=H(M-1,H(K1,...,KN),H(K2,...,KN),...,H(KN))
PLEXORAMA=H(10^100,...,10^100)
            \    10^100     /

Of course this can be improved with judicious application of the factorial
symbol and suchlike, but the definition as it stands is sufficient to merit
the appellation "remarkably useless." :)

David Bush   Virginia Tech HALLELUJAH! FINALS ARE OVER  dbush@csugrad.cs.vt.edu
From: mouse@thunder.mcrcim.mcgill.edu (der Mouse)
Newsgroups: rec.puzzles
Subject: Re: Paper Folding
Date: 17 Dec 92 12:08:41 GMT
Organization: McGill Research Centre for Intelligent Machines

In article <1992Dec15.071749.20479@serval.net.wsu.edu>, wvanweer@wsuaix.csc.wsu.edu (Wayne VanWeerthuizen) writes:

> [unit cube with striped sides. stripes running a different way on
> each pair of faces]

> But, if the paper has parallel stripes on it (ie. stripes run the
> same way in all unit squares.) how can the above cube be made?

> The paper must (before folding) be one continuous flat sheet.

Does the paper have stripes on both sides?  Do the stripes run the same
way on both sides?  May the shape before folding be other than a
rectangle?

In any case, I've got a way of folding such a cube from a piece of
paper of area 11.5, with stripes on both sides, running the same way on
both sides, with an additional proviso.  The shape is a strip of 12
unit squares, with one end square cut diagonally, with only half of it
present.  The stripes run parallel to the long dimension of the strip;
the additional proviso is that the stripe pattern must be symmetric
about the centerline of the strip, because most faces of the cube are
patched together from two diagonally-separated half-faces, and the
stripes won't match up otherwise.

And yes, I'm sure this way works; I made such a strip of paper and
tried it.

					der Mouse

			    mouse@larry.mcrcim.mcgill.edu
From: mouse@thunder.mcrcim.mcgill.edu (der Mouse)
Newsgroups: rec.puzzles
Subject: Re: Xmas number Puzzle [a few answers]
Date: 17 Dec 92 01:19:43 GMT
Organization: McGill Research Centre for Intelligent Machines

In article <9212110845.AA14009@sun4nl.nluug.nl>, bultman@dgw.rws.nl (G.W.Bultman) writes:

> As promised, a new number puzzle.

> - Make the numbers 10, 100 & 1000 using only 1's, 2's, 3's ... 9's -

> Using only the standard operators (+,-,*,/,sqrt,exponentiation and !). 
> The catch, of course, is to use a few [123456789]'s as possible.

> Not allowed are 
>      - the decimal point without a leading digit

Why not?  Is there some reason, or is this just to make it harder?

> Examples: 
> +        10           |         100          |        1000         |

> +      22-2           |     (222-22)/2       |                     |

Hm?  22-2 is 10?  :-)

Some trivial upper bounds: for any digit x,

10 = (xx - x) / x        (four copies of x)
100 = (xxx - xx) / x     (six copies of x)
1000 = (xxxx - xxx) / x  (eight copies of x)

with the trailing "/ x" omitted when x=1.  I can improve on this with

100 =	((22-2) / 2) ^ 2
	(33*3) + (3/3)
	(4!*4) + 4
	5! + 5 - (5*5)
	99 + (9/9)

1000 =	(11-1) ^ (1+1+1)
	(sqrt(2^22) / 2) - 22 - 2
	((33-3) / 3) ^ 3
	(55-5) * ((5*5)-5)
	999 + (9/9)

So far, these are the best I've found, and as the posting is about to
expire here, I'm posting them to see what the world has to say.

					der Mouse

			    mouse@larry.mcrcim.mcgill.edu
Date: Wednesday, 16 Dec 1992 13:29:50 EST
From: <RVESTERM@vma.cc.nd.edu>
Newsgroups: rec.puzzles
Subject: Re: The Rifleman Problem
 <1992Dec16.161727.5632@udel.edu>

brian rapp asks, "if you knew you were going to be in one of these
lethal flights, where would you sit?"

the bathroom, obviously.

bob vesterman.
From: klausf@rama.informatik.rwth-aachen.de (Klaus Frank)
Newsgroups: rec.puzzles
Subject: Re: Cute problem radicalized
Date: 17 Dec 92 17:53:58 GMT
Organization: Rechnerbetrieb Informatik - RWTH Aachen
Distribution: world
NNTP-Posting-Host: rama.informatik.rwth-aachen.de

J.Theodore.Schuerzinger@dartmouth.edu (J. Theodore Schuerzinger) writes:

>It seems to me that there are an [...] number of solutions -- just
>plug in various vales of n.

Alice chooses randomly a number: n = 1000002 < 10^8. Then she calculates:
n^13 = 100002600031200228801144004118410982421964832947236608029286415974405\
3248008192

The last digit is y = 2.
Now she adds parts of n^13 :

            1000026
     + 000312002288
     + 011440041184
     + 109824219648
     + 329472366080
     + 292864159744
     + 053248008192
     --------------
   x = 797161797162 (mod 10^12-1)

She writes Bill a letter containing x and y. Can Bill calculate n without
"plugging in" a million possible values for n (or more than a million) ?

Of course he could guess: 
  Errr, 79716 occurs twice and is therefore irrelevant. What remains, is
  797161797162 - 797160797160 = 1000002 (He remembers two trivial cases
  in which this calculation is correct - e.g. for n = 1, 00000 occurs twice
  in x = 00000 0 00000 1 and is irrelevant, so...). Well, let's try 1000002.
  Ah! That's it!

Can you show Bill an algorithm which works for any n < 10^8 Alice could have
chosen?
Date: Thursday, 17 Dec 1992 16:36:55 EST
From: <RVESTERM@vma.cc.nd.edu>
Newsgroups: rec.puzzles
Subject: Re: Big Numbers
 <92351.123112RVESTERM@vma.cc.nd.edu>,<92351.132601RVESTERM@vma.cc.nd.edu>
 <1gp8pmINNik@gap.caltech.edu> <1gp9e8INNhit@cat.cis.Brown.EDU>
 <BzF7z8.9Ao@csugrad.cs.vt.edu>

i don't understand this circle thing.  if we have the obvious
circle(x)=lim n-gon(x) as n-->oo, then circle(2), for example,
is not finite.

bob vesterman.