Problem 703

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
albert
Posts: 54
Joined: Sat Aug 02, 2008 12:36 pm

Problem 703

Post by albert »

How can S(3) ever be 35?
The total number of function to select from (B^3 -> B) is 16 and 35 is greater than that !
Here goes a full table of all function B^3 -> B
TTT T
TTT F
TTF T
TTF F
TFT T
TFT F
TFF T
TFF F

FTT T
FTT F
FTF T
FTF F
FFT T
FFT F
FFF T
FFF F

Groetjes Albert

DJohn
Posts: 57
Joined: Sat Oct 11, 2008 12:24 pm

Re: Problem 703

Post by DJohn »

Each function from B^3 to B maps three inputs to one output. There are 8 possibilities for the input, and a function is specified by giving an output independently for each of them. There are 2^8 = 256 ways of doing this, so there are 256 possible functions. In general, there are 2^(2^n) functions from B^n to B.

For two inputs, there are 16 functions. Here they are:

Code: Select all

A  B   out       A  B   out       A  B   out       A  B   out
0  0   0         0  0   0         0  0   0         0  0   0
0  1   0         0  1   0         0  1   0         0  1   0
1  0   0         1  0   0         1  0   1         1  0   1
1  1   0         1  1   1         1  1   0         1  1   1

A  B   out       A  B   out       A  B   out       A  B   out
0  0   0         0  0   0         0  0   0         0  0   0
0  1   1         0  1   1         0  1   1         0  1   1
1  0   0         1  0   0         1  0   1         1  0   1
1  1   0         1  1   1         1  1   0         1  1   1

A  B   out       A  B   out       A  B   out       A  B   out
0  0   1         0  0   1         0  0   1         0  0   1
0  1   0         0  1   0         0  1   0         0  1   0
1  0   0         1  0   0         1  0   1         1  0   1
1  1   0         1  1   1         1  1   0         1  1   1

A  B   out       A  B   out       A  B   out       A  B   out
0  0   1         0  0   1         0  0   1         0  0   1
0  1   1         0  1   1         0  1   1         0  1   1
1  0   0         1  0   0         1  0   1         1  0   1
1  1   0         1  1   1         1  1   0         1  1   1

User avatar
kenbrooker
Posts: 140
Joined: Mon Feb 19, 2018 3:05 am
Location: Northern California, USA

Re: Problem 703

Post by kenbrooker »

For those more conversant in Computer Science than Mathematics, the following translation of
Problem 703 may be helpful, if not invaluable --

A k-input binary Truth Table is a map from k input bits (0=False; 1=True) to 1 output bit.
For example, the 2-input binary Truth Tables for the logical AND and XOR functions are:

              x y             xANDy            xXORy
              - -            -------          -------
              0 0               0                0
              0 1               0                1
              1 0               0                1
              1 1               1                0

As a further example, we can demonstrate that three 2-input binary Truth Tables, T, satisfy
the formula T(x, y) AND T(y, xANDy) = 0 for all 2-bit inputs (x, y) as follows:

                             Tables(x, y)
 x, y      [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P]

 0, 0      [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
 0, 1      [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
 1, 0      [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1]
 1, 1      [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

    z = xANDy                Tables(y, z)
 y, z      [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P]

 0, 0      [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
 1, 0      [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1]
 0, 0      [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
 1, 1      [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

            &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

                          T(x, y) AND T(y, z)
 x, y,(z)  [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P]

 0, 0, 0   [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
 0, 1, 0   [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1]
 1, 0, 0   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1]
 1, 1, 1   [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

               Tables A, C & E all zero for a Count = 3

Additionally, there are 2118 4-input binary Truth Tables, T, that satisfy
the formula T(a,b,c,d) AND T( (b,c,d,a) AND (bXORc) ) = 0 
for all 4-bit inputs (a,b,c,d).

How many 20-input binary truth tables, T, satisfy the formula
T(a,b,c, ... t) AND T( (b,c,d, ... t,a) AND (bXORc) ) = 0
for all 20-bit inputs (a,b,c, ... t)?
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

Post Reply