HDTenEightyP/NetNews huggingface dataset:
From: dik@cwi.nl (Dik T. Winter)
Newsgroups: rec.puzzles
Subject: Re: Bit Counting
Date: 17 Dec 92 00:18:27 GMT
Organization: CWI, Amsterdam

In article <Yf=bQj200Vp=IOqm9s@andrew.cmu.edu> court+@CMU.EDU (Court Demas) writes:
 > > 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.
 > 
But now you are restricting the original problem to just an implementation
on some machine (probably with some upperbound on the numbers involved,
which invalidates the use of big-Oh).  The original question was about
an abstract algorithm without any reference to an ALU or whatever.
But the name does already tell its tale: Arithmetic Logic Unit.

Regarding your remark: of the hardware manuals for machines I have
at home that I checked, and that group the instruction by kind, all
distinguish arithmetic and logical operations (CDC 3200, DEC 10, NEC SX2,
Cray Y-MP, VAX, 80386, 68030), and they group multiplication and division
together with the arithmetic operations, when available.  So I appear not
to be the only one making the distinction.
-- 
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland
home: bovenover 215, 1025 jn  amsterdam, nederland; e-mail: dik@cwi.nl
From: klas@harry.uh.edu ()
Newsgroups: rec.puzzles
Subject: Rubberband trick
Date: 19 Dec 1992 02:27:31 GMT
Organization: University of Houston
Distribution: world
Reply-To: klas@harry.uh.edu ()
NNTP-Posting-Host: harry.imb.uh.edu

To appreciate this problem you need to know a little bit about
thermodynamics.

Take a rubberband and extend it as far as it will go without
breaking. Hold it in that position for 20-30 seconds. Let it
contract completely and immediately touch it to your lips. It is
not a very strong effect, but you should be able to notice
something quite surprising. What has happened and how do you
explain it?

You get a more noticeable effect if you use a balloon (not
inflated) or a piece of latex tubing instead of the rubberband.

Klas Hedenstierna
klas@harry.imb.uh.edu
From: jmorris@spider.co.uk (John Morris)
Newsgroups: rec.puzzles
Subject: Re: Bit Counting
Date: 17 Dec 92 13:12:00 GMT
Organization: Spider Systems Limited, Edinburgh, UK.

In article <Yf=bQj200Vp=IOqm9s@andrew.cmu.edu> court+@CMU.EDU (Court Demas) writes:
>> 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.
>
Yes - the Vax. It has "BIS" (bit set - just an OR) and BIC (bit clear -
and "and not" operation). No "AND" as such.

John "I only stop lurking to nit-pick" Morris


-- 
-John Morris-Spider Systems Ltd-031 554 9424-jmorris@spider.co.uk-GM4ANB@GB7EDN-
From: J.Theodore.Schuerzinger@dartmouth.edu (J. Theodore Schuerzinger)
Newsgroups: rec.puzzles
Subject: Re: Cute problem radicalized
Date: 15 Dec 92 16:34:43 GMT
Organization: Dartmouth College, Hanover, NH
X-Posted-From: InterNews1.0b1@newshost.dartmouth.edu

In article <klausf.724434532@hathi>
klausf@hathi.informatik.rwth-aachen.de (Klaus Frank) writes:

> 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.

I may be getting the mod function mixed up (I haven't studied any math
in two years!), but how about the following solution:

n=x=y=1

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

OK, assuming integral values of n there isn't an infinite number of
solutions, because n is bounded, but you get my drift.


--Ted Schuerzinger
email: .zed@Dartmouth.EDU
"I should have known it would be bad vodka when all the label said was
'Russian Vodka'."
Xref: sparky rec.puzzles:7904 rec.org.mensa:8788 sci.psychology:4790
From: clong@romulus.rutgers.edu (Chris Long)
Newsgroups: rec.puzzles,rec.org.mensa,sci.psychology
Subject: Results of Mega Test #25
Date: 13 Dec 92 09:12:43 GMT
Followup-To: rec.puzzles
Organization: Rutgers Univ., New Brunswick, N.J.


I've received over 100 responses, and they support my belief that this
is one of the worst questions I've ever seen on such a test (the worst
was the tetrahedron-pyramid problem that appeared on the SAT).  Two
reasons were given much more frequently than the others.  One was the
intended answer, and the other was the answer I chose (but for a
different, even better, reason than why I chose it).  Only a few people
found both "good" reasons, with these equally divided as to which was
the "best" answer.

