wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> CAML
        
(Message started by: Felix on Jun 16th, 2003, 11:28pm)
Title: CAML
Post by Felix on Jun 16th, 2003, 11:28pm
This was a question on a state high school test last year (CAML) with very, very few people actually getting it right. I want to see how hard it is for you guys.

If x satisfies the equation Arc cos x + Arc cos 2x + Arc cos 3x = pi, for what ordered triple of integers (a,b,c) will x also satisfy ax3 + bx2 + cx - 1 = 0?

While I'm at it, here's another one:
Find the least positive integer using 1-9 exacly once that is evenly divisible by each of these digits.
Title: Re: CAML
Post by Leonid Broukhis on Jun 17th, 2003, 12:25am
The least positive number that is evenli divisible by 1 to 9 is 2520 = 9*8*7*5.
So, the answer is, trivially, [hide] 9*8*7*6*5/4/3*2*1 [/hide].
Title: Re: CAML
Post by THUDandBLUNDER on Jun 17th, 2003, 2:51am

Quote:
The least positive number that is evenli divisible by 1 to 9 is 2520 = 9*8*7*5.

2520 = 9*8*7*5 is not evenly divisible by 8. But 7! = 5040 is.  
 
So I think the question asks to find the smallest number which is divisible by 5040,
and that uses all the digits 1-9 exactly once.

But a number that is divisible by 5040 will have 0 as its last digit.
We are allowed to use the digits 1-9 once only. Nothing is said about 0.
So, as I see it, we must also be allowed an arbitrary number of 0's.
Title: Re: CAML
Post by wowbagger on Jun 17th, 2003, 3:40am

on 06/17/03 at 02:51:47, THUDandBLUNDER wrote:
2520 = 9*8*7*5 is not evenly divisible by 8.

???
Do you understand "evenly divisible" to mean "divisible, and the result is even"? I don't think this is intended.


Quote:
So I think the question asks to find the smallest number which is divisible by 5040,
and that uses all the digits 1-9 exactly once.

The part about the digits from 1 to 9 appearing exactly once is important. Maybe Leonid overlooked this.
Title: Re: CAML
Post by THUDandBLUNDER on Jun 17th, 2003, 3:51am

Quote:
Do you understand "evenly divisible" to mean "divisible, and the result is even"? I don't think this is intended.

I see. So it just means 'divisible'?
Given that there seems to be no 'oddly divisible', this usage seems unnecessarily confusing.

But my later argument still holds.


Quote:
The part about the digits from 1 to 9 appearing exactly once is important. Maybe Leonid overlooked this.

The reason is, trivially, that Leonid is still thinking of Sir Col's pandigital products.   :D
Title: Re: CAML
Post by LZJ on Jun 17th, 2003, 4:41am
You guys aren't answering the question (the 1st one, anyway)  ;D

I think it is (12,14,0), but I only tried for 10 minutes so I didn't check the solution...

