MathDB

A switch has two inputs

1, 2

and two outputs

1, 2

. It either connects

1

1

and

2

2

, or

1

2

and

2

to 1. If you have three inputs

1, 2, 3

and three outputs

1, 2, 3

, then you can use three switches, the first across

1

and

2

, then the second across

2

and

3

, and finally the third across

1

and

2

. It is easy to check that this allows the output to be any permutation of the inputs and that at least three switches are required to achieve this. What is the minimum number of switches required for

4

inputs, so that by suitably setting the switches the output can be any permutation of the inputs?

Problem Statement