I'll be happy to provide a more detailed analysis (when it's ready) to
those who've taken the Mega Test or those who will attest to the fact
that they never intend to take it.  This will include a catalog of every
reason given, together with their frequency.
-- 
Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618

"S.B., with an I.Q. of 161, failed to complete his course of study,
running away instead with his professor's wife."
H. J. Eysenck, _Know Your Own I.Q._
From: carl@SOL1.GPS.CALTECH.EDU (Carl J Lydick)
Newsgroups: rec.puzzles
Subject: Re: Big Numbers
Date: 17 Dec 1992 07:06:37 GMT
Organization: HST Wide Field/Planetary Camera
Distribution: world
Reply-To: carl@SOL1.GPS.CALTECH.EDU
NNTP-Posting-Host: sol1.gps.caltech.edu

In article <92351.132601RVESTERM@vma.cc.nd.edu>, <RVESTERM@vma.cc.nd.edu> writes:
=hmm... as i proved in my last post, there is no smallest number which
=cannot be described by 150 characters or less.
=
=however, i just realized that only finitely many things can be described
=by 150 characters or less.

Disproof of that assertion by demonstration:
	All numbers that can be described by 150 characters or less.
Other counterexamples:
	The positive integers
	The integers
	The real numbers
	The complex numbers
	The even integers
	The odd integers
Now, if you meant that there are only a finite number of descriptions requiring
150 or fewer characters, I'd have to agree with you.
--------------------------------------------------------------------------------
Carl J Lydick | INTERnet: CARL@SOL1.GPS.CALTECH.EDU | NSI/HEPnet: SOL1::CARL

Disclaimer:  Hey, I understand VAXen and VMS.  That's what I get paid for.  My
understanding of astronomy is purely at the amateur level (or below).  So
unless what I'm saying is directly related to VAX/VMS, don't hold me or my
organization responsible for it.  If it IS related to VAX/VMS, you can try to
hold me responsible for it, but my organization had nothing to do with it.
Xref: sparky rec.puzzles:8071 rec.org.mensa:8886
From: mouse@thunder.mcrcim.mcgill.edu (der Mouse)
Newsgroups: rec.puzzles,rec.org.mensa
Subject: Re: The Worm and the Blanket Problem
Date: 21 Dec 92 00:34:36 GMT
Organization: McGill Research Centre for Intelligent Machines

In article <1992Dec16.064930.26639@questrel.com>, dmi@questrel.com (Dean Inada) writes:
> In article <1992Dec12.194815.16303@CSD-NewsHost.Stanford.EDU> snewman@Xenon.Stanford.EDU (Steven Newman) writes:

>> Here is a new upper bound for the worm-and-blanket problem.

> I'd like a subtle clarification of this puzzle:

> Is it sufficient that, for each configuration of the worm, there
> exists some position of the blanket that covers it?

This seems to be what everyone is answering.

> Or do we also require that any continuous motion of the worm can be
> followed by some continuous motion of the blanket that keeps the worm
> covered at each instant?

This seems to me to be a significantly harder problem, and actually did
not occur to me as a possible interpretation.  Got any suggestions for
its solution?

					der Mouse

			    mouse@larry.mcrcim.mcgill.edu
Newsgroups: rec.puzzles
From: snewman@Xenon.Stanford.EDU (Steven Newman)
Subject: Re: Ask Marilyn
Summary:  Odds are 2/3, not 1/2
Organization: Computer Science Department, Stanford University.
Date: Mon, 14 Dec 1992 19:09:42 GMT

> Does everyone agree that Marilyn vos Savant's answer to the pancake
> probability problem in yesterday's Parade magazine was wrong? The
> answer is really 50-50. Either you've picked the pancake with 2 brown
> sides, in which case the other side is brown, or you've picked the
> pancake with one brown side, in which case the other side is not
> brown. 50-50.

I don't read Parade, but this sounds like a standard puzzle: you have
two cards, one red on both sides, one red on one side and white on the
other.  You put both cards into a bag and then pull one out at random,
looking only at one side of the card.  The side you see is red.  What
is the probability that the other side is red?

The answer is 2/3, not 1/2.  Many people find this *very* hard to
believe, but it is true.  The argument above fails because the odds
of having picked the red-red card are GREATER THAN 50%.  This is
because we have tossed out some of the cases where you pick the red-
white card, i.e. those cases where you happened to pull it out with
the white side on top.

