wu :: forums - Print Page


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

        riddles >> medium >> 1 3 5 7 9
        
(Message started by: Leonid Broukhis on Feb 4^th, 2005, 12:01am)

Title: 1 3 5 7 9
Post by Leonid Broukhis on Feb 4^th, 2005, 12:01am

What is the smallest nonnegative integer that cannot be represented as an expression that involves only numbers (as opposed to digits) 1, 3, 5, 7, 9 - each one exactly once - and uses only basic four arithmetic operations? What is the largest integer that can be represented?

Title: Re: 1 3 5 7 9
Post by towr on Feb 4^th, 2005, 12:41am

Are we allowed to use single digit numbers?

Title: Re: 1 3 5 7 9
Post by Leonid Broukhis on Feb 4^th, 2005, 12:53am

Single digit numbers (namely 1, 3, 5, 7 and 9) are the only numbers that are allowed.

Title: Re: 1 3 5 7 9
Post by towr on Feb 4^th, 2005, 2:46am

so [hide](9-7)/(5-3)-1=0[/hide]
and [hide]3*5*7*(9+1)=1050[/hide] ?
Or can we also only use each arithmetic operator only once?

Title: Re: 1 3 5 7 9
Post by Barukh on Feb 4^th, 2005, 5:23am

Towr, I think you misinterpreted the first question:

on 02/04/05 at 00:01:31, Leonid Broukhis wrote:

What is the smallest nonnegative integer that CANNOT be represented as an expression that involves only numbers 1, 3, 5, 7, 9 - each one exactly once - and uses only basic four arithmetic operations?

…and there is a better candidate for the second answer: [hide](1+3)*5*7*9 = 1260[/hide].

Title: Re: 1 3 5 7 9
Post by John_Gaughan on Feb 4^th, 2005, 6:29am

The first few nonnegative integers are relatively easy:
::[hide]
0 == (9-7)/(5-3)-1
1 == 9-7-5+3+1
2 == (9-7)/(5-3)+1
3 == 9-7+5-3-1
4 == 9/3+7-5-1
5 == 9-7+5-3+1
6 == 9/3+1+7-5
7 == 9+7-5-3-1
8 == 1*9+7-5-3
9 == 9+7-5-3+1
10 == 9*5/3-1*5
11 == 9-7+5+3+1
12 == (9-5-1)*(7-3)
13 == 9+7-5+3-1
14 == 9+7-5+3*1
15 == 9+7-5+3+1
16 == (9-7)*(5+3)*1
17 == 9+7+5-3-1
18 == 9+7+5-3*1
19 == 9+7+5-3+1
20 == 5*(9+7)/(3+1)
21 == 5*(7-9/3)+1
22 == 5*(9-3)-7-1
23 == 9+7+5+3-1
24 == 5*(9-3)-7+1
25 == 9+7+5+3+1
26 == (9/3)*7+5*1
27 == (7+5-3)*9/3
28 == 7*(9-1)/(5-3)
29 == 3*(9-7)*5-1
30 == 3*(9-7)*5*1
31 == 7*3*(9+1)/5
32 == (9+7)*(5-3)*1
33 == 9*(7+5-1)/3
34 == (9+7+1)*(5-3)
35 == 7*(9+1)/(5-3)
36 == (7+3-1)*(9-5)
37 == (9/3)*(7+5)+1
38 ==
39 == 9*(7+5+1)/3
40 == (9+1)*(7+5)/3
41 ==
42 == 7*3*(9+1)/5
[/hide]::

I will fill in more as I figure them out.

Title: Re: 1 3 5 7 9
Post by asterix on Feb 4^th, 2005, 7:18am

Just to fill in the one you skipped. [hide]21=5*(7-(9/3))+1[/hide]

Title: Re: 1 3 5 7 9
Post by Leonid Broukhis on Feb 4^th, 2005, 8:13am

on 02/04/05 at 02:46:32, towr wrote:

so [hide](9-7)/(5-3)-1=0[/hide]
and [hide]3*5*7*(9+1)=1050[/hide] ?
Or can we also only use each arithmetic operator only once?

What is the smallest number that cannot be represented?
I expected the largest number part to be a "think again" question, and it worked. A cognitive scientist may be able to explain why it works.
Using each operation only once is too restrictive. :)

Title: Re: 1 3 5 7 9
Post by rmsgrey on Feb 4^th, 2005, 8:34am

I can get ::[hide]1260=(1+3)*5*7*9[/hide]:: for "largest possible"

Title: Re: 1 3 5 7 9
Post by Grimbal on Feb 4^th, 2005, 9:59am

on 02/04/05 at 08:13:23, Leonid Broukhis wrote:

What is the smallest number that cannot be represented?

-[infty]?

Title: Re: 1 3 5 7 9
Post by Leonid Broukhis on Feb 4^th, 2005, 10:17am

on 02/04/05 at 09:59:59, Grimbal wrote:

-[infty]?

