Math Is Fun Forum

Robar

Member

Registered: 2011-04-28

Posts: 5

Total Number Of Combinations

I'm hoping this is the right area to post this. I've got a final exam coming up shortly and our teacher gave us 5 questions for practice. One of these questions will be the only question on my math exam and I have a feeling that since this one question is the only one I can't figure out that it will be the one on the exam. This exam can cover any topics and can require any equations from any of the 4 years worth of math we took so that's partly what makes this one hard for me to figure out. Any help would be great.

Our teacher provided us with this tool so we knew how the puzzle could be solved and it makes the question make more sense. The tool is located at http://www.miketyndall.com/hobowars/unisolver/ and is apparently part of some online game which is where he got the idea for this question. The only real difference between the question he gave us and this tool is that the tool uses 3 colours with values linked to them where as the question he gave us just uses the values.

After looking at the puzzle you will notice that the puzzle is a 4x4 grid with each grid piece having a value of 'Red' for a -1, 'Yellow' for a 0 or 'Green' for a 1. The idea is to get the highest score possible every time the puzzle is randomly designed. We've been given the following information:

1) The lowest score after solving is 8
2) The highest score after solving is 16

The Question:
a) How many solved puzzle combinations have a final score of 9, 10, 11, 12, 13, 14, and 15?
b) How many total combinations are there?

Basically to answer part b is to just add up the answers from part a but to include a score of 8 and the single score of 16 to the total but I think that he was hoping people would forget to add in the totals for the ones he didn't ask for in part a.

I'm not looking for the answer but rather how to figure out the answer. I'm not sure how to figure out how many combinations of a final score of 8/9/10/11/12/13/14/15/16 there are but I'm sure there's got to be some kind of an equation but I can't figure it out for the life of me.

Once again thanks for those willing to try to help me out

Bob

Administrator

Registered: 2010-06-20

Posts: 10,583

Re: Total Number Of Combinations

hi Robar,

Am I missing a rule here?  I just clicked any circle that wasn't green, until it was green, and so got 16 every time.  Presumably, there is some limit on this, but what?

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Robar

Member

Registered: 2011-04-28

Posts: 5

Re: Total Number Of Combinations

sorry, I forgot about that, that tool lets you do the dots 1 at a time, but the small dots around the left and top side are what are used to change an entire row or column at one time.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,583

Re: Total Number Of Combinations

hi Robar,

Thanks for the reply.

I'm afraid I'm still being confused. This is what I'm getting (or not):

(i) A pattern of three colours on a 4 x 4 grid is generated. 

(ii) Green = +1.  Yellow = 0.  Red = -1

(iii)  The current score total is declared.  The best score is blank.

(iv)  If I click solve, a 'best score' is declared and I'm told what rows / columns to change and by how much (1 change or 2 changes) to reach this score. [three or more changes would be pointlesss]

(v)  A change consists of making a yellow into green, a green into red and a red into yellow.

(vi)  It doesn't seem to matter which order I make the changes since a colour that is affected by both a row and column change ends up cycling through a number of changes determined by adding the row and column changes together.

Now for my confusion.

You have been told the lowest score after solving is 8 and the best score is 16.  I assume that means that a particular puzzle started at 8 and, by making some row and column changes, has been made into 16.

So why would it also have a final value of 9 or 10 or ......

What does 'solving' actually mean?  I thought it meant 'get the best score' so why would I have several 'best scores'?

Bob

Last edited by Bob (2011-04-28 22:59:00)

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Bob

Administrator

Registered: 2010-06-20

Posts: 10,583

Re: Total Number Of Combinations

or maybe you just want to know

How many ways can you get a score of say 15?

To get 16 all must be green.

If you change one green to yellow the score drops by 1.  If you change one green to red the score drops by 2.

So I think the number of ways of getting 15 is just the number of ways you can change one green into yellow = 16

And a score of 14 means either one green has become red = 16 ways or two greens have each become yellow = 16 x 15 / 2 = 120 ways.

Is this what you are after?

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Robar

Member

Registered: 2011-04-28

Posts: 5

Re: Total Number Of Combinations

yes so basically there is only 1 way to get a 16, 16 ways to get a 15, etc. I believe there's 256 ways to get a 14. Once you get to 13 down to 8 it gets a lot more tricky because if you have 3 yellows and a green in a row or column then that's a 13 but when you change that entire row the 3 yellows will turn green and the green will turn red so the best score would be a 14 so that's where I'm having my problems.

Robar

Member

Registered: 2011-04-28

Posts: 5

Re: Total Number Of Combinations

My exam is on Friday, was wondering if anyone had any thoughts on this? I'm still struggling, other than figuring out the puzzles 1 by 1, I can't think of how to calculate this. Thanks again for any help

Bob

Administrator

Registered: 2010-06-20

Posts: 10,583

Re: Total Number Of Combinations

hi Robar,

Sorry about the delay replying; I've been away with no computer.

The analysis seems to get more complex as you drop down from 16, to 15, to 14 etc so I'll have to have a think for a while.  Then I'll post back my best shot at this.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Bob

Administrator

Registered: 2010-06-20