If you don't believe me, please TRY THE EXPERIMENT before posting a
"proof" that the odds are 50-50.  Take two pieces of paper, put an "X"
on one side of one of them, and repeatedly choose one side of one piece
at random.  If you see the "X", then try again; if you see a blank side,
then record the contents of the other side ("X" or blank).  After a few
dozen trials you will see that the odds of having the "X" on the other
side are only 1/3.

 - Steve Newman (snewman@cs.stanford.edu)

Newsgroups: rec.puzzles
From: boll@CS.ColoState.EDU (dave boll)
Subject: The Rifleman Problem
Date: Tue, 15 Dec 1992 23:51:32 GMT
Organization: Colorado State University, Computer Science Department


  Does anyone remember the "Rifleman Problem"? It was published (surely not
  for the first time) in that renowed journal of scientific research
  Omni, in the early to mid 80's.

  The problem is this:

  N riflemen are situated randomly on a plane. At the same instant, each
  shoots and kills his nearest neighbor. How many are left?

  My hazy recollection is that Omni said the 1-D case was solved, but the
  2-D case wasn't. I also seem to recall (they published it as a brain
  teaser) that they received some correct answers - but I don't have 
  access to Omnis that are that old.

  I did a computer simulation (put the points on the surface of a sphere,
  use large N, etc. for a decent 2D case), but what would be interesting
  is the analytic form of the answer.

  Does anyone recall or know?
-- 
     ------------------------------------------------------------
     Dave Boll  boll@handel.cs.colostate.edu
                "The speed of time is 1 second per second"
     ------------------------------------------------------------
