Question

There is an auction in which exactly two 2 bidders are interested; \(A\) and \(B\).
The bidding starts at $0, and neither bidder has more than $100; so whomever bids $100 will win.
Valid bids must be $10, $20, or $50, above the previous bid.

Q: How many different combinations of legal bids; adding to $100 are there, what are they, and how does this relate to the state graph?

Answer 1

I’ve made this state graph (below),
but I’m not sure how to explicitly express all the combinations/permutations.

Answer 2

Seems like there are lots, and lots. . .

Answer 3

By the phrase 'different combinations':
does the question mean that
50,20,10,20
& 50,20,20,10
& 50,10,20,20, etc are different combinations or the same ?

Answer 4

if different permutations don't count,
The 'combinations' I have are:

50,50
50,20,20,10
50,20,10,10,10
50,10,10,10,10,10
20,20,20,20,20
20,20,20,20,10,10
20,20,20,10,10,10,10
20,20,10,10,10,10,10,10
20,10,10,10,10,10,10,10,10
10,10,10,10,10,10,10,10,10,10

Answer 5

I don't know how this relates to the state graph

Answer 6

we want to find number of nonnegative integer solutions to
\[10a+20b+50c=100\]
right ?

Answer 7

yeah, that is right

Answer 8

divide 10 each side and get
\[a+2b+5c=10\]

Answer 9

yeah, go on

Answer 10

\[a \in \{0,1,2,3,4,5,6,8,10\}\\
b \in \{0,1,2,3,4,5\}\\
c \in \{0,1,2\}\]

Answer 11

One linear equation with three unknowns, ...
i'm stuck

Answer 12

this can be solved but reading the problem again, i feel solving this eqn is not so much useful because 10a = 100 is not a valid state for A.

Answer 13

10+10+10+10+.... is not a valid state for bidding of A

Answer 14

Why isn't, the case of ten successive bids of $10, is valid?

Answer 15

the difference must be atleast 20 between successive bids for A.
after A bids, B has to bid at least 10 more... so the difference between successive bids for A must be at least 20

Answer 16

yeah, ok i understand that, but why cant we consider the bids of A and B as a combined string (for simplification)?

Answer 17

i count 126 permutations,

Answer 18

50,50 (1)
50,20,20,10 (12)
50,20,10,10,10 (20)
50,10,10,10,10,10 (6)
20,20,20,20,20 (1)
20,20,20,20,10,10 (15)
20,20,20,10,10,10,10 (33)
20,20,10,10,10,10,10,10 (28)
20,10,10,10,10,10,10,10,10 (9)
10,10,10,10,10,10,10,10,10,10 (1)
_______
(126)

Answer 19

suppose A bids first :
```
A : 10, 20, 50
B : 20,30,60 30,40,70 60,70,100
```

in next iteration A can bid below amounts :
```
A : 30,40,70 40,50,80 70,80
40,50,80 50,60,90 80,90
70,80 80,90
```

Answer 20

i see what you are doing there, but it looks like the state space explodes to quickly

Answer 21

so if A bids first, then any state of A starts with (10, x)

x cannot be 20 or 60... this seem to get complicated... i think the given state diagram compresses the complete information concisely

Answer 22

the digram wasn't given i had to draw it myself

Answer 23

To be honest, I think that the order of bits should matter.

Answer 24

Ohh nice i like that state diagram, just noticed it is missing 10->40 transition

Answer 25

10 -> 40, is not +10, +20 or +50

Answer 26

A bids : 10
B bids : 10+10 = 20
A bids : 20+20 = 40

Answer 27

i presume it is open bidding/auction ? isnt it so ?

Answer 28

I would say this, the state graph is a directed graph. Every possible bidding option is an path from the \($0\) state to the \($100\) state.

Answer 29

if A and B bids are not related then solving that diophantine equation will do

Answer 30

Bidding list, bidding outcome

Answer 31

@rational yes it is an open auction

@wio i drew a directed graph, because i don't know what a state graph is, what is the difference?

Answer 32

@UnkleRhaukus What type of class is this?

Answer 33

computer science: algorithms & problem solving

Answer 34

Okay, state graphs are all directed graphs anyway.

Our alphabet is \(\{$10,$20,$50\}\). The different combinations of legal bids that the finite state machine accepts represent the strings that are in this language.

Answer 35

And to make a state a 'win' state, you add two circles to it.

Answer 36

Like S1 in this diagram.

Answer 37

hmm

Answer 38

Wait, I'm going into state machines, but now that I think about it, if this is just an algorithms class, then maybe it should just be a directed graph.

Answer 39

We haven't discussed state machines in class, (yet).

Answer 40

It's a completley different course

Answer 41

Have I computed the permutations correctly? does 126 seem like a reasonable result?

Answer 42

hmmmm permutations

Answer 43

i knew I did this in like 8th or 9th

Answer 44

Yeah, I checked the first few and they were correct.

Answer 45

i'm not heaps sure about the case

20,20,20,10,10,10,10

i got 33, but how do i check it?

Answer 46

You distribute the 20s among the places, and then the rest is filled in with 10s.
This is given by \(^7C_4 ={7\choose 4}= 35\), because the 20s are identical and so order doesn't matter.

Answer 47

Wow, how did you do the original ones?
50,20,10,10,10 would technically be the trickiest, since it would use the multinomial \({5 \choose 1,1,3} = 20\)

Answer 48

for the combination

50,20,10,10,10

x,y,10,10,10
x,10,y,10,10
x,10,10,y,10
x,10,10,10,y

10,x,y,10,10
10,x,10,y,10
10,x,10,10,y

10,10,x,y,10
10,10,x,10,y
10,10,10,x,y

ten combinations, (swapping x and y ) multiply by 2 = 20 combination

Answer 49

20,20,20,10,10,10,10
20,20,10,20,10,10,10
20,20,10,10,20,10,10
20,20,10,10,10,20,10
20,20,10,10,10,10,20

20,10,20,20,10,10,10
20,10,20,10,20,10,10
20,10,20,10,10,20,10
20,10,20,10,10,10,20

20,10,10,20,20,10,10
20,10,10,20,10,20,10
20,10,10,20,10,10,20

20,10,10,10,20,20,10
20,10,10,10,20,10,20

20,10,10,10,10,20,20


10,20,20,20,10,10,10
10,20,20,10,20,10,10
10,20,20,10,10,20,10
10,20,20,10,10,10,20

10,20,10,20,20,10,10
10,20,10,20,10,20,10
10,20,10,20,10,10,20

10,20,10,10,20,20,10
10,20,10,10,20,10,20

10,20,10,10,10,20,20


10,10,20,20,20,10,10
10,10,20,20,10,20,10
10,10,20,20,10,10,20

10,10,20,10,20,20,10
10,10,20,10,20,10,20

10,10,20,10,10,20,20


10,10,10,20,20,20,10
10,10,10,20,20,10,20

10,10,10,20,10,20,20

10,10,10,10,20,20,20


15+10+6+3+1=35

i see the triangle numbers now

Answer 50

\[1+2T(3)+2T(4)+6+1+T(5)+Te(5)+T(7)+9+1=128\]

and maybe double the result because either A or B could bidding first
so

256

Answer 51

where \(T(n\) is the triangular numbers ,
and \(Te(n)\) is the tetrahedral numbers