For the 2nd question, I think Felix has to clarify whether he wants the answer as, say 135792468, or 1*3*5*7/9/8/6*4*2... (these aren't the answers, of course)
Title: Re: CAML
Post by THUDandBLUNDER on Jun 17th, 2003, 9:34am

Quote:
You guys aren't answering the question (the 1st one, anyway)

OK, LZJ, I'll take care of the 2nd one and will leave the 1st for you. Deal?

The required pandigit number must be divisible by all the digits 1-9.

HCF of these digits = 23.32.5.7 = 2520

Now, we don't need to worry about the 32 because the sum of the digits of any pandigital number = 45,
which is divisible by 9. Hence, all pandigital numbers are divisible by 9.

And the factor of 10 means the last digit of our required number is 0.
This means we must multiply our initial pandigital number by 10.
So this takes care of a factor of 2 and the factor of 5.

We are now left with 22.7

As it is the smallest, let us take 123456789 as our initial pandigital number.
It is perhaps a surprising fact that 123456789 x 14 gives 1728395046, another pandigital number!
(This is also true for 2,4,5,7,8,10,11,13,16, 17, and more.)

So we are left with just a factor of 2.

That is, 17283950460 is divisible by all the digits 1-9, except 8.  :'(

To get around this is we need to multiply 17283950460 by 10.

So that we finally get (muffled roll of drums)

172839504600
Title: Re: CAML
Post by BNC on Jun 17th, 2003, 10:12am

on 06/17/03 at 09:34:28, THUDandBLUNDER wrote:
So that we finally get (muffled roll of drums)

172839504600


Nice. However, I think that 1234857960 will do the trick, and is somewhat smaller.
Title: Re: CAML
Post by THUDandBLUNDER on Jun 17th, 2003, 10:21am

Quote:
Nice. However, I think that 1234857960 will do the trick, and is somewhat smaller.

Hmm...how did you find that? By brute force (the last resort of the exhausted mind)?   :P
Title: Re: CAML
Post by James Fingas on Jun 17th, 2003, 10:34am
I get a smaller answer, which I believe is optimal: [hide]1234759680[/hide].

My search was certainly brute force. First I found this solution: 1235679480, and then I looked for all solutions smaller than this. Notice that the second-last and third-last digits have to be divisible by 4 when you put them side by side, and then brute-force look for solutions that are also divisible by 7. There is a formula you can use for divisibility by 7, but I think brute force was quicker (even with me generating all the combinations by hand).
Title: Re: CAML
Post by Sir Col on Jun 17th, 2003, 10:37am
I'm not convinced about that first question at all.

This is what I've got so far:

From cos-1x+cos-12x+cos-13x=pi, we let a=cos-1x, b=cos-12x and c=cos-13x.

Therefore a+b=pi–c and sin(a+b)=sin(pi–c)=sin(c).

sin(a)cos(b)+cos(a)sin(b)=sin(c).

sin(cos-1x)cos(cos-12x)+cos(cos-1x)sin(cos-12x)=sin(cos-13x).

As sin(x)=sqr(1–cos2(x)), sin(cos-1x)=sqr(1–x2).

Therefore 2x*sqr(1–x2)+x*sqr(1–4x2)=sqr(1–9x2)

Squaring both sides and simplifying,
4x2sqr(4x4–5x2+1)=8x4–14x2+1.

Squaring again and simplifying leads to,
144x6–196x4+28x2–1=0.

I don't see how this can be related to the cubic, unless I've made an error in with my simplifying?
Title: Re: CAML
Post by James Fingas on Jun 17th, 2003, 12:33pm
The problem is simpler if you take the cosine instead of the sine. Then you don't have to square twice. But I think you've got the gist of the solution.

Your sextic doesn't factor nicely using my cubic, but one or both of use probably screwed up the math at some point ...
Title: Re: CAML
Post by NickH on Jun 17th, 2003, 1:06pm
I think James and Sir Col have solved it.  I get...

::[hide]a = 12, b = 14, c = 0[/hide]::
Title: Re: CAML
Post by Sir Col on Jun 17th, 2003, 3:24pm
Silly me! Thanks for the encouragement to continue...
:: [hide]The hextic, 144x6–196x4+28x2–1=0, factors to make (12x3–14x2+1)2=0, hence a=12, b=14, c=0.[/hide] ::

Was this really set as a high school question?
Title: Re: CAML
Post by LZJ on Jun 17th, 2003, 3:27pm
For question 1, there's a much simpler way, actually: just use the cosine rule, and solve the simultaneous equations.
Title: Re: CAML
Post by Felix on Jun 17th, 2003, 9:53pm
Yeah, it was part of a statewide test for a math competition in California (called the CAML). I think somewhere around ten students or so got it correct (out of hundreds of thousands).
Title: Re: CAML
Post by THUDandBLUNDER on Jun 17th, 2003, 10:28pm
And how about the 2nd one? I don't think there's any analytical method to find the least positive integer,
at least not without a programmable calculator.

Title: Re: CAML
Post by Sir Col on Jun 18th, 2003, 12:30am

on 06/17/03 at 15:27:54, LZJ wrote:
For question 1, there's a much simpler way, actually: just use the cosine rule, and solve the simultaneous equations.

Easier?! I tried that option when I saw that a+b+c=pi, but solving the simultaneous equations did not seem like an easy option. What trick did you use, LZJ?

I agree, T&B. I can't find any analytical method to solve the second problem. In the end I worked from the principle that the number must be a multiple of 2520 (the minimum value that is divisible by 1 to 9) and got a computer to count in steps of 2520, checking the string of digits once it reached at least a 9-digit number.
Title: Re: CAML
Post by Sir Col on Jun 18th, 2003, 12:32am
Hey, I just realised that my last post count was 124. A really cheap person would make a completely pointless post just to reach Uberpuzzler status!  ::)
Title: Re: CAML
Post by THUDandBLUNDER on Jun 18th, 2003, 12:49am