Newsgroups: rec.puzzles
From: sbardhan@uncc.edu (Soumendu Bardhan)
Subject: Re: Aces and Queens (P.S. to: The paradox
Summary: Interesting Calculus Puzzle
Reply-To: sbardhan@uncc.edu
Organization: University of NC at Charlotte
Date: Fri, 18 Dec 1992 02:33:29 GMT

X+ X+ X+ X+ X+ X .... X times = X^2

differntiating both sides w.r.t. X we obtain

1+1+1+1+.......X times = 2X
or, X = 2X
as X may not be zero,
1 = 2.


Newsgroups: rec.puzzles
From: bisc@zellweger.ch (Thomas K. Bischoff)
Subject: Re: 8-queen problems (revisited?)
Reply-To: bisc@zellweger.CH (Thomas K. Bischoff)
Organization: Zellweger Uster AG, Switzerland
Date: Thu, 17 Dec 92 13:39:22 GMT

In article <1992Dec15.181155.22208@questrel.com> chris@questrel.com (Chris Cole) writes:
>
>From the Archive, the answer is:
>********
>games/chess/queens.s
>********
>92.  The following program uses a backtracking algorithm to count positions:
>
>#include <stdio.h>
>
>static int count = 0;
>
>void try(int row, int left, int right) {
>   int poss, place;
>   if (row == 0xFF) ++count;
>   else {
>      poss = ~(row|left|right) & 0xFF;
>      while (poss != 0) {
>         place = poss & -poss;
>         try(row|place, (left|place)<<1, (right|place)>>1);
>         poss &= ~place;
>         }
>      }
>   }
>
>void main() {   
>   try(0,0,0);
>   printf("There are %d solutions.\n", count);
>   }
>--
>Tony Lezard IS tony@mantis.co.uk OR tony%mantis.co.uk@uknet.ac.uk
>OR EVEN arl10@phx.cam.ac.uk if all else fails.


Could some kind soul explain this program. I have tried to understand it for
several hours. (I know C, this is not the problem).
-- 
Thomas K. Bischoff    Net: bit@ten.ch,bisc@zellweger.ch 
***** Minds, like parachutes, only function when open.

Xref: sparky rec.puzzles:8024 sci.math:17127
From: anarch@Apple.COM (The Anarch)
Newsgroups: rec.puzzles,sci.math
Subject: Re: Circular graph problem
Date: 18 Dec 92 00:33:35 GMT
Followup-To: rec.puzzles
Organization: Secular Humanists from Hell

In article <1992Dec16.113500.1157@client24.comlab.ox.ac.uk>
mnewman@comlab.ox.ac.uk (Matthew Newman) writes:
> Consider circular graphs with N nodes, such that there is an integer
> at each node. Consider those integers K such that for some graph G
> each integer in [1..k] is the sum of integers at the nodes of some
> connected sub-graph G...
> ... I can do better than this and get the maximum possible k=13 like
> this :     (1)--(2)    and like this:   (1)--(3)
>             |    |                       |    |
>            (4)--(6)                     (2)--(7)

In article <1992Dec16.172145.21848@dartvax.dartmouth.edu> J.Theodore.Schuerzinge
r@dartmouth.edu (J. Theodore Schuerzinger) writes:
>I don't understand why these last two count as valid -- in the first,
>there's no combination that totals 4, while in the second there's no
>combination that totals 7.  Or am I just reading yet another problem
>incorrectly?!?

   A single node constitutes a connected subgraph.

-- 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-anarch@apple.com-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   "The Walpurgisnacht has become synonomous with any general revelry, and
     particularly for the breaking out of demonic lewdness and disorder."
D I S C L A I M E R :   E V E R Y T H I N G   I   W R I T E   I S   F A L S E
From: rmurphy@aludra.usc.edu (Bob Murphy)
Newsgroups: rec.puzzles
Subject: Re: Cute problem(generalized) [spoiler]
Date: 14 Dec 1992 00:23:08 -0800
Organization: University of Southern California, Los Angeles, CA
NNTP-Posting-Host: aludra.usc.edu

In article <Bz7Go6.16F@world.std.com> jkenton@world.std.com (Jeff Kenton) writes:
>Here's a problem I haven't seen before that I thought folks
>might enjoy:
>
>	Given the numbers 101, 10101, 1010101, ... (decimal, not binary)
>with 'n' 1's separated by 'n-1' 0's.  101 is prime.  Prove that none of
>the rest is prime.
>

In any integer base b with b >= 2 it turns out that 101 is the only
possible prime.

Let a[1] = 101
    a[2] = 10101
    a[3] = 1010101
      . 
      .
      . 

Now a[n] = b^(2n) + b^(2n-2) + ... + b^4 + b^2 + 1

which can be written in closed form as:

                b^(2n+2) - 1
        a[n] = --------------
                   b^2 - 1 

                (b^(n+1) - 1)*(b^(n+1) + 1) 
   or   a[n] = -----------------------------
                          b^2 - 1                 

Case 1: n is even
-----------------

b^(n+1) - 1 = (b - 1)*(b^n + b^(n-1) + ... + b^2 + b + 1)

The above is actually true whether n is even or odd but the 
following is true only when n is even.

b^(n+1) + 1 = (b + 1)*(b^n - b^(n-1) + ... + b^2 - b + 1)

Now since the denominator of a[n] is equal to b^2 - 1 or
(b - 1)*(b + 1) we see that this term cancels and we end up with:

a[n] = (b^n + b^(n-1) + ... + b + 1)*(b^n - b^(n-1) + ... - b + 1)

It's fairly easy to show that both factors are greater than 1.

Thus for n even we know that a[n] is composite.

Case 2: n is odd
----------------

Again we start with:

                (b^(n+1) - 1)*(b^(n+1) + 1)
        a[n] = -----------------------------
                          b^2 - 1

We have that:

b^(n+1) - 1 = (b^2 - 1)*(b^(n-1) + b^(n-3) + ... + b^2 + 1)

Now since the denominator of a[n] is equal to b^2 - 1 we see that 
this term cancels and we end up with:

a[n] = (b^(n-1) + b^(n-3) + ... + b^2 + 1)*(b^(n+1) + 1)

For n > 1 both of these factors are greater than 1 so for
n odd and greater than 1 we have that a[n] is composite.

Hence a[n] is never prime except for a[1] = 101 which may
or may not be prime depending on the base. 

In base ten we do get that 101 is indeed prime.


QUESTION:  For which bases is 101 prime?  This can be rephrased
           as: For which values of b is b^2 + 1 a prime?

I don't know the answer to this and I believe that it
may be a difficult problem.

                           Bob Murphy (rmurphy@aludra.usc.edu)
From: warwick@cs.uq.oz.au (Warwick Allison)
Newsgroups: rec.puzzles
Subject: Serial representation of arbitrary data
Date: 15 Dec 92 00:09:34 GMT
Reply-To: warwick@cs.uq.oz.au


This is a strange problem.  Maybe it has an obvious solution.


The problem is this:

	Represent a sequence of arbitrary length binary values.

Do it in as short a number of bits as possible.

For example, one solution is to represent

	10010010
	1001
        1010010
	11
	110111

As:
    000000001 10010010 00001 1001 00000001 1010010 001 11 0000001 110111
    "8 bits"  value    "4"   val  "7"      value   "2" v  "6"     value

ie. to precede each value with a sequence of 0s of the same length, and a 1.

This isn't optimal, surely.  For a start, every "value" is prefixed by
a "1" (except "0").

BTW,
Solution X should be considered better than solution Y if for a given N,
sequences of bitpatterns of length > N will take less bits with X than Y.

--
Warwick
--
  _-_|\      warwick@cs.uq.oz.au            /Disclaimer:
 /     * <-- Computer Science Department,  /  
 \_.-._/     University of Queensland,    /   C references are NULL && void*
      v      Brisbane, Australia.        /
From: J.Theodore.Schuerzinger@dartmouth.edu (J. Theodore Schuerzinger)
Newsgroups: rec.puzzles
Subject: World Puzzle Team Championships (was did you know...)
Date: 20 Dec 92 01:51:49 GMT
Organization: Dartmouth College, Hanover, NH
X-Posted-From: InterNews1.0b1@newshost.dartmouth.edu

While a Canadian did finish first individually, the US team place first
overall (by having their last of four place 9th individually).  One of
my friends here at Dartmouth was on the team.

--Ted Schuerzinger
email: .zed@Dartmouth.EDU
"I should have known it would be bad vodka when all the label said was
'Russian Vodka'."
Newsgroups: rec.puzzles
From: wvanweer@wsuaix.csc.wsu.edu (Wayne VanWeerthuizen)
Subject: Re: Paper Folding
Organization: Washington State University
Date: Thu, 17 Dec 92 13:48:38 GMT

In article <1992Dec17.120841.14563@thunder.mcrcim.mcgill.edu> mouse@thunder.mcrcim.mcgill.edu (der Mouse) writes:
>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]