Posts: 10,583

Re: Total Number Of Combinations

hi Robar,

I used Excel to generate all the possibilites with a total of 8 or more.  See the table diagram below.

Now to show you how to work out how many combinations there are for each of these.  I'll use G = 11, Y = 3, R = 2 as an example.

There are 16 different ways to pick the first green, followed by 15 to pick the second, then 14 ... 6 ways to pick the 11th.  These can be re-arranged in 11 x 10 x 9 x....x 2 x 1 ways.  So we have

For the yellows

and for the reds

giving 4368 x 10 x 2 = 87360 ways altogether.

There's a function COMBIN in Excel that will let you produce all of these.

GOOD LUCK with the exam. 

Bob

Last edited by Bob (2011-05-03 04:31:46)

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Total Number Of Combinations

Hi,

We need number of solutions for

Now for the answers, the method may not be helpful for exam, but good for verifying the answers:
Use a generating function:

The co-efficients are your answers, e.g there are 136 ways to yield a sum of 14 (coefficient of x^14), 5196627 ways for a sum of 0 (the constant term), 3620 ways for -12 etc...

Last edited by gAr (2011-05-03 05:28:14)

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Bob

Administrator

Registered: 2010-06-20

Posts: 10,583

Re: Total Number Of Combinations

hi gAr

Now that is very neat!

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Total Number Of Combinations

Hi bob,

Thanks! bobbym taught me to think of generating functions.

But as I mentioned, it's not very helpful for exams if computers are not accessible.

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Bob

Administrator

Registered: 2010-06-20

Posts: 10,583

Re: Total Number Of Combinations

hi gAr,

I don't know what this exam will be like, but a lot of this question isn't testable under exam conditions I think.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Total Number Of Combinations

Hi bob,

Yes, that's what I think too.

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Total Number Of Combinations

Hi;

This idea is interesting but not easier.

If we start with the diophantine equation we can make some adjustments to it that make it just a little bit easier to deal with. At least for a computer anyway. Maybe even by hand because the principle of inclusion exclusion can be used to solve the equation for each n. ( Only for the number of solutions )

Make the substitution:

Now the diophantine equation looks like this:

Now the GF is:

This might be a littler easier to expand and a recurrence is possible.

Just as long as we remember 0<=n <=16 for the recurrence.

1 way to get a 16, 16 ways to get a 15, etc. I believe there's 256 ways to get a 14

I used his values and symmetry to prime the recurrence. Although he is incorrect on 14 having 256 ways. His first 2 are correct. The expense of this is that the answer is not as easy to interpret as gAr's.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Total Number Of Combinations

Hi bobbym,

That recurrence is good.

How do we extract that from a generating function?

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Total Number Of Combinations

Hi gAr;

I wrote routines to do these a long time ago. I have mostly forgotten how to do some of them. The simplest ones I still have some examples for. Supposing you want the recurrence for the coefficients of

Mathematica uses brackets [] for indexed variables. In other words a[1] = 5 puts 5 into the a[1] variable. When I latex a[n] I use a(n) so do not be confused. Use whatever Sage supports, brackets, parentheses, subscripts...

Use your package to duplicate this command.

Expand[(1-x+x2)(a[n]-a[n-1]+a[n-2])]

Notice that that a[n] variables have the same sign as the corresponding x's do. Always order the x's and a[n]'s as I have.

Yields:

Substitute x = 1 in the above expression and you should get.

Set that equal to 0.

Solve for a(n)

That is the recurrence. You will have to get a(0) and a(1) to start it off.

Try:

On your own. See if you can get:

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Total Number Of Combinations

Hi bobbym,

Thanks! Got the examples you explained.
But couldn't get the one for limited terms, (1+y+y^2)^16

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Total Number Of Combinations

Hi gAr;

That one requires a different technique. I think it is based on the method of solving DE's using series. When I programmed that one it seemed very clear to me and I thought I would never forget it. So I did not write it down or copy an example.

Now I all I have is a small mathematica program that works but no idea of what I did!

That was very stupid. I did not keep accurate notes then.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Total Number Of Combinations

Hi bobbym,

Okay.
That's really cool!
When I used rsolve in wolfram, it showed "Gegenbauer polynomials", perhaps you can remember something from that?

By the way, is your method mentioned anywhere in literature? I couldn't find any reference when I searched.

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Total Number Of Combinations

Hi gAr;

The method starts from the operations that you can do to generating functions. It is called the x dx log(x) method named that by me. I do not think you will find it any where in any reference. I pretty much made it myself. I am going to post all I know about it and something new that I have discovered just now. It will be in the Computer Mathematics thread.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Total Number Of Combinations

Hi bobbym,

That's wonderful.
Thank you!

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Robar

Member

Registered: 2011-04-28

Posts: 5

Re: Total Number Of Combinations

Thanks for all your help. This exam has to be calculated 100% by hand and we have 5 hours to complete the single question. There's also a bonus question that will be based on the initial question.

I'll let you know how things go tomorrow! I'm still hoping he doesn't pick this question as it has a lot of writing to it compared to the others.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Total Number Of Combinations

Hi Robar,

All the best.

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."