Quote:
A really cheap person would make a completely pointless post just to reach Uberpuzzler status!  

Hehe. You are more prescient than you realized. You don't get promoted until #126!  ::)
Title: Re: CAML
Post by Sir Col on Jun 18th, 2003, 12:55am
No one can say there was no point to this post => .  :P
Title: Re: CAML
Post by Felix on Jun 18th, 2003, 12:42pm
The second one was just a problem I found on the internet quite a while ago, not part of any test.
Title: Re: CAML
Post by Sir Col on Jun 18th, 2003, 5:28pm
It was an interesting problem to work on, Felix.

Do you have any more challenging problems from the state high school tests?
Title: Re: CAML
Post by BNC on Jun 18th, 2003, 11:34pm
A delayed answer to T&B's:


on 06/17/03 at 10:21:29, THUDandBLUNDER wrote:
Hmm...how did you find that? By brute force (the last resort of the exhausted mind)?   :P


I didn’t use brute force.

First, I noticed that sum(1..9)=45, thus divisibility by 3 and 9 are granted. The requirement for divisibility by 5 and 2 means an LSB of 0. So, we’re talking about a 10-digit number, with all the digits 0..9 once, and the 0 as the LSB. This, by itself, takes care of the divisibility by 1,2,3,5,6,9. Left to take care: 4,7,8.
The 4 and 8 are handled by the 3-digit number that is the LSBs of the number. I wanted to place the highest possible value digits in there, to I chose 9 (that is why I got a sub-optimal answer). The best combination with 9 is 960 as the lower 3 digits.

Now, we have a number _ _ _ _ _ _ _ 960, with all the digits somewhere, and is already divisible by 1,2,3,4,5,6,8,9. We have a LOT of degrees of freedom to take care of the missing 7. What I did now was simply to assume MSBs of 1234, and thus the number became 1234_ _ _ 960. The remaining digits {5,7,8} are placed in positions that will ensure divisibility by 7 (the +1,+3,+2,-1,-3,-2… rule). From there it’s easy to find my answer of 1234857960.

My mistake was not noticing that the '8' "sneaked" to a high-value position. I should have checked the number with 680 LSB, and would have got James Fingas’s answer (which, I agree, is optimal).
Title: Re: CAML
Post by Felix on Jun 19th, 2003, 9:36pm
Unfortunately, I think I already got rid of the other tests that I have, so I have no other questions from these tests. All of them are much easier than the arc cosine one though.
Title: Re: CAML
Post by LZJ on Jun 21st, 2003, 2:25am
Sorry for not posting my reply before...

Let cos-1x be a, cos-12x be b, cos-13x be c, and let a, b and c be the angles of a triangle.
Let the length of the triangle side opposite angle a be A, and similarly for the other 2 angles.

Using cosine rule,
C2 = A2 + B2 - 6ABx --(1)
(since cos(c) = 3x)
B2 = A2 + C2 - 4ACx --(2)
A2 = B2 + C2 - 2BCx --(3)

Simplify:
Example of simplification...sub (3) into (2)
B2 = (B2 + C2 - 2BCx) + C2 - 4ACx
2C2 = 2C(2Ax + Bx)
Since A, B, C > 0,

C = 2Ax + Bx
B = 3Ax + Cx
A = 2Cx + 3Bx

C = 4Cx2 + 6Bx2 + Bx,
C(1 - 4x2) = B(6x2 + x)

B = 9Bx2 + 6Cx2 + Cx,
B(1 - 9x2) = C(6x2 + x)

1 + 36x4 - 13x2
= 36x4 + x2 + 12x3

12x3 + 14x2 - 1 = 0

See? Readily solvable in less than 10 minutes  ;)
Title: Re: CAML
Post by Sir Col on Jun 21st, 2003, 3:24am
Very impressive, LZJ, and thanks for taking the time to share your solution. When I tried it, I missed the rather obvious fact that A,B,C>0!  :-[


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board