Well, on opposite sides the stripes run the same way.  But, any two adjacent
sides have the stripes different. 

>>> 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?

Okay, the stripes run on only ONE side of the paper.  The paper can start
out with any shaped perimeter, but must be flat and one continuous piece.
(I thought the shape other than a rectangle was clear, because I said
that without the stripes, one can make a plain cube from a T shaped 
collection of 6 unit squares.)

Oh, and two more provisions.  If the paper is laid back flat after having
been folded, all the small sections delimited by the creases, must
be convex, with no holes.  And for two regions to be connected
they must share at least a line segment at the crease of length 1/2.
(These restrictions are to avoid problems with the area scoring.)

>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

My best is area 8. (Nine unit squares with parts corners cut, still following
the provisions above.) 

-- 
 ---------------------------------------------------------------------------
        Wayne VanWeerthuizen    205 Scott Hall     Pullman, WA  99163
           wvanweer@wsuaix.csc.wsu.edu      (509) 335-1835 (voice)   
 ---------- Only YHVH is God.  Jesus is the Messiah, Son of YHVH. ----------
Newsgroups: rec.puzzles
From: jz@kbs.citri.edu.au (Justin Zobel)
Subject: Re: Serial representation of arbitrary data
Organization: Collaborative Information Technology Research Institute
Date: 15 Dec 92 21:34:14 GMT

warwick@cs.uq.oz.au (Warwick Allison) writes:

>This is a strange problem.  Maybe it has an obvious solution.
>The problem is this:
>	Represent a sequence of arbitrary length binary values.
>Do it in as short a number of bits as possible.

Do you know the numbers in advance?  If so it is a standard compression
problem; the sequence has an entropy (theoretical minimun length) and
there are several algorithms that yield a representation very close to
that length.

If you don't know the numbers in advance, but expect lots of repetition
(or pattern of some form) then you can use adaptive compression.

So let's assume that neither of the above conditions hold, and also
assume that you know nothing about the distribution of the numbers (for
example, whether short numbers predominate) ... in which case the problem
is underspecified.  For some distributions, one code will be terrible and
another excellent; and vice versa for some other distribution.

>For example, one solution is to represent
>	10010010, 1001, 1010010, 11, 110111,
>    000000001 10010010 00001 1001 00000001 1010010 001 11 0000001 110111
>    "8 bits"  value    "4"   val  "7"      value   "2" v  "6"     value

Elias (Universal codeword sets and representations of the integers, IEEE
Transactions on Information Theory, vol 21, no 5) is probably the standard
reference for codes for arbitrary length integers.  His `gamma' code is a
little like the one above: represent x as floor(log2(x)) 0's followed by
x itself. Example:
    number:		1	2	3	4	5	...
    representation:	1	010	011	00100	00101	...

His `delta' code is similar, except that gamma is used to represent the
leading 0's.  These codes are excellent if small numbers predominate.

justin