I did say "nonnegative integer" in the original posting.

Title: Re: 1 3 5 7 9
Post by Barukh on Feb 5^th, 2005, 12:19am

I get [hide]122[/hide] for the first question.

Title: Re: 1 3 5 7 9
Post by Barukh on Feb 5^th, 2005, 12:30am

on 02/04/05 at 08:13:23, Leonid Broukhis wrote:

What is the smallest number that cannot be represented?

I get [hide]122[/hide].

Leonid, do you know what is second smallest such number?

on 02/04/05 at 08:13:23, Leonid Broukhis wrote:

I expected the largest number part to be a "think again" question, and it worked. A cognitive scientist may be able to explain why it works.

Could you explain this (are you a cognitive scientist? ;))

Title: Re: 1 3 5 7 9
Post by Leonid Broukhis on Feb 5^th, 2005, 11:49am

on 02/05/05 at 00:30:10, Barukh wrote:

I get [hide]1xx[/hide].

Leonid, do you know what is second smallest such number?

Could you explain this (are you a cognitive scientist? ;))

1xx is right. Second smallest is 1xx + 16. If you're asking, does it mean that you have not automated the search process? :o
I have a list of all numbers that can be represented.

Title: Re: 1 3 5 7 9
Post by Leonid Broukhis on Feb 5^th, 2005, 11:52am

on 02/05/05 at 00:30:10, Barukh wrote:

Could you explain this (are you a cognitive scientist? ;))

Not rigorously, but I guess that the subconscious "make biggest part bigger to make the whole look bigger" has something to do here.

Title: Re: 1 3 5 7 9
Post by Sir Col on Feb 5^th, 2005, 5:20pm

And the next such number is 1xx+24. ;)

Nice problem, Leonid.

As an extension...

(1) Up to the maximum value expressible using the odd numbers: 1, 3, 5, 7, 9, what percentage of numbers can be obtained?

(2) What if the even numbers: 0, 2, 4, 6, 8, are used instead?

Title: Re: 1 3 5 7 9
Post by Leonid Broukhis on Feb 5^th, 2005, 6:36pm

on 02/05/05 at 17:20:03, Sir Col wrote:

And the next such number is 1xx+24. ;)

Nice problem, Leonid.

Inspired by making 24 out of 1, 3, 4, 6.

Quote:

As an extension...

(1) Up to the maximum value expressible using the odd numbers: 1, 3, 5, 7, 9, what percentage of numbers can be obtained?

I get 28.47%

Quote:

(2) What if the even numbers: 0, 2, 4, 6, 8, are used instead?

20.52%

And if numbers 1, 2, 3, 4, 5 are used, then it is 67.40%

For 1, 2, 3, 4 it is 86.49%

For 1, 2, 3 it is 100% :)

Title: Re: 1 3 5 7 9
Post by Sir Col on Feb 6^th, 2005, 2:53am

I'm intrigued to know what approach you used.

I used postfix (reverse Polish) notation with permutations of the given numbers. For those unfamiliar, a couple of examples will demonstrate how this system allows for unambigous stack/array calculations without the need for brackets/parentheses:
3 4 + 2 * = 7 2 * = 14
2 17 13 - / 11 + = 2 4 / 11 + = 0.5 11 + = 11.5

Then using a collection of masks I inserted all combinations of the arithmetic symbols at the appropriate places.

For example, when working with four numbers: a, b, c, d, the three arithmetic symbols (#) can legally be placed in the following places:
a b c d # # #
a b c # d # #
a b c # # d #
a b # c d # #
a b # c # d #

It turns out that the number of masks for a set of n numbers is given by C(2n-2,n-1)/n, which is the (n-1)th Catalan number [nth Catalan = C(2n,n)/(n+1)]. So I used fourteen masks for a set of five numbers.

Title: Re: 1 3 5 7 9
Post by Leonid Broukhis on Feb 6^th, 2005, 10:17pm

I used putting 1 3 5 7 9 or whatever set of numbers in a vector, randomly taking two elements (== shuffling the vector and taking 1st and 2nd elements), applying a random operation and putting the result back, then iterating until the vector has one element (keeping track of how it was achieved, of course). If its value is an integer and it has not been seen before, the generating expression is output. Not strict, but does the job. I take it that my percentages match yours, right?

Title: Re: 1 3 5 7 9
Post by Sir Col on Feb 7^th, 2005, 6:30am

They're very close, but not quite the same as mine. I get:

358/1260~=28.413% for 1, 3, 5, 7, 9
78/384=20.3125% for 0, 2, 4, 6, 8
121/180=67.222...% for 1, 2, 3, 4, 5
31/36=86.111...% for 1, 2, 3, 4

Title: Re: 1 3 5 7 9
Post by Leonid Broukhis on Feb 7^th, 2005, 8:40am

I've included 0 as well. 359/1261, etc. I thought that giving 4 significant digits of the percentages will allow to find out the cause of the possible discrepancy.