Free lunch problem

Here is another problem that I found interesting:

• understand the problem:

if you are part of a group that choose who treat to lunch by sitting in a circle and reciting the natural numbers in a counter-clock wise direction starting with the one sitting at the northern extreme of the circle. friends who utter even numbers are eliminated from the counting (and won't get the free lunch either). the counting continues until all but one person is remaining and this person gets the free lunch. so if there are n friends, where would you choose to sit to get the free lunch?

• devise a plan:

draw the outcome for a bunch of n values until you notice a pattern.

• carry out the plan:

here is some values of n that I considered:

observations:

- of course, friends with even numbers get eliminated each round

i.e half of the people get eliminated each round

- when n is odd f1 never gets free lunch since the last number said would be odd = n and f1 would have to say an even number = n+1.

- when n is even, f1 sometimes get free lunch which makes sense since if n is even then half the people get eliminated n/2 can be either even or odd. which takes us back to the starting point (recursion???)

so we can conclude:

 - if dividing n/2 each round will always result in an even number then we should sit at position 1

i.e if n can be written as (2^x)

- if n = (2^x) + y then we should sit at the yth odd number from 1 

so if n = 6 = (2^2) + 2 then we need to sit at the 2nd odd number away from 1 -> 5

i.e. 1+2(y)

here is a python program that would do this for us:

just for fun, I ran this function for n in [1, 50]:

1 -> 1	11 -> 7	21 -> 11	31 -> 31	41 -> 19
2 -> 1	12 -> 9	22 -> 13	32 -> 1	42 -> 21
3 -> 3	13 -> 11	23 -> 15	33 -> 3	43 -> 23
4 -> 1	14 -> 13	24 -> 17	34 -> 5	44 -> 25
5 -> 3	15 -> 15	25 -> 19	35 -> 7	45 -> 27
6 -> 5	16 -> 1	26 -> 21	36 -> 9	46 -> 29
7 -> 7	17 -> 3	27 -> 23	37 -> 11	47 -> 31
8 -> 1	18 -> 5	28 -> 25	38 -> 13	48 -> 33
9 -> 3	19 -> 7	29 -> 27	39 -> 15	49 -> 35
10 -> 5	20 -> 9	30 -> 29	40 -> 17	50 -> 37

products of sum problem

Hey again!

towards the beginning of the term we were introduced to George Polya's method to approaching problems presented in "How to solve it". I intend to follow this method to try to reach a solution to a problem that was presented to us in class.

• Understand the problem:

we are trying to find the maximum product that can be formed of a list of positive integers that sum up to n where n is a positive integer and if we can generalize the solution, we can write a function in python that returns the biggest product of n.

• Plan a solution:

I think the easiest way to tackle this problem is to actually write down all possible lists that sum up to a particular integer and then try to find the biggest product. And if we do this process to enough integers, hopefully, we will recognize a pattern that will help us to reach the solution.

• Carry out the plan:

First: 

we need to write down all the possible lists of positive integers of n for n = 1 till n=6 and determine the largest product for each. 

The best way to write all lists is to start splitting up n into 1s and then gradually group them together to form all possible lists, keeping track at the same time of the product produced by each list (product of elements in the list). and then finding the max of all these products.

Here is the possible lists for n in the interval [1,6]:

                                 

 

1-> 1	(1)=1
2 -> 2	(1,1) = 1	(2) =2
3 -> 3	(1,1,1)=1	(3)=3
	(2,1) =2
4-> 4	(1,1,1,1) =1	(4)=4
	(1,1,2) = 2	(2,2)=4
	(1,3)=3
5->6	(1,1,1,1,1)=1	(5)=5
	(1,1,1,2)=2	(3,2)=6
	(1,1,3)=3
	(1,4)=4
6->9	(1,1,1,1,1,1)=1	(6)=6
	(1,1,1,1,2)=2	(2,2,2)=8
	(1,1,1,3)=3	(1,2,3)=6	(3,3)=9
	(1,1,4)=4	(2,4)=8
	(1,5)=5

Second:

we can observe the following:

- lists that include 1 as an element are not the ones with the biggest sum (except for 1, of course).

- grouping n into 3s and 2s produce the largest product.
However, as you might expect having more 3s would increase the product than having more 2s.

Third:

now we can write a python function that groups n into 3s when possible or 2s.
I used recursion for that: