johna@haddock.UUCP (03/15/84)
#R:pucc-i:-21000:haddock:25400001:177600:70 haddock!johna Feb 27 15:03:00 1984 It appears there would be 297 balls left. johna @ ima!haddock
lief@hpfcrs.UUCP (lief) (10/15/84)
PROBLEM: Given 12 golf balls, one being odd (either heavier or lighter).
Determine which one is heavier or lighter with only 3 weighings
on a balance scale.
I don't know what the solution is supposed to be, but here is how I would
do it (same technique as Hamming codes are done):
(1) The balance scale can be thought of as a 3-state digit. In other words:
a. If the left is heavier than the right, the value is 0 (arbitrary).
b. If the left is ligther than the right, the value is 1
c. If the left is the same as the right, the value is 2
(2) Because of the 3-state nature of the balance scale, if we perform 3
seperate weighings, then that gives us 3^3 or 27 possibilities, which
should be sufficient. For our situation there exists 24 possibilities,
either 1 of the 12 balls will be heavier or 1 of the 12 balls will be
lighter.
(3) I will assign a unique 3 digit value to each golf ball (using 3-state
digits). This to is somewhat arbitrary, except that we would like the
heavy ball to be the complement of the light ball. Thus we have:
BALL ID HEAVY VALUE LIGHT VALUE
======= =========== ===========
a 000 111
b 001 110
c 002 112
d 010 101
e 102 012
f 120 021
g 121 020
h 122 022
i 210 201
j 211 200
k 212 202
l 221 220
Note that I did not use 011, 100, or 222. Obviously, there is no
complement for 2 since that is when both sides of the scale are equal.
Thus, one would not use 222 as it could not be unique.
(4) Divide the 12 golf balls into 3 groups of 4 and perform the 3 weighings
in the following order (determined by the values assigned above in (3)):
WEIGHING NUM LEFT SIDE RIGHT SIDE OFF SCALE
============ ========== ========== ==========
0 a b c d e f g h i j k l
1 a b c e d i j k f g h l
2 a d f i b g j l c e h k
Note that the left side corresponds to digit 0, the right side corresponds
to digit 1 and off scale corresponds to digit 2. Weighing number 0 corres-
ponds to the 1st digit of the ball value, weighing number 1 corresponds to
the 2nd digit of the ball value, and weighing number 3 corresponds to the
3rd digit of the ball value (1st digit is the left-most digit). Just in
case you don't understand this table, what I am saying is that in the 2nd
weighing, place balls a, b, c, and e on the left side, balls d, i, j, and
k on the right side, and balls f, g, h, and l off the scale.
(5) Example: Suppose on the first weighing, the sacles are equal. On the
second weighing the left side is heavier. On the third weighing, the
scales are equal again. This gives me a result of 202 (where 2 is assigned
for equality and 0 is assigned when the left side is heavier, as defined
above). Looking at the table in (3) shows that 202 corresponds to ball
k being lighter than all the other balls.
Example: Suppose on the first weighing, the left side is heavier. On the
second weighing the left side is heavier. On the third weighing, the
right side is heavier. This gives a result of 001. Looking at the table
in (3) shows that this corresponds to ball being heavier than all the other
balls.
Lief Sorensenlief@hpfcrs.UUCP (lief) (10/19/84)
In response to the SEND + MORE = MONEY puzzle:
SEND
+ MORE
------
MONEY
(1) D + E = 10*C1 + Y
(2) C1 + N + R = 10*C2 + E
(3) C2 + E + O = 10*C3 + N
(4) C3 + S + M = 10*M + O
where C1, C2, and C3 are the corresponding carries. These can be rewritten:
(4) C3 = 9*M + O - S
(5) C2 = 90*M + 9*O - 10*S + N - E
(6) C1 = 900*M + 90*O - 100*S + 9*N - 9*E - R
(7) D = 9000*M + 900*O - 1000*S + 90*N - 91*E - 10*R + Y (subs for C1 in (1))
assume C3=1, then from (4) M = (S - O - 1)/9 where M,S, and O are integers
less than or equal to 9. This equation is impossible for this stipulation
so therefore C3=0, and S=9, O=0, and M=1.
plug this result into (5) and C2 = N - E. We know that N is not equal to
E so therefore C2 must be 1 and E = N -1.
plug the above results into (6) and C1 = 9 - R. Since S is already 9, R
must be 8 and C1 must be 1. (Of course you agree that C1 can only be
either 0 or 1).
finally, play with (7) and D - Y = 10 - E. Let's assume that N = 7. Then
E = 6 since E = N - 1. Thus we have D - Y = 4. The only integer pairs
that can solve this is D,Y = 4,0 5,1 6,2 7,3 8,4 9,5. However,
one of the numbers in each pair is already defined so none of these will
work. Let's assume that N = 6 and of course E = 5. Then we have to fit
D - Y = 5. The possible solutions are D,Y = 5,0 6,1 7,2 8,3 9,4.
Note that both 7 and 2 have not been defined yet, so this pair is a
solution.
O=0 M=1 Y=2 E=5 N=6 D=7 R=8 S=9
9567
+1085
-----
10652 which is a correct solution (I didn't prove it was unique!)
Lief Sorensendsr@uvacs.UUCP (04/26/85)
I am not always in tune with netiquette and how and why people use the net. Do people who post puzzles do so in the spirit of a ice-breaker or are they really looking for the best answer or better, are they looking for references. I prefer the latter, but I am a stick in the mud sometimes. For example here are some known answers to recent postings: Longest one syllable word- Martin Gardner (all of whose books should be read and reread) in an uncollected column (about 6 years ago) mentioned the discovery SCHNAPSSED and BROUGHAMMED. (These are not in my WEB2 but as I recall they were in Random House (?).) Words in alphabetical order naturally- The long program given for this is far more complicated than the one-line egrep call in Kernighan & Pike (1984, p.104). They discovered, as Aho did years earlier while working on pattern matching, the word EGILOPS. Actually they missed the below-the-line (WEB2) variant AEGILOPS. Shortest word with all vowels- SEQUOIA (I dimly recall a foreign term with 6 letters ...) Vowels in order- FACETIOUSLY and ABSTEMIOUSLY are well-known but there are about 15 other examples that appeared in Word Ways:The Journal of Recreational Linguistics, an excellent source that settled these questions, and similar questions, years ago. 1000 Lockers- This appeared in the first issue of the now defunct 4-Star Puzzler (an offshoot of the excellent Games magazine) and appeared in Honsberger's column years ago and is based on well-known excersize in Number Theory texts. Shortest word list with letters in order- Do not recall the best known answer but is in Word Ways recently. And now a challenge that was posted in Word Ways: Find the smallest pangrammatic window in naturally occurring text, i.e. a contiguous set of letters containing all 26 letters. The current record is somewhat less than 100 letters.
chuck@dartvax.UUCP (04/27/85)
> > >> Find the smallest integer which can be broken up into: > > >> a^4 + b^4 = k > > >> c^4 + d^4 = k > > > > > >I'll start by giving you a hint: since it's the sum of two fourth powers > > >and must be odd it is necessarily of the form 8n+1. > > > > The reasoning behind this conclusion escapes me. Why must it > > be odd? > > It's fairly simple: assume k is even. Then we have one of two cases either > a and b must be even or a and b must be odd. Either assumption leads to > a simple algebraic demonstration by infinite descent that there must be > a smaller solution. Call me dense, but this little "hint" doesn't do anything for me. I see 3 cases: clearly a = b mod 2 and c = d mod 2. So the 3 cases are a even, c even; a odd, c odd; a even, c odd. I can handle the first of these cases. But for the rest, I remain clueless. Could you provide a slightly more elaborate hint? -- Chuck Simmons
doug@terak.UUCP (04/29/85)
I can guarantee that the "measure the height of a building with a
barometer" question with its unexpected answers was around at least in
1966, when my high-school Physics teacher distributed a mimeographed
copy to the class. I didn't keep it (or if I did, I don't know where
to find it). My favorite answer was the one about trading the barometer
for the required info. Other answers: time how long it takes to fall
from the top of the building; tie it to a string, lower it from the roof
and measure the length of the string; swing it from a string and time
the period of the pendulum; measure it with a ruler and measure the
building with it; and measure it, its shadow, and the building's shadow
with a ruler and triangulate.
--
Doug Pardee -- Terak Corp. -- !{hao,ihnp4,decvax}!noao!terak!dougjeff@hpcnoe.UUCP (jeff) (05/16/85)
>>> How about generalizing it, lets assume that the gold originally >>> weighed K pounds and was broken into n pieces, what are the weights >>> of the n pieces given that the above property still holds ? >>In general, we want to break it into blocks of 3^n for n going from >>0 up as high as possible. I think that leaving the leftover as just one >>block will be good enough to weigh everything, by always using that >>block for weights above it. > Yes, but...suppose the problem is: break a 40-lb block into *5* pieces? > Then, using 3^n, we get 1 3 9 27 *0*. How would you do this? I assume > that any of them could just be broken in two, but your answer should have > included this case. Or the case 40-lb block into 3 pieces, which there is no solution. Or the case 40-lb block into 41 pieces, which means that at least two blocks would be non-integral lb weights. There is an algorithmic way of calculating if there is no solution for a given n, K. Is there a mathmatical formula which does this? Jeff Wu / CNO Hewlett-Packard Fort Collins CO
larry@hpfclg.UUCP (larry) (06/22/85)
/***** hpfclg:net.puzzle / dartvax!chuck / 12:24 am Jun 17, 1985*/
The following 5 instruction routine is written in 68000 code.
What does it do?
; D0 and D1 are 32 bit registers.
move.l d0,d1 ; d1 := d0
bra.s L2 ; goto L2
L1: sub.l d1,d0 ; L1: d0 := d0 - d1
L2: lsr.l #1,d1 ; L2: d1 := d1 div 2
bne.s L1 ; if d1 <> 0 then goto L1
Cheers, Chuck
/* ---------- */
*** SPOILER ***
(rot13)
Gur cerprqvat pbqr frdhrapr jvyy pnyphyngr gur ahzore bs 1 ovgf va Q0.
N ybbc vainevnag orgjrra Y1 & Y2 pbhyq or cuenfrq nf sbyybjf:
Gur ahzore bs ovgf va Q1 cyhf gur qvssrerapr Q0-Q1 vf vainevnag.
Ng gur ortvaavat Q0=Q1 fb gur inyhr bs gung vainevnag rkcerffvba vf
jung jr jnag. Ng gur raq Q1=0 fb gur inyhr bs gur vainevnag
rkcerffvba vf Q0. Rnpu gvzr guebhtu gur ybbc gurer vf 1 bs 2 pnfrf:
Q1 vf bqq, be Q1 vf rira. Vs Q1 vf rira, fuvsgvat qbrfa'g punatr
gur ahzore bs 1 ovgf va Q1 naq Q0-Q1 vf gur fnzr nsgre gur fhogenpgvba.
Vs Q1 vf bqq, fuvsgvat erzbirf n 1 ovg va Q1 naq Q0-Q1 vapernfrf ol 1.
Guvax bs Q0 nf orvat Q1+A. Vs Q1 vf bqq gura Q1=Q1/2+Q1/2+1 (vagrtre
qvivfvba), fb Q1-Q1/2=Q1/2+1. Gur arj Q1 vf Q1/2 fb gur arj Q0 vf
Q1+1+A, whfg nf jr jnag.
V ernyvmr gur rkcynangvba vf n ovg whzoyrq, ohg V qvq vg zber sbe
zlfrys guna sbe lbh.
Yneel Srafxr
{vuac4, ucynof}!ucspyn!yneel-s
Larry Fenske
{ihnp4, hplabs}!hpfcla!larry-flarry@hpfclg.UUCP (larry) (07/12/85)
I always thought it was "ram it in".
stephen@datacube.UUCP (10/18/85)
>> Identify the sequencing algorithm for this list of numbers: >> >> 8 >> 5 >> ... >> !inhp4!cmcl2!acf4!odom >Alphabetical order would account for it. >--henry schaffer >/* ---------- */ Which alphabet has digits in it? Stephen Watkins UUCP: ihnp4!datacube!stephen Datacube Inc.; 4 Dearborn Rd.; Peabody, Ma. 01960; 617-535-6644
brianu@ada-uts.UUCP (11/25/85)
>***** ada-uts:net.puzzle / bbncc5!ldenenbe / 11:08 am Nov 19, 1985 >The Massachusetts State Megabucks Lottery works like this: A ticket costs >$1 and consists of six distinct numbers of your choosing between 1 and 36 >inclusive. You may buy as many tickets as you like. On Lottery Day >the Authorities choose six numbers. If those six are the same as your >six, you win! (There may be many winners, since other players may have >chosen the same set of six numbers. You split the Big Bucks equally.) >There are lesser prizes for matching five, four, and three numbers. > >What is the minimum number of tickets that you must buy to ensure that >at least one of your tickets matches two or more of the winning numbers? Well, there are 36*35/2 = 630 different combinations of two numbers 1-36. Suppose that they only choose 2 numbers rather than 6. Those 2 nuumbers must be one of the 630 combinations. To ensure that you have at least one ticket with this combination, you must buy enough tickets to cover all the pairs. Each ticket covers 15 pairs, so you must by at least 630/15=42 tickets. This is assuming you can find a covering without overlap. (this may or may not be possible) Since they draw 6 rather than 2 numbers, you will match all 15 pairs generated. So this method guarantees 15 pairs rather than the required 1. However, if there does not exist a non-overlapping covering of the 630 pairs, the nummber required can be reduced. So we have 42 tickets as the maximum that may be required. Brian Utterback Intermetrics Inc. UUCP:{cca,ihnp4}!ima!inmet!ada-uts!brianu
tgralewi@ti-csl (02/28/86)
In my days as an under graduate I was required to create a general solution
to the "scheduling problem" as previously stated.
As previously stated the solution is non trivial, the one we (my class) did
consisted of a general set of constraints and lists of people and the hours
and days each person could work. The final solution was written in LISP
(not my favorite language but ideal for this kind of problem). The program
took as input a set of lists containing the afore mentioned information and
basicaly used itteration (by recursion and list pruning) to try every possible
combination until one fit all the constraints.
The program took the first possible worker that could fill the next slot open
and removed him from the lists and called itself with the new lists and
new time slots, if the returned value was unsuccessful the next person was
selected, etc.
The program was not trivial (about 20 or 30 pages of LISP) and slow (of the
5 or so programs that actualy worked they took from 1 to 24 hours to run).
The data we used to test the system was something of the form:
8 employees
4 week repeated schedule
Each must have 3 two day weekends and 1 three day weekend
No person may work 2 shifts without at least 2 shifts gap
whenever possible a person must not change shifts (1st, 2nd, or 3rd)
more than twice in one shedule
Personal vacations may be added in and need to be scheduled
(this was the reason for a program instead of just a fixed schedule)
No more than 40 hours per person per week
2 people on each shift
There were also some constraints about adding half days etc, but I don't
remember them.
Just my 2 cents worth (looks more like about $.36 but it's only worth $.02)
Discalimer? (I disclaim having a disclaimer)
Return address? (I am still trying to figure that one out)